# 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 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

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)

return x = Cons x Nil
Nil >>= f = Nil
InC xs >>= f = InC (xs >>= f)
(Cons x xs) >>= f = (f x) `plus` (xs >>= f)

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 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 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)