Implementing Haskell's Maybe Monad in c++11

问题:

I am trying to implement the Maybe monad from Haskell using the lambda functions in C++11 and templates. Here's what I have so far

#include<functional>
#include<iostream>
using namespace std;

template<typename T1>
struct Maybe
{
  T1 data;
  bool valid;
};

template<typename T1, typename T2>
Maybe<T2> operator>>=(Maybe<T1> t, std::function < Maybe<T2> (T1)> &f)
{
  Maybe<T2> return_value;
  if(t.valid == false)
  {        
    return_value.valid = false;
    return return_value;
  }
  else
  {        
    return f(t.data);
  }            
}


int main()
{
  Maybe<int> x = {5, true};
  Maybe<int> y = {29, false};

  auto z = [](int a) -> Maybe<int>
    {
      Maybe<int> s;
      s.data = a+1;
      s.valid = true;
      return s;
    };

  Maybe<int> p = (x >>= z);
  Maybe<int> q = (y >>= z);

  cout<<p.data<<' '<<p.valid<<endl;        
  cout<<q.data<<' '<<q.valid<<endl;
}    

When it comes to the actual >>= call, I am getting a compiler error saying that no match found for >>= operator. Is my understanding of C++11's lambda functions failing me here?

回答1:

The type of a lambda isn't a specialization of std::function. It's some unamed type. There is a conversion to std::function, but that means type deduction won't work for it. So, in this call:

Maybe<int> p = (x >>= z);

The type T2 can't be deduced:

Maybe<T2> operator>>=(Maybe<T1> t, std::function < Maybe<T2> (T1)> &f)

Store the lambda in a std::function variable from the start, and it should work:

std::function < Maybe<int> (int)> z = [](int a) -> Maybe<int> { ... };

However, it's probably easier to accept any kind of function object. That way you can still use auto for the lambda.

template<typename T1, typename F>
typename std::result_of<F(T1)>::type
operator>>=(Maybe<T1> t, F&& f) {
    ... std::forward<F>(f)(t.data);
}

回答2:

The following works for me: I use decltype to infer the type returned by the lambda:

template<typename T1, typename Func>    
auto operator>>=(Maybe<T1> t, Func f) -> decltype(f(t.data))
{    
  decltype(f(t.data)) return_value;    
  if(t.valid == false)    
  {            
    return_value.valid = false;    
    return return_value;    
  }    
  else    
  {            
    return f(t.data);    
  }                
}

EDIT

For type safety :

template<typename T1>    
struct Maybe    
{    
  T1 data;    
  bool valid;

  static const bool isMaybe = true;
};

