On Fri, Jul 30, 2010 at 11:57:00AM -0500, 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).

Could you use State for something like storing the latest two values of a Fibonacci series? For example, each time you call it, it generates the next term, discards the oldest term, and stores the newly-generated term?

Although state can't be used to calculate things that couldn't be calculated otherwise, it can be used to implement things faster (in a real, computer theoretic sense) than they could be otherwise. For instance, the union-find algorithm cannot be implemented efficiently without state, the state monad allows the best of both worlds, a pure interface but the fast algorithm under the hood. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/

Jason Catena wrote:

On Jul 30, 11:17 am, Anton van Straaten wrote:

...

Prelude> :m Control.Monad.State Prelude Control.Monad.State> let addToState :: Int -> State Int (); addToState x = do s <- get; put (s+x) Prelude Control.Monad.State> let mAdd4 = addToState 4 Prelude Control.Monad.State> :t mAdd4 m :: State Int () Prelude Control.Monad.State> let s = execState mAdd4 2 Prelude Control.Monad.State> :t s s :: Int Prelude Control.Monad.State> s 6

By this example State doesn't seem to give you anything more than a closure would

Sure, the example was just intended to show a value being extracted from a monad, which was what was being asked about.

since it doesn't act like much of an accumulator (by, for example, storing 6 as its new internal value).

Actually, in the example, the "put (s+x)" does store 6 as the new value of the state. It's just that the example doesn't do anything with this new state other than extract it using execState. You can use functions like addToState in a larger expression, though. E.g., the following updates the internal state on each step and returns 14: execState (addToState 4 >> addToState 5 >> addToState 3) 2

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

For example, each time you call it, it generates the next term, discards the oldest term, and stores the newly-generated term?

You should really try to implement this as an exercise, in which case don't read any further! * * * (OK, now I've assuaged my guilt about providing answers) Here's the simplest imaginable implementation of your spec (the type alias is purely for readability): type Fib a = State (Integer, Integer) a fibTerm :: Fib Integer fibTerm = do (a,b) <- get put (b,a+b) return a When you run the Fib monad, you provide it with a pair of adjacent Fibonacci numbers such as (0,1), or, say, (55,89). If you only run one of them, all it does is return the first element of the state it's provided with. Chaining a bunch together gives you a Fibonacci computation. For convenience and readability, here's a runner for the Fib monad: runFib :: Fib a -> a runFib = flip evalState (0,1)

And could you then use this Fibonacci State monad in a lazy computation, to grab for example the first twenty even Fibonacci numbers, without computing and storing the series beyond what the filter asks for?

Easily: fibList :: [Integer] fibList = runFib $ sequence (repeat fibTerm) main = print $ take 20 (filter even fibList)

We can generate Fibonacci series double-recursively in a lazy computation. Would it be more or less efficient to use a Fibonacci State monad instead?

If you're thinking of comparing to a non-memoizing implementation, then the Fib monad version is a bajillion times faster, just because it avoids repeated computation. But your mention of "lazy" makes me think you might be referring to a list-based implementation (since laziness doesn't help a naive implementation at all). Using lists is much more efficient since it effectively memoizes. E.g. this: fibs = 0 : 1 : zipWith (+) fibs (tail fibs) ...is faster and more memory efficient than the Fib monad, but not so much that it'd matter for most purposes. Fib's performance could be improved in various ways, too.

Would the State implementation provide a larger range before it blew the stack (which tail-recursion should prevent), or became too slow for impatient people?

The Fib monad performs very well. "fib 50000" takes 1.6 seconds on my machine. The non-memoizing double-recursing version can only get to about fib 27 in the same time, with similar memory usage, but that may not have been what you wanted to compare to.

Would Haskell memoize already-generated values in either case? Could we write a general memoizer across both the recursive and State implementations, or must we write a specific one to each case?

By using a list in fibList above, we get memoization for free. Although it may not be quite what you were asking for, lists in Haskell can be thought of as a kind of general memoizer. Anton