[Haskell-beginners] adding state handing to existing code

[Stephen Tetley]

2010/1/25 Scott Thoman <scott at thoman.org>:
> If I were designing something, for a very simple example, like the map
> function but maybe over some custom sequence-like thing, how could I
> make it so that the user-supplied function could be monadic/stateful
> or not?  Is there a way to make the map function flexible enough so
> that the author of the function argument could make it stateful or
> pure without any control over the definition of map itself?

Hi Scott

[Not quite answering your question directly, but...]

There are monadic versions of the usual 'functionals' map fold - mapM,
foldM. etc

If you don't need to consider other monadic effects (eg. exceptions)
and only need state, some of the common higher order functions are
'stateful'. 'unfoldr' is the most obvious one. 'unfoldr' passes a
state though each recursive step. At each step the 'user function'
looks at the state and decides whether to produce both a new value and
a new state or terminate the computation.

foldr, and foldl too can be seen as stateful. One way to think about
folds (on lists) is that they reduce the list to a summary value, the
summary value is effectively state. If you want to have 'user state'
and still produce a summary value you can pass a pair to the fold
partitioning the user state and summary value.

mapAccumL and mapAccumR from Data.List are variations on this theme -
they combine fold and map, passing an accumulating parameter (a.k.a.
the user state) through the list traversal returning both the new list
and the state.

The unfold version of mapAccumL unfortunately isn't in the standard
library, it lets you traverse the list statefully but has the
additional very useful property that you can escape the traversal
before the end of the list. Here's the definition I use:

-- | @unfoldMap@ is the unfold analogue of accumMapL.
-- We can signal exhaustion early by the Maybe type.
unfoldMap  :: (a -> st -> Maybe (b,st)) -> st -> [a] -> ([b],st)
unfoldMap _ s0 []     = ([],s0)
unfoldMap f s0 (x:xs) = case (f x s0) of
    Nothing       -> ([],s0)
    Just (a,st)   -> (a:as,b) where (as,b) = unfoldMap f st xs

Best wishes

Stephen