Roman Cheplyaka

How to force a list

May 28, 2015

Let’s say you need to force (evaluate) a lazy Haskell list.

A long time ago, this was a common way to fight lazy I/O: you read a String and then force it. These days you can have normal I/O with strict Text or ByteString instead.

Anyway, let’s say you do need to force a list. This came up in a pull request for lexer-applicative. Another scenario is if you want to evaluate a lazy Text or ByteString without copying the chunks. Or, you know, for any other reason.

First of all, how exactly do you want to force it? There are two primary ways: force the spine or force the elements too. (You can’t force the elements without forcing the spine.)

Forcing the spine means forcing all cons cells without touching the elements. One way to do that is to evaluate the length of the list, but that feels ad-hoc because it computes the result that is not needed. Here’s an elegant way to walk the spine:

forceSpine :: [a] -> ()
forceSpine = foldr (const id) ()

(Obviously, you need to force the resulting () value, by calling evaluate or seq-ing it to something else, for any evaluation to take place.)

const id, also known as flip const, returns its second argument while ignoring the first. So the evaluation goes like this:

forceSpine [x1, x2]
= foldr (const id) () [x1, x2]
= (const id) x1 $ foldr (const id) () [x2]
= foldr (const id) () [x2]
= (const id) x2 $ foldr (const id) () []
= foldr (const id) () []
= ()

See how forceSpine “unpacks” the list (thus forcing the spine) and throws all elements away.

I mentioned that you may also want to force the elements of the list, too. Most of the time you want to deep-force them, and so you should just rnf the whole list. Even when the elements are atomic (like Char or Int), evaluating them to weak head normal form is still equivalent to rnf.

But occasionally you do want to shallow-force the elements. In that case, simply replace const id with seq in the definition of forceSpine to obtain forceElements:

forceElements :: [a] -> ()
forceElements = foldr seq ()

Again, looking at the evaluation chain helps to understand what’s going on:

forceElements [x1, x2]
= foldr seq () [x1, x2]
= seq x1 $ foldr seq () [x2]
= foldr seq () [x2]
= seq x2 $ foldr seq () []
= foldr seq () []
= ()

Same as before, only elements get forced before being thrown away.

And here’s a table that may help you understand better the difference between seq, forceSpine, forceElements and rnf:

list `seq` () forceSpine forceElements rnf
[Just True] () () () ()
[Just undefined] () () () undefined
[undefined] () () undefined undefined
True : undefined () undefined undefined undefined
undefined undefined undefined undefined undefined

Since forceSpine and forceElements are based on foldr, they can be trivially generalized to any Foldable container, with the caveat that you should understand how the container and its Foldable instance work. For example, forceSpine is useless for Data.Map.Map, since it is already spine-strict, and forceElements for a tuple will only force its second element.