Monads in Julia (and module problems)

[Patrick O'Leary]

I've finally decided to complete the remaining exercises in Seven Languages in Seven Weeks, the last of which is "Implement a Monad in a nonfunctional language." So I implemented four of them. In Julia. And wrote a macro so you can use Haskell's do-syntax (with minor differences).

Here's the source: https://gist.github.com/3677645

And you can do silly things like:

julia> @mdo begin
         a <- Maybe(1)
         b <- Maybe(2)
         return a + 2*b
       end
Maybe(5)

julia> @mdo begin
         a <- Maybe(1)
         b <- Maybe(nothing)
         return a + 2*b
       end
Maybe(nothing)

or:

julia> @mdo begin
         a <- MList(1:3)
         b <- MList(4:6)
         return (a,b)
       end
MList([(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)])

(seriously, just use a list comprehension!)

There are also implementations of Identity and State. So, uh, have fun?

If you look at the source, I've commented out all the module bits. It turns out that I hit interesting scoping problems if you use the modularized version:

julia> @mdo begin
         y <- @mdo begin
           x <- Identity(5)
           return x+1
         end
         return y + 1
       end
x not defined

julia> mtest(m) = @mdo begin
         x <- m
         y <- Identity(x+1)
         return y + 1
       end

julia> mtest(Identity(5))
in mtest: m not defined
 in mtest at none:51

So I've no idea how to sort that out. Spelled out explicitly, it works as expected:

julia> bind(bind(Identity(5)) do x
         mreturn(Identity, x+1)
       end) do y
         mreturn(Identity, y+1)
       end                    
      
Identity(7)

At any rate, I hope someone finds this interesting. Ideas for improvements are certainly welcome too!

[Jeffrey Sarnoff]

interesting

[Stefan Karpinski]

This clearly supports Jeff's characterization of Julia as "dragging Matlab programmers halfway to Haskell".

interesting

--
 
 
 

[Patrick O'Leary]

LOL. I'm still playing with this a bit. For instance, the version posted sequences the line numbers as monadic actions. I've fixed it locally but I'm messing with other stuff so haven't updated the gist. And you can do guards now for instances of MonadPlus (basically just MList).

With this much abstraction (lambdas, lambdas everywhere) it's definitely slow, but writing it has found a couple Julia bugs, and I'd still like to see if there's a kernel of truly useful here.

Since I have peoples' attention: Any ideas on the module problems?

[Stefan Karpinski]

I got 99 problems but a module ain't one.

--
 
 
 

[Stefan Karpinski]

Seriously, thought, I think Jeff has to address that.

[Andrei de Araújo Formiga]

I commented on the gist earlier, twice, but I fumbled both comments (and I don't see how to do to delete them) so I'm doing it here again.

I was looking at this monad implementation today and trying the examples. My results are a bit different:

julia> @mdo begin
         a <- Maybe(1)
         b <- Maybe(2)
         return a + 2*b
       end

in @mdo: wrong number of arguments
 in @mdo at /Users/andrei/Dropbox/code/julia/monad.jl:37
 in anonymous at no file
 in event_loop at multi.jl:1622
 in anonymous at no file

Trying a simpler example:

julia> @mdo begin

         a <- Maybe(1)

         return a

       end

in @mdo: wrong number of arguments

 in @mdo at /Users/andrei/Dropbox/code/julia/monad.jl:37

 in anonymous at no file

 in event_loop at multi.jl:1622

 in anonymous at no file

Going by the error (wrong # of arguments) and going by the source, I guess I should include the type in the macro instantiation. Then the simple example works:

julia> @mdo Maybe begin

         a <- Maybe(1)

         return a

       end

Maybe{Maybe{Int64}}(Maybe{Int64}(1))

But the original example still doesn't:

julia> @mdo Maybe begin

         a <- Maybe(1)

         b <- Maybe(2)

         return a + 2*b

       end

no method *(Int64,Maybe{Int64})

 in method_missing at base.jl:70

 in anonymous at no file:52

 in bind at /Users/andrei/Dropbox/code/julia/monad.jl:123

 in anonymous at no file:51

 in bind at /Users/andrei/Dropbox/code/julia/monad.jl:123

Am I doing something wrong or is there a problem with the implementation?

2012/9/8 Patrick O'Leary <patrick...@gmail.com>:

> --
>  
>  
>  

[Patrick O'Leary]

On Tuesday, October 9, 2012 9:38:53 PM UTC-5, Andrei Formiga wrote:

I commented on the gist earlier, twice, but I fumbled both comments (and I don't see how to do to delete them) so I'm doing it here again.

Sorry, I thought I had email notification on those, but apparently either not or GMail filtered them.

Am I doing something wrong or is there a problem with the implementation?

You say that like there's anything *right* about the implementation!

That aside, I've gone back and forth on whether to attempt to infer the monad that the @mdo is operating in.  As you've noticed the most recent version votes "no." It really complicates the rewriting and could never have all the guarantees you get in Haskell.

As far as your error goes, it looks like whatever I last put in the gist is broken. I'll try to debug it. If you wanted to play in the meantime, look through the history; just be aware of whether that version of @mdo takes one or two arguments.

[Patrick O'Leary]

On Tuesday, October 9, 2012 10:04:58 PM UTC-5, Patrick O'Leary wrote:

As far as your error goes, it looks like whatever I last put in the gist is broken. I'll try to debug it. If you wanted to play in the meantime, look through the history; just be aware of whether that version of @mdo takes one or two arguments.

 

And fixed. Mental error on my part, I was trying to automatically lift the RHS of a bind arrow, which was a bad idea. You can diff the version I just uploaded with the one before to see the fix. Related exercise for the reader: Implement liftM. Hint: I believe you'll need the same magic type insertion used to implement guard(), mreturn(), and mzero().

[Patrick O'Leary]

Updated: there's now a module, desugaring of @mdo blocks is now properly implemented as a right fold, and there's now a liftM() though I'm still working out how to lift a function in an arbitrary number of variables. The current liftM() is copied from the Prelude in the meantime. I'd just rather not have to implement liftM2(), liftM3(), etc. like Haskell does.

[Jeffrey Sarnoff]

Just wondering: why did you choose to define maybeType as a Composite Type with a Union typed value

type Maybe{T} <: Monad
           value :: Union(T, Nothing)
       end

instead of using a functional generator for  a simple union type

maybeType = T -> Union(T,Nothing)
maybeInt64 = maybeType(Int64)

[Patrick O'Leary]

On Thursday, October 11, 2012 11:51:02 PM UTC-5, Jeffrey Sarnoff wrote:

Just wondering: why did you choose to define maybeType as a Composite Type with a Union typed value

type Maybe{T} <: Monad
           value :: Union(T, Nothing)
       end

instead of using a functional generator for  a simple union type

maybeType = T -> Union(T,Nothing)
maybeInt64 = maybeType(Int64)

Because I need it in the type hierarchy (Maybe{T} <: Monad) to get the rest of the combinators; because I need an actual type so I can use the singleton to properly implement mreturn(); because generating a bunch of different unrelated types for different T makes a lot less sense than a family of parametric types.

[Jeffrey Sarnoff]

makes sense

moving on,  is there any way to do this (or to obtain a similar outcome)?

    abstract AbsType
     Union(TypeA, TypeB) <: AbsType