Back to Questions
5.0k
views4
comments
Haskell Functor and Monad in F#?
f#haskellmonad

Hi,

Any ideas how to use generic functions of the form foo<'a,'b>():'a<'b>?

I have been playing with runtime "typeclasses" in F#, and here is some difficulty in the type system. Namely, when translating Haskell Functor and Monad type classes, I ended up parametrizing by many more types than in Haskell becuase I can't figure out how to define the constraints. Here is what I got:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(* Haskell: class Functor f where fmap :: (a -> b) -> f a -> f b *)
type Functor<'a,'b,'f_a,'f_b> =
    {
      fmap : ('a -> 'b) -> ('f_a -> 'f_b)
    }
  
(* Haskell:
class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a
*)

type Monad<'a,'m_a,'m_b> = 
    interface
        abstract member Bind<'m_a,'a,'m_b> : 'm_a -> ('a -> 'm_b) -> 'm_b
        abstract member Return<'a,'m_a>    : 'a -> 'm_a
    end

As you see this is quite verbose, and sometimes requires an extra type annotation to use. Any workaround?

And just a note - surprisingly, for some examples there are fewer type annotations than one would expect, for instance the following invariant holds for me:

1
2
3
4

[(1,1.);(1,2.);(1,3.);(2,1.);(2,2.);(2,3.);(3,1.);(3,2.);(3,3.)] = 
  ([1; 2; 3]    >>= fun x ->
   [1.; 2.; 3.] >>= fun y ->
   Return<int*double,_>(x, y))
.

Hi,
When it comes to defining a generic map that works for all monads, I found that statically resolved typed parameters seems to be the best choice:

1
2
3
4

let inline fMap b f m =         
    let unit x    = (^x: (member Return: ^b -> ^n) b, x)    
    let (>>=) m f = (^x: (member Bind: ^m -> (^a -> ^n) -> ^n) b, m, f)
    m >>= (fun x -> unit (f x))

Cheers,
HoloEd

By on 3/30/2010 7:54 AM ()

Hi Anton,

F# (or the CLR) does not support the abstraction over type constructors that you need. Sometimes you can get around this using interfaces and subtyping but in my experience not often.

For defining monads, you should look at computation expressions, which are F#'s monads.

Note however, that the limitations you've run into apply equally well to computation expressions. For example, there's currenty no way in F# to write a generic monadic sequence, as in Haskell.

Kurt

By on 11/24/2008 4:54 AM ()

Thanks Kurt for a prompt reply.

I'm aware of computational expressions but to me they look more like a syntactic feature, while I was looking for a type system feature, as I was building something of a typeclass library (typeclasses modulo typechecking).

So there is no systematic way to reduce such code with abstract type constructors to code with interfaces and subtyping? Pity.

But surely, even without generic constructors, one can write generic code in the way I did above, only now it becomes the programmer's responsibility to maintain a lot of dependencies in the type parameters like 'm_a = 'm<'a> and so on.

By on 11/24/2008 5:06 AM ()

You're right - computation expressions are primarily a syntactic feature in F#, not a first class abstraction like in Haskell.

>>>

So there is no systematic way to reduce such code with abstract type constructors to code with interfaces and subtyping?

<<<

Not that I know of, I would certainly be interested to see that.

(only tangentialy related) Incidentally, I did find this paper: [link:research.microsoft.com]

which shows a way to encode GADTs using OO concepts, but I haven't had the time to really look at it yet.

>>>

But surely, even without generic constructors, one can write generic code in the way I did above, only now it becomes the programmer's responsibility to maintain a lot of dependencies in the type parameters like 'm_a = 'm<'a> and so on.

<<<

Sure, but I guess it would become quite tedious to use and write. I don't think it would take long before you start thinking about code generation and the like.

Kurt

By on 11/25/2008 1:17 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