Unfold returning the last state of the accumulator

Question

The unfold function in Haskell is very handy to create lists. Its definition is:

unfold :: (b -> Maybe (a, b)) -> b -> [a]

But I would like to get the last value of the accumulator used. A possible implementation is:

unfoldRest :: (b -> Maybe (a, b)) -> b -> ([a], b)
unfoldRest fct ini = go fct ini []
  where
    go f s acc =
      case f s of
        Nothing -> (acc, s)
        Just (a, b) -> go f b (acc ++ [a])

But I was wondering if there wasn't a way to do it with existing functions. In the end this:

countDown 0 = Nothing
countDown n = Just (n, n-1)
unfoldRest countDown 10

will return:

([10,9,8,7,6,5,4,3,2,1],0)

Because the iteration stopped when the accumulator value reached 0.

Answer 1

import Data.List

unfoldr' :: (b -> Maybe (a, b)) -> b -> [(a, b)]
unfoldr' f = unfoldr (fmap (\(a, b) -> ((a, b), b)) . f)

will give you all the states of the accumulator. Then you can choose to look at whichever you want, including the last.

Answer 2

This is not much of an answer (Tom Ellis' better covers the "a way to do it with existing functions" part), but it is worth it taking a second look at your original solution. Since you are using (++) to append single elements repeatedly, it takes quadratic time with respect to the length of the generated list. You can avoid that by dropping the helper function and building the list directly with (:):

unfoldRest' :: (b -> Maybe (a, b)) -> b -> ([a], b)
unfoldRest' f s = case f s of
    Nothing -> ([], s)
    Just (a, b) -> (\ ~(xs, y) -> (a : xs, y)) $ unfoldRest' f b

The lazy pattern match (~(xs, y) in the lambda) is important; it allows you to look at the first elements of the list without having to calculate the final state, and therefore to do something useful with infinite lists (in any case, Tom Ellis' solution is better for infinite lists, as you can see the not only the generated values but also state after any arbitrary segment). As Will Ness points out, you may find the right hand side of the Just case more natural to write using a let binding, as in let (xs, y) = unfoldRest' f b in (a : xs, y).

As you tagged the question with "pointfree", it is worth it mentioning that you can reduce quite a lot the amount of points by using maybe and the Control.Arrow combinators:

import Control.Arrow ((***), first, app)

unfoldRest'' f s =
    maybe ([], s) (app . (first . (:) *** unfoldRest'' f)) $ f s

Whether you want to go that far is a matter of taste. The laziness issue is dealt with correctly, as the implementation of (***) for functions uses a lazy pattern match.

Answer 3

I've grappled with this problem before - one of ways to solve it is by using the State monad.

In simple terms, they deal with functions on the form s -> (d, s). Intuitively, s is the type of the state that may change during a computation.

The first thing to note is that s -> Maybe (d, s) doesn't have the form s -> (d, s): the former is a tuple of things, while the latter is a Maybe, we need a function on the type s -> (Maybe d, s), if the function returns None, the modified function will return the previous state. One possible implementation of this adapter is:

keepFailure :: (s -> Maybe (d, s)) -> (s -> (Maybe d, s))
keepFailure f s = maybe (Nothing, s) (first Just) (f s)

Remember to import Data.Bifunctor because of the first function There's a function that converts from s -> (d, s) to State s d called state, and runState to convert it back. Now we implement the function which is will try exhausting the state of all possible values:

stateUnfoldr :: State s (Maybe d) -> State s [d]
stateUnfoldr f = do
  mx <- f
  case mx of
    Just x -> do
      xs <- stateUnfoldr f
      return $ x:xs
    Nothing -> return []

In simple terms, mx <- f works like "apply f to the input, update the state, get assign the return value to mx" Then, we can piece everything together:

fStateUnfoldr :: (s -> Maybe (d, s)) -> (s -> ([d], s))
fStateUnfoldr f = runState $ stateUnfoldr $ state . keepFailure $ f

Remember to import Control.Monad.State

state . keepFailure adapts f into a State s (Maybe d) Monad, then stateUnfoldr unfolds to a State s [d], then runState turns it back to a function.

We can also use the execState or evalState instead of runState if you want just the state or just the list.