CODEWITHSUNDEEP
haskellstate
bbtrb
bbtrb

Reputation: 4085

Creation/Handling of lists of Monad.State's?

I'm just in the process of learning haskell and I am sure that an elegant solution to the following problem exists. Given a function f that returns a stateful computation

f :: (Num a) => a -> a -> State [a] a
f x y = modify ((2*x):) >> return (x+y)   -- state and value are modified based on the passed values

I am looking for the cleanest way to generate multiple State's from a given one recursively (as shown below). One solution I came up with is the following

g :: (Num a) => [a] -> (a, [a]) -> [(a,[a])]
g [] _ = []
g (x:xs) aa@(a,b) = (new : next)
    where new = runState (f x a) b   -- here the old value a is required!
          next = g xs aa

but I guess something like 

g :: [a] -> [State [a] a]

should be possible and cleaner? I didn't succeed trying this and get errors from StateT that I can't figure out.

Thank you!

Background: The code is a simplification of parts of a graph generator I am writing, where the state is the current adjacency vector. For each node, several edges may be created and therefore multiple state is required representing the different (partial) graphs.

Edit: (Try of) A description in words of the above function g x (y, s) in words:

For a given list of values x, a single value y and a state s, compute recursively for each x_i in x a new value and state from (y,s) given by the stateful computation f x_i y and return the result as a list.

Edit 2: Example output:

 g [1,2,3] (4,[2,3,4]) == [(5,[10,2,3,4]),(6,[12,2,3,4]),(7,[14,2,3,4])]

Upvotes: 4

Views: 222

Answers (1)

Peaker
Peaker

Reputation: 2354

Here are some iterative changes to your g function. I hope this is what you were looking for, because I am not sure I fully understand what you tried to achieve:

Your original g:

g :: Num a => [a] -> a -> [a] -> [(a,[a])]
g [] _ _ = []
g (x:xs) a b = new : next
  where
    new = runState (f (h x a)) b   -- here the old value a is required!
    next = g xs a b

Points-free:

g1 :: Num a => [a] -> a -> [a] -> [(a,[a])]
g1 xs a b = map (($ b) . runState . f . (`h` a)) $ xs

Flip for ETA reducability:

g2 :: Num a => [a] -> a -> [a] -> [(a,[a])]
g2 b a = map (($ b) . runState . f . (`h` a))

Without the ($ b) . runState application (no need for the extra [a] argument since we don't apply the State computations):

g3 :: Num a => a -> [a] -> [State [a] a]
g3 a = map (f . (`h` a))

The map there can also be written:

map f . map (`h` a)

and then you can take the

 map (\`h\` a)

part out somewhere else.

This gives you something similar to the type you wanted for g, and of course changes the semantics (as that type is still unapplied to the input state)

Upvotes: 3

Related Questions