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.
Pergunta
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
.
Solução
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.
Outras dicas
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.
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.