template<typename T1, typename Func>     
auto operator>>=(Maybe<T1> t, Func f) -> decltype(f(t.data)) 
{
  typedef decltype(f(t.data)) RT;
  static_assert(RT::isMaybe, "F doesn't return a maybe");
  ...

回答3:

Here's my maybe "monad" that I use quite often in my C++ projects (disclaimer: see the comments below). It's insofar more like the Haskell Maybe than your implementation as it only holds an object in the just case (points mobj on it), not wasting space if it's nothing. This also allows it to use of C++11 move semantics, to avoid unnecessary copies. The return types of fmap (fmapped member function) and >>= are deduced with decltype.

template<typename DataT>
class maybe;
template<typename DataT>
maybe<DataT> just(const DataT &obj);
struct nothing_object{nothing_object(){}};
const nothing_object nothing;

                 //template class objects of which may or may not contain some given
                // data object. Inspired by Haskell's Maybe monad.
template<typename DataT>
class maybe {
  DataT *obj;

 public:

  class iterator {
    DataT *mobj;
    explicit iterator(DataT *init):mobj(init){}
   public:
    iterator():mobj(nullptr){}
    iterator(const iterator &cp):mobj(cp.mobj){}
    bool operator!=(const iterator &other)const{return mobj!=other.mobj;}
    DataT &operator*() const{return *mobj;}
    iterator &operator++(){ mobj=nullptr; return *this; }
    friend class maybe;
  };
  class const_iterator {
    const DataT *mobj;
    explicit const_iterator(const DataT *init):mobj(init){}
   public:
    const_iterator():mobj(nullptr){}
    const_iterator(const const_iterator &cp):mobj(cp.mobj){}
    bool operator!=(const const_iterator &other)const{return mobj!=other.mobj;}
    const DataT &operator*() const{return *mobj;}
    const_iterator &operator++(){ mobj=nullptr; return *this; }
    friend class maybe;
  };
  iterator begin(){return iterator(obj);}
  iterator end(){return iterator();}
  const_iterator begin()const{return const_iterator(obj);}
  const_iterator end()const{return const_iterator();}
  const_iterator c_begin()const{return const_iterator(obj);}
  const_iterator c_end()const{return const_iterator();}

  bool is_nothing()const{return obj==nullptr;}
  void make_nothing(){delete obj; obj=nullptr;}
  bool is_just()const{return obj!=nullptr;}
  template<typename CpDataT>
  void with_just_assign(CpDataT &mdftg)const{if(obj) mdftg=*obj;}
  DataT &from_just(){return *obj;}
  DataT &operator*(){return *obj;}
  const DataT &from_just()const{return *obj;}
  const DataT &operator*()const{return *obj;}

  template<typename CmpDataT>
  bool operator==(const maybe<CmpDataT> &cmp)const{
    return is_just()==cmp.is_just() && (is_nothing() || *obj==*cmp.obj); }
  template<typename CmpDataT>
  bool operator!=(const maybe<CmpDataT> &cmp)const{
    return is_just()!=cmp.is_just() || (is_just() && *obj!=*cmp.obj); }
  bool operator==(const nothing_object &n)const{return obj==nullptr;}
  bool operator!=(const nothing_object &n)const{return obj!=nullptr;}

  template<typename MpFnT>
  auto fmapped(MpFnT f) const -> maybe<decltype(f(*obj))> {
    return obj? just(f(*obj)) : nothing;                  }
  template<typename MonadicFn>
  auto operator>>=(MonadicFn f) const -> decltype(f(*obj)) {
    return obj? f(*obj) : nothing;                         }
  template<typename ReplaceDT>
  auto operator>>(const maybe<ReplaceDT> &r) const -> maybe<ReplaceDT> {
    return obj? r : nothing;                                           }
  auto operator>>(const nothing_object &n) const -> maybe<DataT> {
    return nothing;                                              }


  maybe(const nothing_object &n):obj(nullptr){}
  template<typename CpDataT>
  explicit maybe(const CpDataT &cobj):obj(new DataT(cobj)){}
  template<typename CpDataT>
  maybe &operator=(const CpDataT &cobj){delete obj; obj=new DataT(cobj); return *this;}
  template<typename CpDataT>
  maybe(const maybe<CpDataT> &cp):obj(cp.is_just()?new DataT(cp.from_just()):nullptr){}
  template<typename CpDataT>
  maybe &operator=(const maybe<CpDataT> &cp){
    delete obj;  obj = cp.is_just()? new DataT(cp.from_just()) : nullptr; return *this;}
  maybe(maybe<DataT> &&mv):obj(mv.obj){mv.obj=nullptr;}
  maybe &operator=(maybe<DataT> &&mv) {
    delete obj; obj=mv.obj; mv.obj=nullptr; return *this; }

  ~maybe(){delete obj;}
};

template<typename DataT>
auto just(const DataT &obj) -> maybe<DataT> {return maybe<DataT>(obj);}

template<typename MpFnT, typename DataT>              // represents Haskell's <$> infix
auto operator^(MpFnT f, const maybe<DataT> &m) -> decltype(m.fmapped(f)) {
  return m.fmapped(f);
}

template<typename DataT>
auto joined(const maybe<maybe<DataT>> &m) -> maybe<DataT> {
  return m.is_just()? m.from_just() : nothing;
}


template<typename DataT>
auto maybe_yes(const std::pair<DataT,bool>& mbcst) -> maybe<DataT> {
  return mbcst.second ? just(mbcst.first) : nothing;
}
template<typename DataT>
auto maybe_not(const std::pair<DataT,bool>& mbcst) -> maybe<DataT> {
  return !mbcst.second ? just(mbcst.first) : nothing;
}

The somewhat strange-seeming begin and end iterators allow it to be used in C++11 range-based for loops:

maybe<int> a = just(7), b = nothing;

for (auto&i: a) std::cout << i;
for (auto&i: b) std::cout << i;

outputs only once 7.

回答4:

Noticed that std::function have an empty state, we can have the following implementation

template<typename T>
class Maybe{
private:
    Maybe(T t){
        get = [t](){ return t; };
    }
    Maybe(){}
    std::function<T ()> get;
public:
    typedef T content_type;

    template<typename WhenJust, typename WhenNothing>
    auto on(WhenJust &&whenJust, WhenNothing &&whenNothing) 
        -> decltype(whenNothing()){
        if(get==nullptr) return whenNothing();
        else return whenJust(get());
    }
    template<typename U>
    friend Maybe<U> just(U u);
    template<typename U>
    friend Maybe<U> nothing();
};

template<typename T>
Maybe<T> just(T t){
    return Maybe<T>(t);
}

template<typename T>
Maybe<T> nothing(){
    return Maybe<T>();
}

template<typename T, typename BinderFunction>
auto operator >>(Maybe<T> m, BinderFunction bind) 
    -> Maybe<typename decltype(bind(*((T*)nullptr)))::content_type> {
    return m.on([bind](T v){
        return bind(v);
    },[](){
        return nothing<typename decltype(bind(*((T*)nullptr)))::content_type>();
    });
}

In this implementation, all factory methods are free (friend) functions, the >> operator (not to be confused with >> in Haskell, this is the equivalent of >>= with same associative) is also free, and even not a friend function. Also notice the on member function, this is used to force any client intended to use a Maybe instance must be prepared for both cases (Just or Nothing).

Here is an example of usage:

int main()
{
    auto n = just(10) >> [](int j){ std::cout<<j<<" >> "; return just(j+10.5); }
        >> [](double d){ std::cout<<d<<" >> "; return nothing<char>(); }
        >> [](char c){ std::cout<<c; return just(10); }
        ;

    n.on(
        [](int i) { std::cout<<i; },
        []() { std::cout<<"nothing!"; });

    std::cout << std::endl;
    return 0;
}

The output is

10 >> 20.5 >> nothing!

回答5:

My 5 cts.

Sample usage:

Maybe<string> m1 ("longlonglong");

auto res1 = m1 | lengthy  | length;

lengthy and length are "monadic lambdas", i.e.

auto length = [] (const string & s) -> Maybe<int>{ return Maybe<int> (s.length()); };

Complete code:

// g++ -std=c++1y answer.cpp

#include <iostream>
using namespace std;

// ..................................................
// begin LIBRARY
// ..................................................
template<typename T>
class Maybe {
  // 
  //  note: move semantics
  //  (boxed value is never duplicated)
  // 

private:

  bool is_nothing = false;

public:
  T value;

  using boxed_type = T;

  bool isNothing() const { return is_nothing; }

  explicit Maybe () : is_nothing(true) { } // create nothing

  // 
  //  naked values
  // 
  explicit Maybe (T && a) : value(std::move(a)), is_nothing(false) { }

  explicit Maybe (T & a) : value(std::move(a)), is_nothing(false) { }

  // 
  //  boxed values
  // 
  Maybe (Maybe & b) : value(std::move(b.value)), is_nothing(b.is_nothing) { b.is_nothing = true; }

  Maybe (Maybe && b) : value(std::move(b.value)), is_nothing(b.is_nothing) { b.is_nothing = true; }

  Maybe & operator = (Maybe & b) {
    value = std::move(b.value);
    (*this).is_nothing = b.is_nothing;
    b.is_nothing = true;
    return (*this);
  }
}; // class

// ..................................................
template<typename IT, typename F>
auto operator | (Maybe<IT> mi, F f)  // chaining (better with | to avoid parentheses)
{
  // deduce the type of the monad being returned ...
  IT aux;
  using OutMonadType = decltype( f(aux) );
  using OT = typename OutMonadType::boxed_type;

  // just to declare a nothing to return
  Maybe<OT> nothing;

  if (mi.isNothing()) {
    return nothing;
  }

  return f ( mi.value );
} // ()

// ..................................................
template<typename MO>
void showMonad (MO m) {
  if ( m.isNothing() ) {
    cout << " nothing " << endl;
  } else {
    cout << " something : ";
    cout << m.value << endl;
  }
}

// ..................................................
// end LIBRARY
// ..................................................

// ..................................................
int main () {

  auto lengthy = [] (const string & s) -> Maybe<string> { 
    string copyS = s;
    if  (s.length()>8) {
      return Maybe<string> (copyS);
    }
    return Maybe<string> (); // nothing
  };

  auto length = [] (const string & s) -> Maybe<int>{ return Maybe<int> (s.length()); };

  Maybe<string> m1 ("longlonglong");
  Maybe<string> m2 ("short");

  auto res1 = m1 | lengthy  | length;

  auto res2 = m2 | lengthy  | length;

  showMonad (res1);
  showMonad (res2);


} // ()

回答6:

Literally copy & pasting from Haskell style "Maybe" type & *chaining* in C++11

This is probably what you really want to achieve

#include <iostream>
#include <map>
#include <deque>
#include <algorithm>
#include <type_traits>

typedef long long int int64;

namespace monad { namespace maybe {

  struct Nothing {};

  template < typename T >
  struct Maybe {
    template < typename U, typename Enable = void >
    struct ValueType {
      typedef U * const type;
    };

    template < typename U >
    struct ValueType < U, typename std::enable_if < std::is_reference < U >::value >::type > {
      typedef typename std::remove_reference < T >::type * const type;
    };

    typedef typename ValueType < T >::type value_type;

    value_type m_v;

    Maybe(Nothing const &) : m_v(0) {}

    struct Just {
      value_type m_v;
      Just() = delete;
      explicit Just(T &v) : m_v(&v) {
      }
    };

    Maybe(Just const &just) : m_v(just.m_v) {
    }
  };

  Nothing nothing() {
    return Nothing();
  }

  template < typename T >
  Maybe < T > just(T &v) {
    return typename Maybe < T >::Just(v);
  }

  template < typename T >
  Maybe < T const > just(T const &v) {
    return typename Maybe < T const >::Just(v);
  }

  template < typename T, typename R, typename A >
  Maybe < R > operator | (Maybe < T > const &t, R (*f)(A const &)) {
    if (t.m_v)
      return just < R >(f(*t.m_v));
    else
      return nothing();
  }

  template < typename T, typename R, typename A >
  Maybe < R > operator | (Maybe < T > const &t, Maybe < R > (*f)(A const &)) {
    if (t.m_v)
      return f(*t.m_v);
    else
      return nothing();
  }

  template < typename T, typename R, typename A >
  Maybe < R > operator | (Maybe < T > const &t, R (*f)(A &)) {
    if (t.m_v)
      return just < R >(f(*t.m_v));
    else
      return nothing();
  }

  template < typename T, typename R, typename A >
  Maybe < R > operator | (Maybe < T > const &t, Maybe < R > (*f)(A &)) {
    if (t.m_v)
      return f(*t.m_v);
    else
      return nothing();
  }

  template < typename T, typename R, typename... A >
  Maybe < R > operator | (Maybe < T const > const &t, R (T::*f)(A const &...) const) {
    if (t.m_v)
      return just < R >(((*t.m_v).*f)());
    else
      return nothing();
  }

  template < typename T, typename R, typename... A >
  Maybe < R > operator | (Maybe < T const > const &t, Maybe < R > (T::*f)(A const &...) const) {
    if (t.m_v)
      return just < R >((t.m_v->*f)());
    else
      return nothing();
  }

  template < typename T, typename R, typename... A >
  Maybe < R > operator | (Maybe < T const > const &t, R (T::*f)(A const &...)) {
    if (t.m_v)
      return just < R >(((*t.m_v).*f)());
    else
      return nothing();
  }

  template < typename T, typename R, typename... A >
  Maybe < R > operator | (Maybe < T const > const &t, Maybe < R > (T::*f)(A const &...)) {
    if (t.m_v)
      return just < R >((t.m_v->*f)());
    else
      return nothing();
  }

  template < typename T, typename A >
  void operator | (Maybe < T > const &t, void (*f)(A const &)) {
    if (t.m_v)
      f(*t.m_v);
  }

}}

struct Account {
  std::string const m_id;
  enum Type { CHECKING, SAVINGS } m_type;
  int64 m_balance;
  int64 withdraw(int64 const amt) {
    if (m_balance < amt)
      m_balance -= amt;
    return m_balance;
  }

  std::string const &getId() const {
    return m_id;
  }
};

std::ostream &operator << (std::ostream &os, Account const &acct) {
  os << "{" << acct.m_id << ", "
 << (acct.m_type == Account::CHECKING ? "Checking" : "Savings")
 << ", " << acct.m_balance << "}";
}

struct Customer {
  std::string const m_id;
  std::deque < Account > const m_accounts;
};

typedef std::map < std::string, Customer > Customers;

using namespace monad::maybe;

Maybe < Customer const > getCustomer(Customers const &customers, std::string const &id) {
  auto customer = customers.find(id);
  if (customer == customers.end())
    return nothing();
  else
    return just(customer->second);
};

Maybe < Account const > getAccountByType(Customer const &customer, Account::Type const type) {
  auto const &accounts = customer.m_accounts;
  auto account = std::find_if(accounts.begin(), accounts.end(), [type](Account const &account) -> bool { return account.m_type == type; });
  if (account == accounts.end())
    return nothing();
  else
    return just(*account);
}

Maybe < Account const > getCheckingAccount(Customer const &customer) {
  return getAccountByType(customer, Account::CHECKING);
};

Maybe < Account const > getSavingsAccount(Customer const &customer) {
  return getAccountByType(customer, Account::SAVINGS);
};

int64 const &getBalance(Account const &acct) {
  return acct.m_balance;
}

template < typename T >
void print(T const &v) {
  std::cout << v << std::endl;
}

int main(int const argc, char const * const argv[]) {
  Customers customers = {
    { "12345", { "12345", { { "12345000", Account::CHECKING, 20000 }, { "12345001", Account::SAVINGS, 117000 } } } }
  , { "12346", { "12346", { { "12346000", Account::SAVINGS, 1000000 } } } }
  };

  getCustomer(customers, "12346") | getCheckingAccount | getBalance | &print < int64 const >;
  getCustomer(customers, "12345") | getCheckingAccount | getBalance | &print < int64 const >;
  getCustomer(customers, "12345") | getSavingsAccount | &Account::getId | &print < std::string const >;
  //  getCustomer(customers, "12345") | getSavingsAccount | [](Account &acct){ return acct.withdraw(100); } | &print < std::string const >;
}