HW: Unfolding a list in a specific way

Question

In Programming in Haskell, Graham Hutton defines an unfold for lists as follows:

unfold :: (b -> Bool ) -> (b -> a) -> (b -> b) -> b -> [a]
unfold p h t x | p x = []
| otherwise = h x : unfold p h t (t x)

Define a function

• listUnfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]

that is similar to the one above but uses unfoldr in its implementation and is non-recursive.

I've been trying for a while to solve the question above but I still can manage to do so (pretty new in Haskell and functional programming in general).

My attempt:

listUnfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]
listUnfold f h t x 
    | f x == True   = []
    | otherwise     = h x : 
        listUnfoldr (\x -> if f x then Nothing else Just ((h x), (t x))) x

In english, if f x is true, return the empty list. Otherwise, use h x as the head and append the results of unfoldr as the tail. Unfoldr takes a list (x:xs) should recurse itself with x as the head and xs as the tail.

p/s: I'm probably doing this very very wrongly.

Answer 1

You've almost got it! The original function uses the function p (for 'predicate') to determine whether we've finished unfolding, h to apply to each element, and t (for 'transformation') to transform an element into the seed for the rest of the list.

unfoldr expects a single function f :: b -> Maybe (a,b), which returns Nothing if we've finished unfolding, or Just (x, y), where x is the element to add to the list and y is the seed for the rest of the list.

So f in unfoldr is responsible for the functionality of all three of p, h and t. The Nothing-or-Just dichotomy plays the part of the Boolean function p, and the second element of the tuple does t's job of supplying the seed for the rest of the list.

Here's my solution (I've renamed the variables from your question, for clarity):

listUnfold pred f trans seed =
    unfoldr (\x -> if pred x
                   then Nothing
                   else Just (f x, trans x)) seed

Of course, when a value appears on the right-hand-end of a definition, as seed does here, you can take advantage of Haskell's sexy syntax for currying and throw it away altogether:

listUnfold pred f trans = unfoldr (\x -> if pred x
                                         then Nothing
                                         else Just (f x, trans x))

Formally, this transformation is known as eta reduction.

Answer 2

Here's the definition of unfoldr:

unfoldr                 :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
  case f b of
   Just (a,new_b) -> a : unfoldr f new_b
   Nothing        -> []

And here's Hutton's unfold, rewritten slightly to use case instead of guards:

unfold :: (b -> Bool ) -> (b -> a) -> (b -> b) -> b -> [a]
unfold p h t x =
  case p x of
    True  -> []
    False -> h x : unfold p h t (t x)

Some observations:

• By comparing types, we can see that unfoldr and unfold share the same final argument type and the same result type.
  • b in the definition of unfoldr and x in the definition of unfold are basically the same variable.
  • Hopefully we can also match up the definitions of the two functions so that the results are the same.
• Each function consists of a case expression, with two branches.
• In each function, one of those branches results in [].
  • So when p x = True, we want f x = Nothing.
• In each function, the other branch results in {-something-} : {-recursive-call-}.
  • So when p x = False, we want f x = Just ({-something-}, {-something-else-}).

By now it should be clear that unfold p h t x = unfoldr f x where f = ..., and it's not too difficult to carry on the chain of reasoning and fill in the definition of f.