How to write my version of unfoldr in a better / more idiomatic manner in Haskell?

Question

I'm trying to write my version of unfoldr in order to solve a chapter exercise from Haskell Book (Chapter 12, Signaling Adversity). The book says:

Write the function myUnfoldr using direct recursion. Compare with the built-in unfoldr to check your implementation. Again, don’t look at implementations of unfoldr so that you figure it out yourself.

And gives the following:

myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a] 
myUnfoldr = undefined

My initial attempt for myUnfoldr has been to write it using a single helper function:

maybeToList :: Maybe a -> [a]
maybeToList (Just x) = [x]
maybeToList Nothing = []

myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a]
myUnfoldr f x = (fst $ head $ maybeToList (f x)) :
  myUnfoldr f (snd $ head $ maybeToList (f x))

This type checks, and for a few example runs it seems like I've achieved what unfoldr does, because:

λ> take 10 $ unfoldr (\x -> Just (x, x + 1)) 0
[0,1,2,3,4,5,6,7,8,9]

and the same result with myUnfoldr:

λ> take 10 $ myUnfoldr (\x -> Just (x, x + 1)) 0
[0,1,2,3,4,5,6,7,8,9]

But of course, myUnfoldr is problematic because if I try the following:

λ> take 10 $ myUnfoldr (\x -> Nothing) 0
[*** Exception: Prelude.head: empty list

whereas unfoldr works as expected, returning [].

I can see why my unFoldr is problematic, but I couldn't find out how to handle the situation where f can return Nothing.

So my second take at the problem is to use another helper function, and this time use guards:

isJust :: Maybe a -> Bool
isJust (Just _) = True
isJust _      = False

myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a]
myUnfoldr f x | isJust $ (f x) = (fst $ head $ maybeToList (f x)) : myUnfoldr f (snd $ head $ maybeToList (f x))
              | otherwise = []

This second version seems to work as expected both for take 10 $ myUnfoldr (\x -> Just (x, x+1)) 0 and take 10 $ myUnfoldr (\x -> Nothing) 0

But I'm still not comfortable with my solution.

Any ideas whether it can be written in a more concise form, without using a helper function? Or in a more idiomatic way?

Answer 1

Two words: pattern matching. You're using $ head $ maybeToList (f x) twice to get both the next state as well as the list element. However, we can pattern match on f x to get whether we're having Just another element (and a state to continue our little unfolding) or whether we're done:

myUnfoldr :: (s -> Maybe (a, s)) -> s -> [a]
myUnfoldr f x = case f x of
    Just (next, state) -> next : myUnfoldr f state
    Nothing            -> []

The problem with your variant is that you don't use isJust (f x) to your advantage. Instead of checking whether something is Just and then getting the values out of it, just check whether the pattern matches.

Note that this is also possible with pattern guards:

myUnfoldr :: (s -> Maybe (a, s)) -> s -> [a]
myUnfoldr f x
  | Just (next, state) <- f x = next : myUnfoldr f state
  | otherwise                 = []

I haven't read the book yet, but I guess that both techniques have been told by chapter 12.