Data.List.Extras.LazyLength

This module provides least-strict functions for getting a list's length and doing natural things with it.

The regular version of length will traverse the entire spine of the list in order to return an answer. For comparing the length against some bound, that is by far too strict. Being too strict can cause a space leak by expanding a lazy list before necessary (or more than is ever necessary). And it can lead to unnecessarily non-terminating programs when trying to determine if an infinite list is longer or shorter than some finite bound.

A nicer version of length would return some lazy approximation of an answer which retains the proper semantics. An option for doing this is to return Peano integers which can be decremented as much as necessary and no further (i.e. at most one more than the bound). Of course, Peano integers are woefully inefficient. This module provides functions with the same lazy effect but does so efficiently instead.

As of version 0.3.0 the GHC rules to automatically rewrite certain calls to length into our least-strict versions have been removed for more consistent and predictable semantics. All clients should explicitly call these least-strict functions if they want the least-strict behavior.

Documentation

lengthBound :: Int -> (Int -> Int -> a) -> [b] -> a

A variant of length which is least-strict for comparing against a boundary length.

lengthBound is polymorphic in the return of the helper function so we can use compare as well as >, >=, ==, /=, <=, <. If you want to use any other functions, know that we only preserve the ordering of the list's length vs the boundary length and so the function should not rely on the true values of either of the numbers being compared.

lengthCompare :: [a] -> [b] -> Ordering

A variant of length which is least-strict for comparing the lengths of two lists. This is as strict as the length of the shorter list (which allows comparing an infinite list against a finite list).

If you're going to immediately follow this with a zip function then see Data.List.Extras.Pair instead.