Is currying monadic?

Here’s a question that came up while I’ve been trying to
href="http://greenokapi.net/blog/2009/05/04/currying-in-perl/">implement
currying in Perl: is Currying monadic?

I’ve tried a couple of times, but not managed to explain what I mean very well on #haskell, so let’s
see if a longer writeup explains it better.

My simplistic understanding of monads is that they take various things that
are nests of nested expressions, and allow you to reason about them, and
given them a pretty syntax that makes it look like they are in fact a
sequence of commands.

For example: (pseudocode)

    let a = 1
    let b = 2
    output a+b

Looks like a sequence of commands, but you couldn’t just separate each
line and string the commands together. Rather you have to consider it
as a nest:

    (let a = 1
        (let b = 2
            (output a+b )))

And in many cases, we can go from a nested structure to a monad, for example, we could simplify these horribly nested ifs:

    (if file exists
        (if file is readable
            (if reading the file gave a string
                (if the string matches a username
                    (do some action with the username)))))

… into a nice Maybe monad:

    do check file exists
       check file is readable
       string <- read from file
       check string matches username
       do something with the username

Similarly, nested lists:

    (for each i in list 1
        (for each j in list 2
            (is i the same as j?
                (output i))))

can be abstracted as a List monad:

    do i <- list 1
       j <- list 2
       check i == j
       output i

OK, so I'm not talking about wrapping and unwrapping values, the monad
laws, or typing in general. They are what gives this stuff its strong
theoretical basis and makes it robust. But the simple-minded "Nest ->
Sequence" idea works for me at least, and gives a good feel for
where monads can come in useful.

Currying

So... when I was implementing currying, I noted that you could write a
currying sub (pseudocode again):

    function add3 (a, b, c) {
        return a+b+c
    }

as something like this:

    function add3 (a) {
        return function (b) {
            return function (c) {
                return a+b+c 
            } 
        } 
    }

This is again a nested expression. So I wondered if you could again "flatten" it with a monadic do block:

    let add3 = do
        a <- get first parameter
        b <- get second parameter
        c <- get third parameter
        return a+b+c

OK, so I "know" that functions in Haskell (which uses currying for
functions as a general rule) are the "Reader monad". But I don't
understand it well enough to know if that means you can use Reader to
implement the above...

(I don't understand Reader at all in fact. I must bang my head against
it again, but I find it very confusing - how the monad is represented,
what the functions are, and how they get magically applied.)

So, I did attempt to implement it using my Perl module
Acme::Monads. This href="http://github.com/osfameron/acme--monads/blob/master/t/04_curry.t">test
shows that this sort of works:

    my $add = mdo (2) {
        mbind $x = Curry shift;
        mbind $y = Curry shift;
        return $x+$y;
        };

    say $add->(1)->(2); # 3, yay!

Note that the "return" isn't a monadic Unit but Perl's return,
i.e. a plain value. That makes this example strictly speaking not
monadic: what I don't know is whether that means the whole idea is fatally flawed, or whether (as I believe) I was just too dumb to fix the errors I got when I tried running with munit...
I suspect that it should be possible, with the
whole expression then being wrapped by some function
(runCurry?) which extracts the final result out of the monad.

Did this explanation make any sense? Please let me know, and any
comments on whether it's possible/sane to do this (writing currying as a
monad) are appreciated!

