Data.List.Extras.LazyLength

This module provides least-strict functions for getting a list's length and doing natural things with it. On GHC this module also uses rewrite rules to convert certain calls to length into our least-strict versions.

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 and would wreck the cache and burn heap. This module provides functions with the same lazy effect as if we used Peano integers, but does so efficiently instead.

(For Peano integers see numbers:Data.Number.Natural or non-negative:Numeric.NonNegative.Class.)

Documentation

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

A variant of length which is least-strict for comparing against a boundary length. This function is defined primarily for use by rewrite rules rather than for direct use (though it's fine for that too).

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). The function itself is trivial, but again it's designed primarily for rewrite rules.

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