Portability | portable |
---|---|
Stability | stable |
Maintainer | wren@community.haskell.org |
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.)
- 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. 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] -> 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). 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.