Comments

  1. Ganesh Sittampalam says:

    This is basically a state monad where the state is a list of arguments that you then pop one element off at a time. In Haskell you’d have some issues with type safety (since all the elements of a list have to have the same type and you might well want differently typed arguments), and you’d probably have to use some kind of indexed monad to get full static type checking for it.

  2. Zoheb Vacheri says:

    Currying is Applicative. This will be obvious if you look at the Control.Applicative class. Monads are an instance of Applicative. So currying could also be Monadic if they observe the monad laws

    Prelude Control.Applicative> import Control.Applicative
    Prelude Control.Applicative> pure (+) Just 3 Just 4
    Just 7

    I used the MayBe Monad but you could create your own type that just boxes a value and pure could be simply something like id.

  3. Zoheb Vacheri says:

    The code in the previous comment got screwed up

    Prelude Control.Applicative> import Control.Applicative

    Prelude Control.Applicative> pure (+) Just 3 Just 4

    Just 7

  4. Zoheb Vacheri says:

    Given that Maybe is a Monad and not just an Applicative Functor, it should be easy to see by analogy that currying/application should also satisfy the Monad laws.

  5. First the family Reader monads:

    Reader a = (a ->)

    So a curried multi-parameter function can be considered as a composition of many Readers.

    Reader a . Reader b . Reader c == (a ->) . (b ->) . (c ->)

    A monad is a functor equipped with two natural transformations that follow certain laws. So this composition is actually a composition of functors. Another way of looking at it is that we’re wrapping many functors around the same holes, so we can rewrite the composition as (a -> b -> c -> -) using dash as our metasyntactic variable, as is common in category theory. Similarly we can think of ([-] . [-] . [-]) which can also be written as [[[-]]].

    For the [[[-]]] example, one of the monad laws allows us to collapse multiple layers into a single layer so every [[[X]]] can be mapped to some [[X]] and every [[X]] can be mapped to some [X], both with certain properties of “preserving structure”. Now, in the case of Reader we should consider what that means. Using join requires that all the layers are the same (e.g. (a->).(a->)), but the join of the Reader monad collapses that so everyone reads from the same a (it maps every (a->a-> X) to some (a-> X)), which isn’t what we want for currying.

    But there is a different way that we can “collapse” the composition of different Reader monads. Namely, we can find a mapping from (a->).(b->).(c->) to (a * b * c ->) aka ((a,b,c) ->). This general process is what uncurrying is about, and the dual is currying.

    So, to answer your question, no currying does not form a monad— at least not directly. However, the type constructor Reader is itself a functor as well, not just (Reader X) for all X. So if we look at (->) as a functor, then the composition (a->).(b->).(c->) is remarkably similar to the expression [a]++[b]++[c] which can be reduced to [a,b,c] in analogue with (a * b * c->). Note particularly the two different operators in flight for both examples.

    The natural isomorphism between (a->).(b->) and (a * b->) is quite different from the natural transformation from F.F to F. For one, the former is an isomorphism so we can rewrite in either direction. Other details have to do with the fact that (->) forms a category (with id and (.)) and that it doesn’t form a monoid (with the same) except in the restricted case of endomorphisms (X->X).

    For un/currying to be possible the category for (->) must be cartesian closed, meaning it has all products and exponentials as objects. Most of the common categories are CCC, but not all are.

  6. Er, it looks like your blog ate the asterices in (a * b * c ->) and rendered them as italics.

    (Reply: yeah, looks like it does formatting, I thought I’d turned that off for comments, *sigh*. I’ve edited, adding some spacing which seems to work around that).

  7. Zoheb Vacheri says:

    I just found a post that created a “Trivial Monad”, like the one I talked about above like MayBe in Dan Piponi’s blog. I think what you have done is recreate the “Trivial Monad” in Perl.

    http://blog.sigfpe.com/2007/04/trivial-monad.html

  8. Ganesh is right that it looks like a state monad, where the state is perhaps a stack of arguments. Rather then “get first parameter” and “get second parameter”, you will have one command getting the next parameter.

    However, you’d really want some static type checking preventing you from calling getNextParameter too many times, while allowing you to but elements of different types in the stack.

    You can perhaps index a state monad-like structure by the type of call stack it expects. For example, “ST (Int, (Double, (Char, ()))) Int” could be the encoding of a function Int -> Double -> Char -> Int, and the getNextParameter method might have type:

    getNextParameter :: (a -> ST as b) -> ST (a , as) b

    But I am not sure whether it is still a monad, though…