Monads(?) in C++

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Monads(?) in C++

Postby Yakk » Wed May 27, 2015 4:56 pm UTC

So I'm messing around with optional<T> and exception_or<T> in C++.

I'm vaguely aware that these are related to various monads in Haskell, and there is a construct I want to duplicate, but I don't know how to name it.

Imagine a function apply. Apply( F, Args... ) calls F(Args...), sort of.

If F(Args...) isn't valid, it goes to each argument of Args... and sees if it knows how to modify how it is called.

Suppose we have:

Code: Select all

int add(int a, int b) { return a+b; }

and we do

Code: Select all

apply( add, 3, 7 )

easy, we get 10. add(int,int) is called, and it produces an int. Now we call:

Code: Select all

apply( add, optional<int>(3), 7 )

and instead we get optional<int>(10).

This is because apply sees that

Code: Select all

add(optional<int>, 7)

isn't valid. It asks its first arg if it knows how to modify the call. Optional says "sure! Does it work if I'm an int? If so, I can modify the call to be of the form:

Code: Select all

optional<int>(optional<int>,int)

instead of

Code: Select all

int(int,int)

this is sufficient, so the modified call goes through.

The modified call ends up checking if the first argument is engaged, and if not it bypasses the entire call and returns an empty optional.

A similar thing works with "exception_or< int >", where the "failure" state of an exceptional exception_or< int > propagates to the modified call's return value.

Done right, this even works with a mixture of optionals and exception_or objects.

This should also work with type-safe unions (named variants< typeA, typeB, typeC >). If the original callable doesn't support being called by a variant, but does support being called by each of typeA, typeB and typeC, the variant can modify the call to be one of the 3 calls, with the return types unioned together into a variant.

