Monad implementation

Google Group
1

I want to define a generic interface to monad and being capable of
implementing all kind of monads without to rewrite generic functions that
are same for all.

I would like to have something equivalent of this in OCAML :

my attempt :

abst@ype monad_t (a: t@ype)

typedef monad (a, b:t@ype) = '{
bind = (monad_t(a), a - monad_t(b)) -> monad_t(b)
, return = (b) -> monad_t(b)
}

typedef monad_ext(a, b: t@ype) = '{
bind = (monad_t(a), a - monad_t(b)) -> monad_t(b)
, return = (b) -> monad_t(b)
, fmap = (a - b, monad_t(a)) - monad_t(b)
, lift = (a - b, monad_t(a)) - monad_t(b)
}

fun{a, b: t@ype} new_ext_monad(mm: monad(a, b)): monad_ext(a, b) = let
fun fmap(f:a - b, m: monad_t(a)): monad_t(b) =
mm.bind(m, lam (x: a): monad_t(b) = mm.return(f x))
in '{
bind = mm.bind
, return = mm.return
, fmap= fmap
, lift = fmap
} end

//MAYBE
assume monad_t(a: t@ype) = Option a

fun{a, b: t@ype} new_maybe_monad(): monad(a, b) =
'{
bind = lam (v: Option a, f: (a - Option b)): Option b =>
case+ v of
| Some x => f x
| None => none()
, return= lam (x: b): Option b => Some x
} where {
fun{a: t@ype} none(): Option a = None
}

fun test_maybe(): void = let
val m = new_ext_monad(new_maybe_monad<int, int>())
infixl (+) >>=
fun >>= (c: Option int, mf: int - Option int): Option
int =
m.bind(c, mf)
val v = m.lift(lam(x: int): int = x+3, m.return(2)) >>=
(lam(x: int): Option int = m.return(x*2))
in
case+ v of
| Some x => printf(“value is %i\n”, @(x))
| None => ()
end

It is working for this simple monad but if I try to implement the state
monad of the ocaml example I cannot figure out how to implement the monad
interface due to the additionnal b type of state I presume:

typedef state_t (a:t@ype, b:t@ype) = b - (a, b)

assume monad_t(a: t@ype) = [b:t@ype] state_t(a, b)

fun{a, b, c: t@ype}
new_state_monad(): monad(a,b) = ‘{
bind= lam (m: state_t(a, c)(* HERE first error *), f: (a -
state_t(b, c))): state_t(b, c) => l where {
fun l(s:c): (b, c) = let
val (x, s’) = m s
val m’ = f x
in m’ s’ end
}
, return= lam(x: a): state_t(a,b) => lam (s:b): (a,b) = @(x, s)
}

I have many errors :
mismatch of static terms (tyleq):
The needed term is: S2Efun(clo(-1); 0; 0; S2Evar(c(2591)); S2Etyrec(flt; 0;
0=S2Evar(a(2589)), 1=S2Evar(c(2591))))
The actual term is: S2Eexi(b$34(2592); ; S2Eapp(S2Ecst(state_t);
S2Evar(a(2589)), S2Evar(b$34(2592))))
…

Any advice ?

thanks a lot
cyrille

2

Usually. following a C++ implementation is the right way to go.

By the way, I made monad_maybe and monad_list avaiable in ATS2:

http://www.ats-lang.org/LIBRARY/#ATSLIB_libats_ML

I have to say that monads are fun to play with.

Cheers,

–Hongwei

3

mm for sure the state monad is uneeded in ATS but I am looking towards
Functional Reactive Programming and I actually use a continuation monad
around my purely functional 3D engine.

Maybe we can find a better way for implementing FRP in ATS :wink:

4

FRP is very cool.

At one time, I thought about implementing it in ATS but never had time to
carry it out.
I think linear types can play a very important role in implementing FRP. Is
there an implementation
of FRP in OCaml?

5

Here is an encoding of state-monad in ATS2:

This kind of programming seems very inefficient (unless there is some
special compilation
support). More importantly, it is not so clear whether there is a genuine
need for monads in ATS.
For instance, the examples given in the following tutorial can be readily
handled in ATS with the
support of templates:

6

I don’t know much about Ocaml. I have just seen this framework but never
played with : https://github.com/jaked/froc (it is a kind of imperative
implementation with a dataflow graph very similar to frtime in racket http://docs.racket-lang.org/frtime/
)

I have studied Haskell implementations and Microsoft one ( Rx framework :
https://rx.codeplex.com/ )
My current FRP implementation is event-push FRP with the rx semantic based
on a continuation monad

I want to experiment event-pull FRP based on haskell Arrows (
http://www.haskell.org/haskellwiki/Netwire and
http://www.haskell.org/haskellwiki/Yampa )
I have made some little experiments in javascript but now I want to play
with my 3D engine.

I begin to see the monad stuff is a bit heavyweight for language other than
haskell, maybe should be more reasonable to implement FRP in ATS with
something more similar to C++ attempts :
http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.158.8191

7

I ported your code to ATS2:

Your style is too ocaml-ish :slight_smile:

8

thanks for the suggestion of style.
I will try out my examples tomorrow :wink: