c++ - voltear - invertir un numero de forma recursiva en c

Implementando la Posada Monada de Haskell en c++ 11

Question

Estoy intentando implementar la mónada Maybe de Haskell utilizando las funciones lambda en C ++ 11 y las plantillas Esto es lo que tengo hasta ahora

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

Cuando se trata de la llamada real >>= , recibo un error del compilador que dice que no se encontraron coincidencias para el operador >>= . ¿Mi comprensión de las funciones lambda de C ++ 11 me está fallando aquí?

Answer 1

Aquí está mi "mónada" que uso con frecuencia en mis proyectos de C ++ ( descargo de responsabilidad: vea los comentarios a continuación ). Es en la medida más parecida a Haskell Maybe que a su implementación, ya que solo contiene un objeto en el caso just (puntos mobj en él), no desperdiciando espacio si no es nothing . Esto también le permite utilizar la semántica de movimientos de C ++ 11 para evitar copias innecesarias. Los tipos de retorno de fmap (función miembro fmapped ) y >>= se deducen con 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;
}

Los iteradores de begin y end apariencia un tanto extraña permiten que se utilice en el rango de C ++ 11 para bucles:

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

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

Salidas solo una vez 7 .

Answer 2

Copiar y pegar literalmente desde el tipo de Haskell "Tal vez" escriba & * encadenamiento * en C ++ 11

Esto es probablemente lo que realmente quieres lograr

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

Answer 3

El tipo de un lambda no es una especialización de std::function . Es un tipo no amado. Hay una conversión a la std::function , pero eso significa que la deducción de tipos no funcionará para ella. Entonces, en esta convocatoria:

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

El tipo T2 no se puede deducir:

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

Almacene la lambda en una variable std::function desde el principio, y debería funcionar:

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

Sin embargo, es probable que sea más fácil aceptar cualquier tipo de objeto de función. De esa manera todavía puedes usar auto para la 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);
}

Answer 4

Lo siguiente funciona para mí: uso decltype para inferir el tipo devuelto por la 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);    
  }                
}

EDITAR

Para seguridad de tipo:

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");
  ...

Answer 5

Mis 5 cts.

Uso de la muestra:

Maybe<string> m1 ("longlonglong");

auto res1 = m1 | lengthy  | length;

lengthy y length son "lambdas monádicas", es decir

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

Código completo:

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


} // ()

Answer 6

Notamos que la std::function tiene un estado vacío, podemos tener la siguiente implementación

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

En esta implementación, todos los métodos de fábrica son funciones gratuitas (amigo), el operador >> (que no debe confundirse con >> en Haskell, esto es el equivalente de >>= con el mismo asociativo) también es gratuito, e incluso no es un amigo función. También tenga on cuenta la función de miembro, esto se usa para forzar a cualquier cliente que quiera usar una instancia de Maybe debe estar preparada para ambos casos (Solo o Nada).

Aquí hay un ejemplo de uso:

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

La salida es

10 >> 20.5 >> nothing!