non-deterministic monad of streams easier in Ocaml?

Submitted by metaperl on Tue, 04/18/2006 - 7:13am.
::

I was reading Cale Gibbard's Monads as Containers and thought "now this is what I learned Haskell for" and then I began to wonder about Ocaml and monads, which led me to google which led me to this post on non-deterministic monad of streams which the author says "cannot be (naively) done in either Prolog or in Haskell's
|MonadPlus monad, both of which would go into an infinite loop on this example."

I'm going to have to talk to
Submitted by Cale Gibbard on Tue, 04/18/2006 - 2:00pm.
I'm going to have to talk to Jacques. :) His code translates basically directly into Haskell. He probably meant the list monad in particular (where one doesn't have InC, so this sort of thing does of course go into an infinite loop). 
module Stream (Stream (..), toStream, runStream) where
 
import Control.Monad

data Stream a = Nil | Cons a (Stream a) | InC (Stream a)

plus :: Stream a -> Stream a -> Stream a
plus Nil bs = bs
plus (InC as) Nil = InC as
plus (InC as) (InC bs) = InC (plus as bs)
plus (InC as) (Cons b bs) = Cons b (plus as bs)
plus (Cons a as) bs = Cons a (plus bs as)

instance Monad Stream where
    return x = Cons x Nil 
    Nil >>= f = Nil
    InC xs >>= f = InC (xs >>= f)
    (Cons x xs) >>= f = (f x) `plus` (xs >>= f)

instance MonadPlus Stream where
    mzero = Nil
    mplus = plus

toStream = foldr Cons Nil

runStream 0 xs = []
runStream n Nil = []
runStream n (InC as) = runStream n as
runStream n (Cons a as) = a : runStream (n-1) as

numb = InC (mplus (return 0) (do n <- numb; return (n+1)))

tst = do i <- numb
         guard (i > 0)
         j <- numb
         guard (j > 0)
         k <- numb
         guard (k > 0)
         let test x = x^2 == j^2 + k^2
         guard (test i)
         return (i,j,k)

main = print (runStream 7 tst)
In Haskell of course, we
Submitted by Cale Gibbard on Tue, 04/18/2006 - 2:26pm.

In Haskell of course, we have laziness, so we can write runStream without the somewhat pointless length parameter. (Composition with take would handle that)

runStream Nil = []
runStream (InC as) = runStream as
runStream (Cons a as) = a : runStream as

We can also make Stream a Functor:

instance Functor Stream where
    fmap f Nil = Nil
    fmap f (InC as) = InC (fmap f as)
    fmap f (Cons a as) = Cons (f a) (fmap f as)

Which lets us define numb as:

numb = InC $ return 0 `mplus` fmap (+1) numb
Oh, almost forgot, you're
Submitted by Cale Gibbard on Tue, 04/18/2006 - 2:32pm.

Oh, almost forgot, you're also allowed to use the mplus from the MonadPlus instance in the instance for Monad, so we can delete plus, and get rid of the distinction:

instance Monad Stream where
    return x = Cons x Nil 
    Nil >>= f = Nil
    InC xs >>= f = InC (xs >>= f)
    (Cons x xs) >>= f = (f x) `mplus` (xs >>= f)

instance MonadPlus Stream where
    mzero = Nil
    mplus Nil bs = bs
    mplus (InC as) Nil = InC as
    mplus (InC as) (InC bs) = InC (mplus as bs)
    mplus (InC as) (Cons b bs) = Cons b (mplus as bs)
    mplus (Cons a as) bs = Cons a (mplus bs as)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.