[Haskell-cafe] Re: Re: Can we come out of a monad?

wren ng thornton wren at freegeek.org
Sat Jul 31 00:33:40 EDT 2010

Jason Catena wrote:
> By this example State doesn't seem to give you anything more than a
> closure would, since it doesn't act like much of an accumulator (by,
> for example, storing 6 as its new internal value).

Reader r = (r->)
Writer m = Monoid m => (m,)
State  s = (s->) . (s,)

So, yes, the state monad can "change the internal value".

> Could you use State for something like storing the latest two values
> of a Fibonacci series?

Sure. let s = (Int,Int) and

     fibs = start
         start 0 = 0
         start 1 = 1
         start n = evalState (recurse $! n-2) (0,1)

         recurse n = do
             (x,y) <- get
             let z = x+y
             z `seq` if n==0
                 then return z
                 else do
                     put (y,z)
                     recurse $! n-1

will return the nth Fibonacci number, with memoization, while only 
holding onto the previous two memos.

> Would Haskell memoize already-generated values in either case?

No. Doing so would lead to enormous memory leaks.

> Could
> we write a general memoizer across both the recursive and State
> implementations, or must we write a specific one to each case?

There are a number of generic memoization libraries on Hackage, just 
take a look.

Live well,

More information about the Haskell-Cafe mailing list