What about While Loops? Unfolding in Haskell

So far this month, we've been focusing on "for" loops. All of our functions have taken a list as an input and produced either a single value or a list of accumulated values matching the length of the list. But sometimes we actually want to do the opposite! We want to take a single seed value and produce a list of values! This is more in keeping with the behavior of a "while" loop, though it's also possible to do this as a for-loop.

Recall that "fold" is our basic tool for producing a single value from a list. Now when we do the opposite, the concept is calling "unfolding"! The key function here is unfoldr:

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

It takes a single input value and produces a list of items in a resulting type. The function we pass will take our input type and produce a new result value as well as a new input value! This new input value gets passed again to the function on the next iteration. It continues until our function produces Nothing.

unfoldr :: (input -> Maybe (result, input)) -> input -> [result]

Here's a C++ example. Suppose we're trying to produce a binary representation of a number and we're OK with this representation being variable length. Here's how we might do this with a while loop.

enum BitValue { ONE, ZERO };

// This representation is a little odd in that we use an empty list to
// represent '0'
std::vector<BitValue> produceBits(uint64_t input) {
  std::vector result;
  while (input > 0) {
    if (input % 2 == 0) {
      result.push_back(ZERO);
    } else {
      result.push_back(ONE);
    }
    input /= 2;
  }
  std::reverse(result.begin(), result.end());
  return result;
}

So each time through the loop we produce a new bit depending on the "input" value status. Once we hit 0, we're done.

How can we do this in Haskell with unfoldr? Well first let's write a function to do the "unfolding". This follows the same logic that's inside the loop:

produceSingleBit :: Word -> Maybe (Bit, Word)
produceSingleBit 0 = Nothing
produceSingleBit x = if x `mod` 2 == 0
  then Just (Zero, x `quot` 2)
  else Just (One, x `quot` 2)

And now to complete the function, it's a simple application of unfoldr!

produceBits :: Word -> [Bit]
produceBits x = reverse (unfoldr produceSingleBit x)

...

>> produceBits 4
[One, Zero, Zero]
>> produceBits 3
[One, One]
>> produceBits 9
[One, Zero, Zero, One]

We can also implement a fibonacci function using unfold. Our "unfolding" function just needs one of its inputs to act as a counter. We provide this counter and the initial values 0 and 1 as the seed values, and it will keep counting down. This will provide us with the complete list of fibonacci numbers up to the given input index.

fib :: Word -> [Word]
fib x = unfoldr unfoldFib (x, 0, 1)
  where
    unfoldFib (count, a b) = if count == 0
      then Nothing
      else Just (b, (count - 1, b, a + b))

...

>> fib 1
[1]
>> fib 2
[1, 1]
>> fib 5
[1, 1, 2, 3, 5]

It might seem a little unnatural, but there are lots of opportunities to incorporate unfold into your Haskell code! Just keep a lookout for these "while loop" kinds of problems. To stay updated with all the latest on Monday Morning Haskell, make sure to subscribe to our newsletter! You can also follow my streaming schedule on Twitch, which I'll also post on Twitter!