Throw in collapsing rules (so we don't end up with optional< variant< a, variant< b, optional<c>, exception_or<c> > > >) and we can take a call taking a bunch of these smart types and pass them to a function object expecting dumb types, and get a rich type out the other end.

There are some differences between Haskell and C++ that I'm aware of (you know, cosmetic ones), including the fact that the signature of C++ callables may be more flexible (determining if a given set of arguments is valid for a C++ callable is a Turning-complete process: heck, determining if a C++ callable accepts 3 arguments is a Turing-complete problem. This was an accident of C++ design.), and that a zero-arg C++ function is very different than an evaluated C++ function (which gets in the way of a number of functional idioms).

Is this related to operator >>= in Haskell?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Monads(?) in C++

Postby Derek » Wed May 27, 2015 9:39 pm UTC

I don't recall Haskell having a single operator or function that calls T -> T -> T or optional<T> -> T -> optional<T> or optional<T> -> optional<T> -> optional<T> depending on context, I think you have to use a different operation/function for each of those. But I have very little experience with Haskell (literally just read Learn You a Haskell and did a couple Euler problems), so I may be wrong. However, I believe this is possible with C++ templates. Unfortunately, I'm also no C++ template programmer, so what follows is somewhat of a shot in the dark. I think the idea is right, but details and syntax may need to be fixed.

Code: Select all

template<typename T, typename U, typename V>
V apply(V f(T, U), T a, U b) {
    return f(a, b);
}

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(M<V> f(M<T>, U), M<T> a, U b) {
    return f(a, b);
}

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(M<V> f(T, M<U>), T a, M<U> b) {
    return f(a, b);
}

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(M<V> f(M<T>, M<U>), M<U> a, M<V> b) {
    return f(a, b);
}

If my understanding of templates is right, this will create four templates for the function apply. When you use apply, the correct template should be chosen based on the arguments you pass to it.

However, this requires you to supply an f of the right type. But I think what you wanted was a way to supply a function of T -> U -> V and have it converted to a monadic function. This is the role of fmap or lift (although fmap traditionally takes a 1-parameter functions, but it's easy convert it to a 2-parameter function). C++ doesn't support first class functions, but I think this can be done with templates again.

Code: Select all

// fmap must be implemented for each monad. Here is optional.
template<typename T, typename U, typename V>
optional<V> fmap(V f(T, U), optional<T> a, optional<U> b) {
    if(a && b) {
        return optional(f(a.value(), b.value()));
    } else {
        return optional();
    }
}

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(V f(T, U), M<T> a, M<U> b) {
    return fmap<M>(f, a, b);
}

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(V f(T, U), M<T> a, U b) {
    return fmap(f, a, M(b));
}

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(V f(T, U), T a, M<U> b) {
    return fmap(f, M(a), b);
}

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(V f(T, U), T a, U b) {
    return fmap(f, M(a), M(b));
}


Now, if I have this right, this creates apply functions that should automatically convert any non-monadic arguments into monads, then call fmap for the corresponding monad.

I think the last apply template might clash with the first template in the first block of code, so I don't know if these can be used together. Someone more knowledgeable than me will have to explain how that gets resolved. Actually I would be really interested if anyone who is more knowledgeable with C++ templates could tell me how close I am to being right.

It might even be possible to use variadic templates to make fmap into a function that can convert arbitrarily functions of arbitrarily many parameters into monadic function. However there's a combinatorial explosion in the corresponding apply functions, so I don't know if it's worthwhile.

Tub
Posts: 475
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Monads(?) in C++

Postby Tub » Thu May 28, 2015 7:43 am UTC

Yakk: I'm sure it can be done if you restrict yourself to a defined set of wrappers, e.g. optional<T> and exception_or<T>, but nothing else. It might be possible to solve generically with an unspecified amount of wrappers, but I'd need to think harder to answer that question.

In any case, you will want to use C++11, mostly for three features:
  • std::function. If you want to have first class functions, that's what you want to use.
  • variadic templates. While Derek has shown a possible solution for two arguments, variadic templates allow you to define the template recursively for an arbitrary number of arguments.
  • return type deduction. You can write a function int f(int) as auto f(int) -> int, allowing you to specify the return type in a scope where you can access the function parameters. This leads to constructs such as auto f(int x) -> decltype(x), always returning the type of the first parameter. C++14 is even better, just specify auto f(int) and the return type is deduced from the return statement inside the function body.

The last one is absolutely crucial for recursive templates if your return type is "whatever the recursive call returns".

Note though that template metaprogramming is basically its own language with little resemblance to C++ or haskell, and its rules are neither intuitive nor user-friendly. Be prepared to sink hours or even days into this problem.

Derek wrote:If my understanding of templates is right, this will create four templates for the function apply. When you use apply, the correct template should be chosen based on the arguments you pass to it.

Be very very careful with template precedence. The C++ standard has arcane rules for that, but they're barely understandable for mortals and even the compilers don't always get it right. Especially when template resolution and function overloading start to mix. You'll be writing safer code if you explicitely enable or disable templates with std::enable_if so the compiler doesn't get to choose.

Also, this code is troubling:

Code: Select all

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(M<V> f(M<T>, U), M<T> a, U b) {
    return f(a, b);
}

if you're writing apply(f, a, b), the compiler can substitude anything fitting for M. If, say, one of your function parameters was a std::vector, then M might be std::vector. I think that's when casting std::vector<T> to T will fail, then SFINAE kicks in and saves the day, but still - other containers might not fail and give weird results. Restricting the types that M can be is a good thing.

You'd also need to check what happens when f takes a pointer, a reference, a const reference or even a pointer to a const reference to something. It's easy to lose a reference on template type deduction, and then you'll get additional copies of everything.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Monads(?) in C++

Postby Derek » Thu May 28, 2015 8:35 am UTC

Tub wrote:Also, this code is troubling:

Code: Select all

template<template<typename> M, typename T, typename U, typename V>
M<V> apply(M<V> f(M<T>, U), M<T> a, U b) {
    return f(a, b);
}

if you're writing apply(f, a, b), the compiler can substitude anything fitting for M. If, say, one of your function parameters was a std::vector, then M might be std::vector. I think that's when casting std::vector<T> to T will fail, then SFINAE kicks in and saves the day, but still - other containers might not fail and give weird results. Restricting the types that M can be is a good thing.

There should be no casting in any of my functions if I wrote what I meant (which I probably didn't). This particular example should work regardless of what generic type is used because it involves no magic, it's just passing the arguments along to f and then passing the result back. The point of the first set of function templates was only to show that function overloading would allow it to have the right return value (M<T> if any parameter was M<*>, otherwise T).

The second set of function templates is a bit more magical. It relies on having an fmap defined for whatever M is being used. The intent is for template specialization to fail if fmap has not been defined for M. There are probably better, more readable, and more debuggable ways to do this in C++14 than just relying on the implicit failure when fmap is not defined, but again I'm not really an expert on templates.

You'd also need to check what happens when f takes a pointer, a reference, a const reference or even a pointer to a const reference to something. It's easy to lose a reference on template type deduction, and then you'll get additional copies of everything.

Only if you're paying me six figures.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Monads(?) in C++

Postby Yakk » Thu May 28, 2015 10:56 am UTC

Oh, I have plenty of ideas how to do the function remapping.

Take the argument types. For each argument, explode it into a pair of "change the type x change the function" pairs. Probably via traits class, or via adl based traits function.

Do set product of each arg explosion. Search, using some precidence order, for valid call expressions. Use the first one found.

std::function is not going to be required, as I am not going to accept type erasire overhead. Plus std::function only supports one call signature. Look at boost variant apply -- it takes a function object with overloads -- then add in auto-variant-unioning the return value.

Now, passing in a raw function with overloads doesn't work: but passing in a stateless function object that calls the overloads isn't hard.

Getting this to work is doable: I am concerned I'll make stupid design decisions, and that another language has smoothed over the rough spots already.

...

I thought you could take Maybe<T> and T->T->T and produce Maybe<T>->T->Maybe<T>? Ie, part of a monad was the ability to hook up functions to it without having to write them to support it? Or am I on crack?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Monads(?) in C++

Postby Yakk » Thu May 28, 2015 4:44 pm UTC

Aha! http://en.wikipedia.org/wiki/Monad_%28f ... aybe_monad -- the operation is called lift!

I was thinking it was bind. But bind is (apparently) used to write functions, not adapt existing functions.

https://wiki.haskell.org/Lifting

That gives me somewhere to start.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

DaveInsurgent
Posts: 207
Joined: Thu May 19, 2011 4:28 pm UTC
Location: Waterloo, Ontario

Re: Monads(?) in C++

Postby DaveInsurgent » Thu May 28, 2015 5:00 pm UTC


User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Monads(?) in C++

Postby ahammel » Thu May 28, 2015 5:51 pm UTC

Yakk wrote: I thought you could take Maybe<T> and T->T->T and produce Maybe<T>->T->Maybe<T>? Ie, part of a monad was the ability to hook up functions to it without having to write them to support it? Or am I on crack?

Something like this, you mean?

Code: Select all

λ  let apply f a b = (liftM2 f) (return a) b
λ apply (+) 1 (Just 2)
Just 3
λ apply (+) 1 Nothing
Nothing

In fact, since there's no join or bind operation in there, you don't actually need the full monad interface. You can do that with applicative functors:

Code: Select all

λ  let apply f a b = (liftA2 f) (pure a) b

Or, more idiomatically:

Code: Select all

λ let apply f a b = f <$> pure a <*> b
λ apply (++) "foo" (Just "bar")
Just "foobar"
λ apply (++) "banana" Nothing
Nothing
He/Him/His/Alex
God damn these electric sex pants!

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Monads(?) in C++

Postby Derek » Thu May 28, 2015 9:15 pm UTC

Yakk wrote: I thought you could take Maybe<T> and T->T->T and produce Maybe<T>->T->Maybe<T>? Ie, part of a monad was the ability to hook up functions to it without having to write them to support it? Or am I on crack?

Not automatically, you have to transform the function with fmap/lift. That's what the second part of my post was about:

Derek wrote:I think what you wanted was a way to supply a function of T -> U -> V and have it converted to a monadic function. This is the role of fmap or lift


fmap has to be defined for every monadic type. Alternatively, you can define bind for each type and define fmap in terms of return and bind.

Basically, to define the monadic interface for a type you need to ether define:
- return, fmap/lift, and flatten/join, or
- return and bind

Either set can then be defined in terms of the other.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Monads(?) in C++

Postby Xanthir » Wed Jun 03, 2015 5:38 pm UTC

With "return" being the "here's a plain value, please wrap it in a monad", "fmap" being "here's a plain function, please apply it to the value inside of this monad and give me another monad with the return value in it", and "flatten" being "here's a value double-wrapped in some type of monad, please combine the wrappers together so it's only single-wrapped". These all have to be defined specially for each monad, as the correct behavior depends on how the monad actually works.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 5 guests