| Portability | portable |
|---|---|
| Stability | stable |
| Maintainer | wren@community.haskell.org |
Data.List.Extras.LazyLength
Description
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.
- lengthBound :: Int -> (Int -> Int -> a) -> [b] -> a
- lengthCompare :: [a] -> [b] -> Ordering
Documentation
lengthBound :: Int -> (Int -> Int -> a) -> [b] -> aSource
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] -> OrderingSource
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.