Back to Questions
1.5k
views4
comments
Which is the best type to use for a monad definition?
f#monad

I just did a blog entry on creating a maybe monad using a typedef for the option type.

[link:blog.matthewdoig.com]

There are several other options for defining this maybe monad.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//typedef for an option
type Maybe<'a> = option<'a>

//typedef for an function that returns an option
type Maybe<'a> = (unit -> option<'a>)

//a type that contains an option
type Maybe<'a>(value: option<'a>) = 
    member v.Value = value

// a type that contains a function that returns an option
type Maybe<'a>(value: (unit -> option<'a>)) = 
    member v.Value = value
    static member Run(m : Maybe<'a>) = m.Value()

I've worked through the code from the blog entry using each of the types and i'm leaning towards option 4 for monads. Any thoughts on why this type would be a problem for monad defintitions?

.

Option 'a> itself is a monad. If you think of it as a container it either contains a value of type 'a or nothing. Although you can define the alias Maybe 'a> for Option 'a> because Haskell uses that name it's not necessary. Defining a "run" function isn't necessary either. The result of the computation expression is of type Option 'a>. The value is still contained in the monad. The Option module in the standard library already has functions to extract a value out of the Option container. "Run" functions are defined in Haskell for extracting the end result out of a monad which is useful for complex monads like parser combinators.

P.S. Does anyone know how to display < characters on this forum?

By on 10/10/2008 3:36 AM ()

Personally I would choose the first option. Presumably all 4 will present the same user-facing API/programming model for people coding against the monad entirely using workflows, so the only difference is how it interfaces with non-workflow code. There's plenty of existing functions that use option<'a> that could automagically interoperate with the first option, whereas for the rest, it'd require massaging. Consider

1
2
3
4
5
6
7

let myMap = new Map<_,_>(["A",1;"B",2])
let addByKey =
    maybe {
        let! x = myMap.TryFind "A"
        let! y = myMap.TryFind "B"
        return x + y
    }

This code 'just works' with the first representation option, whereas for other choices, you'd have to 'massage' the right-hand-sides of the "let!" lines to make it work. The advantage of the first choice is that it makes the monad work seamlessly with Map.TryFind and lots of other library functions.

By on 10/9/2008 10:06 PM ()

It's getting late and so i will have to run your example code tomorrow. Does f# support implict user defined type conversions?

[link:msdn.microsoft.com]

Another option is

1
2
3

type Maybe<'a>(value: option <'a>) = 
    member v.Value = (fun () -> value)
    static member Run(m : Maybe<'a>) = m.Value()

I can see the practical value of using the monad as an option type. It "just works" anywhere an option type is expected.

However, when i read about monads they are not really so much types as they are type generators. I believe this is why Don Syme has chosen to represent the attempt monad as a (unit -> 'a option). This has the added advantage of being able to run the monad at a different location in the code from where it is defined.

A third option is to use a class type definition that contains the type. This reinforces the concept of a monad as a contianer for the underlying type. Plus additional behavior can be attached to and discovered about the monad. The async monad is defined in the control library as a class type and provides static members for manipulation. Any monad defined as (unit -> value) would benefit from have a static run member for instance

Which makes me wonder if all monads shouldn't just inherit from the async monad so they get the run behavior of your choice out of the box.

My head is really spinning now so i best be getting off to bed!

By on 10/9/2008 11:08 PM ()

No implicit type conversions in F# (they would play havoc with type inference).

For some monads (like Async) the (unit -> ...)-and-.Run() style makes a lot of sense, but it isn't clear to me that that is universally true for all monads.

By "inherit", I presume you are speaking metaphorically (subclassing/inheritance from Async would not be appropriate for other monads).

By on 10/10/2008 12:42 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper