Haskell: iteration is able, how to force the behavior I want?

Question

This is my first post on SO, and I'm relatively new to Haskell, so please excuse any errors or my code is not idiomatic!

Consider the following two intuitive descriptions: a, f (a), f (f (a)) ...

a. a list containing: a, application f for a, application f for , which , application f for , which ...

B. The list containing the i-th position, I have n attachments f to.

My problem is that I burned out trying to use the iterate function in Haskell to execute A. My real application is a simulation, but the following contrived example highlights this problem.

 import Control.Monad.State example :: State Int [[String]] step :: [String] -> State Int [String] step l = do currentState <- get let result = if (currentState == 1) then "foo":l else "bar":l put (currentState + 1) return result example = do sequence $ take 3 . iterate (>>= step) $ return [] 

With these definitions

 evalState example 1 

leads to:

 [[],["foo"],["bar","bar"]] 

Clearly iterate does B, not A! Since the step function only ever adds something to the input list, step ["foo"] cannot produce ["bar", "bar"] , regardless of state!

Let me say that I really understand what is happening here, and also that - formally - the result is exactly “as it should be”: step is a state function, so when f (a) an estimate appears as part of f (f (a )), it will be recounted, and will not be taken from the second element of the list, because the state has changed. I also understand that I could avoid this in my real application by putting my accumulated list inside a state.

However, there are two reasons for posting this post.

First of all, the fact is that iterate often explained in a way that can potentially mislead a novice to think that he does A when he actually does B. This includes Learn You A Haskell (which I found incredibly useful), but also post SO ( here and here , for example). In fact, the verbal explanation of iterate in LYAHFGG is almost exactly the definition of A above. Thus, it would be useful to have a message about this, which would be a resource for other Haskell newcomers who get an error because of this and seek an explanation (therefore, by all means, send more accurate, technical, improved wordings, explanations the difference between A and B below).

Secondly, I will still be interested in whether there is a function that actually makes A! In other words, how can I, in the above state example, make a list (with a slight misuse of the notation): [a, b = f (a), f (b), ...]? In other words, given

 example2 = do firstResult <- step [] secondResult <- step firstResult return $ [[], firstResult, secondResult] 

for which

 evalState example2 1 

gives the desired result

 [[],["foo"],["bar","foo"]] 

How to rewrite example2 using iterate ?

A related question has been posted on the Haskell starter list regarding the memoizing version of iterate . However, this request did not seem to receive a response.

I'm not quite sure that laziness is indeed a problem in my application. Will a strict version of iterate do what I want? My own, naive, “strict iteration”, as shown below, makes no difference.

 iterate' fx = x : rest where previous = fx rest = previous `seq` iterate f previous 

Any ideas on all of these would be greatly appreciated!

Answer 1

There is no difference between A. and B., it is the same in referential transparency.
The essence of the problem is that you interpret them in the context of performing stateful calculations. In this context, the analogue of A that you expect is A: Create a list of results: 1. put the result of the initial calculation in the list, 2. determine the next calculation from the previous result, execute it and add its result to the list, 3. goto 2.
The analogue of B is B ': Perform a list of calculations (by iteration (→ = step)) and from this list of results by performing calculations one by one.
For stateless calculations, or when you pass the same initial state to all the calculations performed in B ', the only difference is efficiency, but if you use sequence , each calculation starts with a different state, so you get different results from' . Destroying your example , we have

 actionList = take 3 $ iterate (>>= step) (return []) = [return [], return [] >>= step, return [] >>= step >>= step] 

list of actions (or monadic values) in State Int [String] . Now when you apply sequence to it,

 example = sequence actionList 

you get an action that, when executed, launches the first of these actions with the initial state, the second with the state that is updated first, and the third with the state updated by the second. To get the behavior you expect, all of them must start with the same initial state.

In principle, a value of type State sv is a function of type s -> (v, s) . iterate creates a list of functions, and sequence applies these functions by supplying them various arguments s (each of them receives the s created by the previous one).

To get the desired behavior, we must introduce a new combinator. Very nice, but can only be used in a few Monads.

 iterateM :: Monad m => (a -> ma) -> ma -> m [a] iterateM step start = do first <- start rest <- iterateM step (step first) return (first:rest) 

What produces

 Prelude Control.Monad Control.Monad.State> evalState (fmap (take 4) (iterateM step (return []))) 1 [[],["foo"],["bar","foo"],["bar","bar","foo"]] 

But it works only in monads with a rather lazy one (>>=) , Control.Monad.State.Lazy is one of the few, Control.Monad.State.Strict is not. And even with CMSLazy , you cannot use the state after iterateM , before continuing with the calculation, you must put to create a new state. To get something that can be used with other monads, we could add the count parameter,

 iterCountM :: (Monad m) => Int -> (a -> ma) -> ma -> m [a] iterCountM 0 _ _ = return [] iterCountM k step start = do first <- start rest <- iterCountM (k-1) step (step fisrt) return (first:rest) 

therefore, we lose flexibility, but get usability in most monads.

Answer 2

This may not answer your question, but what you are doing is very similar to unfoldr .

 step (seed, l) = Just (l', (seed', l')) where seed' = succ seed l' = (if seed == 1 then "foo" else "bar"):l 

---

 ghci> take 3 $ unfoldr step (1, []) [["foo"], ["bar", "foo"], ["bar", "bar", "foo"]] 

No monads are needed. I kind of pounded in the dark, since you didn’t indicate what you were really trying to do, but regardless of whether I received the step correctly, the exit message is something that unfoldr can be used to simply stream state, too.

 unfoldr :: (seed -> Maybe (val, seed)) -> seed -> [val]