How do I write a constant-space length function in Haskell?

Question

The canonical implementation of `length :: [a] -> Int` is: ``` length [] = 0 length (x:xs) = 1 + length xs ``` which is very beautiful but suffers from stack overflow as it uses linear space. The tail-recursive version: ``` length xs = length' xs 0 where length' [] n = n length' (x:xs) n = length xs (n + 1) ``` doesn't suffer from this problem, but I don't understand how this can run in constant space in a lazy language. Isn't the runtime accumulating numerous `(n + 1)` thunks as it moves through the list? Shouldn't this function Haskell to consume O(n) space and lead to stack overflow? (if it matters, I'm using GHC)

Accepted Answer

Yes, you've run into a common pitfall with accumulating parameters. The usual cure is to force strict evaluation on the accumulating parameter; for this purpose I like the strict application operator `$!`. If you don't force strictness, GHC's optimizer might decide it's OK for this function to be strict, but it might not. Definitely it's not a thing to rely on—sometimes you want an accumulating parameter to be evaluated lazily and O(N) space is just fine, thank you.

As noted above, use the strict application operator to force evaluation of the accumulating parameter:

```
clength xs = length' xs 0
  where length' []     n = n
        length' (x:xs) n = length' xs $! (n + 1)
```

The type of `$!` is `(a -> b) -> a -> b`, and it forces the evaluation of the `a` before applying the function.

How do I write a constant-space length function in Haskell?

Solution

Problem