How to do stateful list operations in haskell

Question

I need an operation which iterates over a list and produces a new list, where the new list elements depend on all elements previously seen. To do this I would like to pass an accumulator/state from iteration to iteration.

Think for example of a list of tuples, where the components of a tuple can be "undefined". An undefined value shall assume the latest value of the same component earlier in the list, if any. So at any stage I will have a state of defined components, which I need to pass to the next iteration.

So with a list of type [l] and an accumulator/state of type a there will be a function of type

f :: a -> l -> (a,l)

i.e it spits out a new list element and a new accumulator.

Is there a function which allows simply applying f to a list? I looked at fold, scan and unfold, but none of them seem to do the trick.

Edit: While the state monad looks promising, I can only see how I would get the final state, but I fail to see how I would get the new list elements.

Answer 1

There are some standard functions you can use to do what you ask.

It sounds very much like you want mapAccum, so you just need to import Data.List and decide which way round you're accumulating. (I suspect you want mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]).)

mapAccumL

import Data.List

data Instruction = NoChange | Reset | MoveBy Int

tell :: Int -> Instruction -> (Int,String) -- toy accumulating function
tell n NoChange = (n,"")
tell n Reset = (0,"Reset to zero")
tell n (MoveBy i) = (n+i,"Add "++show i++" to get "++ show (n+i))

which would give

ghci> mapAccumL tell 10 [MoveBy 5, MoveBy 3, NoChange, Reset, MoveBy 7]
(7,["Add 5 to get 15","Add 3 to get 18","","Reset to zero","Add 7 to get 7"])

scanL

But maybe you don't need to use the full power of mapAccum because sometimes the accumulator is what you want in the new list, so scanl :: (a -> b -> a) -> a -> [b] -> [a] will do the trick

act :: Int -> Instruction -> Int
act n NoChange = n
act n Reset = 0
act n (MoveBy i) = n+i

like this:

ghci> scanl act 10 [MoveBy 5, MoveBy 3, NoChange, Reset, MoveBy 7]
[10,15,18,18,0,7]

Definition for mapAccum

Anyway, here's how mapAccumL and mapAccumR are described in Data.List:

mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumL _ state []        =  (state, [])
mapAccumL f state (x:xs)    =  (finalstate,y:ys)
                           where (nextstate, y ) = f state x
                                 (finalstate,ys) = mapAccumL f nextstate xs

The mapAccumL function behaves like a combination of map and foldl; it applies a function to each element of a list, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new list.

mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumR _ state []        =  (state, [])
mapAccumR f state (x:xs)    =  (finalstate, y:ys)
                           where (finalstate,y ) = f nextstate x
                                 (nextstate, ys) = mapAccumR f state xs

The mapAccumR function behaves like a combination of map and foldr; it applies a function to each element of a list, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new list.

Answer 2

You want mapM in conjunction with the State monad where your accumulator a will be the State. First, to see why you need State, just take your type signature and flip the order of arguments and results:

import Data.Tuple

f :: a -> l -> (a, l)

uncurry f :: (a, l) -> (a, l)

swap . uncurry f . swap :: (l, a) -> (l, a)

curry (swap . uncurry f . swap) :: l -> a -> (l, a)

Or you could just define f to already have the arguments and results in the right order, whichever you prefer. I will call this swapped function f':

f' :: l -> a -> (l, a)

Now lets add an extra set of parentheses around the right half of the type signature of f':

f' :: l -> (a -> (l, a))

That part grouped in parentheses is a State computation where the state is a and the result is l. So I will go ahead and convert it to the State type using the state function from Control.Monad.Trans.State:

state :: (a -> (l, a)) -> State a l

So the converted f' would look like this:

f'' :: l -> State a l
f'' = state . f'

However, the function you really want in the end is something of type:

final :: [l] -> a -> ([l], a)

-- which is really just:
state . final :: [l] -> State a [l]

So that means that I need some function that takes a l -> State a l and converts it to a [l] -> State a [l]. This is precisely what mapM does, except that mapM works for any Monad, not just State:

mapM :: (Monad m) => (a -> m b) -> ([a] -> m [b])

Notice how if we replace m with State a, and set a and b to l, then it has exactly the right type:

mapM :: (l -> State a l) -> ([l] -> State a [l])

f''' :: [l] -> State a [l]
f''' = mapM f''

Now we can unwrap the State using runState to get back a list-threading function of the appropriate type:

final :: [l] -> a -> ([l], a)
final = runState . f'''

So if we combine all those steps into one we get:

final = runState . mapM (state . f')

... where f' is your function written to swap the order of arguments and results. If you choose not to modify your original function then the solution is slightly more verbose:

final = runState . mapM (state . uncurry (swap . curry f . swap))