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!