Реализация Haskell Возможно, Monad в С++ 11

Я пытаюсь реализовать монадию Maybe из Haskell, используя функции лямбда в С++ 11 и шаблоны. Вот что я до сих пор

#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;
}

Когда дело доходит до фактического вызова >>=, я получаю ошибку компилятора, говоря, что для оператора >>= найдено совпадение. Мое понимание функций lambda С++ 11 не позволяет мне здесь?

Ответ 1

Тип лямбда не является специализацией std::function. Это некоторый неаудированный тип. Существует преобразование в std::function, но это означает, что вычет типа не будет работать для него. Итак, в этом вызове:

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

Тип T2 не может быть выведен:

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

Сохраните лямбда в переменной std::function с самого начала, и она должна работать:

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

Однако, возможно, легче принять любой объект функции. Таким образом, вы можете использовать auto для лямбда.

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

Для меня работает следующее: я использую decltype для вывода типа, возвращаемого лямбдой:

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);    
  }                
}

ИЗМЕНИТЬ

Для безопасности типа:

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

Здесь моя, может быть, "монада", которую я часто использую в своих проектах на С++ (отказ от ответственности: см. комментарии ниже). Это скорее похоже на Haskell Maybe, чем ваша реализация, поскольку он содержит только объект в случае just (точки mobj на нем), не теряя пространства, если он nothing. Это также позволяет использовать семантику перемещения С++ 11, чтобы избежать ненужных копий. Возвращаемые типы fmap (fmapped функция-член) и >>= выводятся с помощью 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 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 <$> 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;
}

Несколько странно выглядящие итераторы begin и end позволяют использовать его в цикле С++ 11 для циклов:

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

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

выводится только один раз 7.

Ответ 4

Отмечено, что std::function имеет пустое состояние, мы можем иметь следующую реализацию

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>();
    });
}

В этой реализации все методы factory являются свободными (друзьями) функциями, оператором >> (не путать с >> в Haskell, это эквивалент >>= с тем же ассоциативным) также свободной и даже не дружественной функции. Также обратите внимание на функцию члена on, которая используется, чтобы заставить любого клиента, который должен использовать экземпляр Maybe, должен быть подготовлен для обоих случаев (Just или Nothing).

Вот пример использования:

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;
}

Выходной сигнал

10 >> 20.5 >> nothing!

Ответ 5

Мои 5 cts.

Использование образца:

Maybe<string> m1 ("longlonglong");

auto res1 = m1 | lengthy  | length;

lengthy и length являются "монадическими лямбдами", то есть

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

Полный код:

// 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

Буквально скопировать и вставить из стиль Haskell "Maybe" type и * chaining * в С++ 11

Это, вероятно, то, чего вы действительно хотите достичь

#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 >;
}