LazyList — listes possiblement infinies à queues paresseuses et mémoïsées
Synopsis
data LazyList a
= Nil
| a :: Lazy (LazyList a)
Une liste dont la queue n'est évaluée qu'à la demande puis retenue (mémoïsée) : elle peut donc être infinie. Elle partage les constructeurs Nil et :: avec la List stricte du Prélude : le compilateur résout lequel est visé d'après le type, donc la syntaxe de liste ([1, 2, 3]), l'opérateur cons (x :: xs) et le filtrage se lisent exactement comme pour List — seule la queue diffère, en étant paresseuse (Lazy (LazyList a)).
Importez-la qualifiée, p. ex. import Data.LazyList as L, et écrivez L.take, L.repeat, … pour que ces noms ne masquent pas les versions strictes de List.
Nilla liste paresseuse vide
::une tête devant une queue calculée à la demande
repeat : a -> LazyList a
repeat x est la liste infinie x, x, x, ….
iterate : (a -> a) -> a -> LazyList a
iterate f x est x, f x, f (f x), ….
from : Int -> LazyList Int
Les entiers à partir de from n : n, n+1, n+2, ….
fromList : List a -> LazyList a
enumFromTo : Enum a => a -> a -> LazyList a
[lo .. hi] : lo, succ lo, …, hi. enumDist lo hi (unit steps from lo up to hi) is 0 both for [a .. a] and for an empty [b .. a] ; the two are told apart by enumDist hi lo, 0 only when hi == lo.
enumFromToExcl : Ord a => Enum a => a -> a -> LazyList a
[lo .. hi[ (or [lo .. hi)) : up to but EXCLUDING hi ; empty when hi <= lo.
enumFromThenTo : Ord a => Enum a => a -> a -> a -> LazyList a
[a, b .. c] : a, then a step of b - a at a time, while within the bound c (inclusive). Direction from a vs b ; step 0 refused, as for List.
enumFromThenToExcl : Ord a => Enum a => a -> a -> a -> LazyList a
enumFrom : Enum a => a -> LazyList a
[e ..] : the range e, succ e, … with no bound — only a LazyList can hold it. It stops where the TYPE stops (KB-200) : never on Int or Nat, at U+10FFFF on Char.
enumFromThen : Ord a => Enum a => a -> a -> LazyList a
[a, b ..] : the stepped range a, a + (b - a), … with no bound. Step 0 is refused as for List ; the direction is read from a vs b, and the range stops where the type stops — [5, 3 ..] : LazyList Nat is 5, 3, 1 then ends, [10, 8 ..] : LazyList Int never ends.
head : LazyList a -> Maybe a
Le premier élément, s'il existe.
tail : LazyList a -> Maybe (LazyList a)
Tout ce qui suit le premier élément, s'il existe.
take : Nat -> LazyList a -> LazyList a
take n xs est les n premiers éléments, en List stricte (donc finie même quand xs ne l'est pas).
drop : Nat -> LazyList a -> LazyList a
drop n xs écarte les n premiers éléments.
takeWhile : (a -> Bool) -> LazyList a -> LazyList a
Le plus long préfixe dont les éléments satisfont p, en List stricte.
toList : LazyList a -> List a
Force the WHOLE lazy list into a strict List — the explicit conversion (diverges on an infinite list; pair it with take/takeWhile first).
map : (a -> b) -> LazyList a -> LazyList b
Applique f à chaque élément, paresseusement.
filter : (a -> Bool) -> LazyList a -> LazyList a
Garde les éléments satisfaisant p, paresseusement.
append : LazyList a -> LazyList a -> LazyList a
Concatène deux LazyList (la première devrait être finie).
singleton : a -> LazyList a
nil : LazyList a
concatMap : (a -> LazyList b) -> LazyList a -> LazyList b
Transforme chaque élément en une LazyList et concatène les résultats, paresseusement. Les compréhensions de liste [ e | x <- xs, … ] sur une LazyList l'utilisent, donc elles restent paresseuses et peuvent COURT-CIRCUITER : ne consommer que head (ou take 1) du résultat ne force de l'entrée que ce qui est nécessaire pour produire le premier élément.
SÛR POUR LA PILE : sauter un nombre arbitraire d'images vides (la recherche en profondeur d'une [ e | … ] qui court-circuite tardivement) s'exécute en pile O(1) au lieu de déborder.
concat : LazyList (LazyList a) -> LazyList a
Aplatit une LazyList de LazyList, paresseusement (même comportement de court-circuit).
zipWith : (a -> b -> c) -> LazyList a -> LazyList b -> LazyList c
zipWith f xs ys combine les éléments deux à deux, s'arrête à la plus courte.
foldr : (a -> b -> b) -> b -> LazyList a -> b
Repli à droite. Termine sur les listes finies ; sur une liste infinie, il ne termine que si f ignore son second argument assez tôt.
foldrLazy : (a -> Lazy b -> b) -> Lazy b -> LazyList a -> b
Right fold that can stop (the twin of List.foldrLazy, and the LazyList definition of the Foldable method): f receives the fold of the tail suspended (Lazy b), so the fold stops as soon as f does not read it, and terminates on an infinite list; the seed z is read only if the fold reaches the end. foldrLazy (&&) True (repeat False) is False.
any : (a -> Bool) -> LazyList a -> Bool
Is p true of SOME element? Stops at the first hit — any p xs on an infinite xs terminates as soon as a witness appears.
all : (a -> Bool) -> LazyList a -> Bool
Is p true of EVERY element? Stops at the first counter-example.
find : (a -> Bool) -> LazyList a -> Maybe a
The first element satisfying p, if any (stops there).
elem : Eq a => a -> LazyList a -> Bool
Is x an element? Stops at the first occurrence.
length : LazyList a -> Nat
The number of elements, as a Nat — FORCES the whole list (diverges on an infinite one); observe an infinite list through take first.
foldl : (b -> a -> b) -> b -> LazyList a -> b
Repli à gauche. Diverge sur une liste infinie (il doit en atteindre la fin).
isEmpty : LazyList a -> Bool
Is the list empty? Forces only the first cell.
reverse : LazyList a -> LazyList a
The list in reverse order — FORCES the whole list.
dropWhile : (a -> Bool) -> LazyList a -> LazyList a
The remainder after the longest prefix whose elements satisfy p (the companion of takeWhile).
splitAt : Nat -> LazyList a -> (LazyList a, LazyList a)
Split after the first n elements: (take n xs, drop n xs).
index : Nat -> LazyList a -> Maybe a
The element at position n (0-based), or Nothing when out of range.
zip : LazyList a -> LazyList b -> LazyList (a, b)
Pair up elements of two lists, lazily (truncating to the shorter).
zipWith3 : (a -> b -> c -> d) -> LazyList a -> LazyList b -> LazyList c -> LazyList d
Zip three lists with a function, lazily (truncating to the shortest).
replicate : Nat -> a -> LazyList a
sum : Additive a => LazyList a -> a
Sum of the elements (0 for the empty list) — FORCES the whole list.
product : Multiplicative a => LazyList a -> a
Product of the elements (1 for the empty list) — FORCES the whole list.
maximum : Ord a => LazyList a -> Maybe a
Largest element, or Nothing if empty — FORCES the whole list.
minimum : Ord a => LazyList a -> Maybe a
Smallest element, or Nothing if empty — FORCES the whole list.
elemBy : (a -> a -> Bool) -> a -> LazyList a -> Bool
Is an element present, using a supplied equality test? Stops at the first occurrence.
lookup : Eq k => k -> LazyList (k, v) -> Maybe v
Look up a key in an association list (stops at the first match).
mapMaybe : (a -> Maybe b) -> LazyList a -> LazyList b
Apply a partial function to every element, keeping the successes, lazily.
catMaybes : LazyList (Maybe a) -> LazyList a
last' : LazyList a -> Maybe a
The last element, or Nothing if empty — FORCES the whole list.
init' : LazyList a -> Maybe (LazyList a)
All but the last element, or Nothing if empty, lazily.
intersperse : a -> LazyList a -> LazyList a
Insert sep between consecutive elements, lazily.
intercalate : Monoid m => m -> LazyList m -> m
Join monoid values, inserting sep between consecutive elements — FORCES the whole list.
findIndex : (a -> Bool) -> LazyList a -> Maybe Nat
The 0-based index of the first element satisfying the predicate (stops there).
elemIndex : Eq a => a -> LazyList a -> Maybe Nat
The 0-based index of the first occurrence of a value (stops there).
partition : (a -> Bool) -> LazyList a -> (LazyList a, LazyList a)
Split into (elements satisfying p, the rest), each LAZY and in order.
span : (a -> Bool) -> LazyList a -> (LazyList a, LazyList a)
(longest prefix all satisfying p, the remainder) = (takeWhile p xs, dropWhile p xs).
break : (a -> Bool) -> LazyList a -> (LazyList a, LazyList a)
The prefix up to the first element satisfying p, and the rest: break p = span (not . p).
insertOrd : Ord a => a -> LazyList a -> LazyList a
Insert into a sorted list, keeping it sorted (lazily past the insertion).
insertBy : (a -> a -> Ordering) -> a -> LazyList a -> LazyList a
Insert with a supplied comparator, keeping the list sorted.
sort : Ord a => LazyList a -> LazyList a
Sort into ascending order (stable insertion sort) — FORCES the whole list.
sortBy : (a -> a -> Ordering) -> LazyList a -> LazyList a
Sort by a supplied comparator (stable) — FORCES the whole list.
sortOn : Ord b => (a -> b) -> LazyList a -> LazyList a
Sort by a key projection, computing each key once — FORCES the whole list.
nubBy : (a -> a -> Bool) -> LazyList a -> LazyList a
Remove duplicates using a supplied equality, keeping the first occurrence, lazily.
nub : Eq a => LazyList a -> LazyList a
Remove duplicates (by ==), keeping the first occurrence, lazily.
groupBy : (a -> a -> Bool) -> LazyList a -> LazyList (LazyList a)
Group consecutive elements deemed equal by the predicate, lazily.
group : Eq a => LazyList a -> LazyList (LazyList a)
Group consecutive equal elements (by ==), lazily.
scanl : (b -> a -> b) -> b -> LazyList a -> LazyList b
Left scan: the running accumulator after each step, seeded with z, lazily (one longer than the input).
scanr : (a -> b -> b) -> b -> LazyList a -> LazyList b
Right scan (always non-empty) — FORCES the whole list.
unfoldr : (b -> Maybe (a, b)) -> b -> LazyList a
Build a list from a seed, lazily: f returns Just (element, next seed) to emit, or Nothing to stop (it may never stop).
foldl1 : (a -> a -> a) -> LazyList a -> Maybe a
Left fold over a NON-empty list, seeded with its first element; Nothing for the empty list — FORCES the whole list.
foldr1 : (a -> a -> a) -> LazyList a -> Maybe a
Right fold over a NON-empty list; Nothing for the empty list — FORCES the whole list.
tails : LazyList a -> LazyList (LazyList a)
All suffixes, longest first, lazily: tails [1, 2] = [[1, 2], [2], []].
isPrefixOf : Eq a => LazyList a -> LazyList a -> Bool
Is the first list a prefix of the second? Stops at the first difference.
isSuffixOf : Eq a => LazyList a -> LazyList a -> Bool
Is the first list a suffix of the second? FORCES both lists.
isInfixOf : Eq a => LazyList a -> LazyList a -> Bool
Is the first list a contiguous sub-sequence of the second? Stops at the first occurrence.
listToMaybe : LazyList a -> Maybe a
maybeToList : Maybe a -> LazyList a
A Just becomes a one-element list, a Nothing the empty list.
lefts : LazyList (Either a b) -> LazyList a
Keep only the Left values, lazily.
rights : LazyList (Either a b) -> LazyList b
Keep only the Right values, lazily.
partitionEithers : LazyList (Either a b) -> (LazyList a, LazyList b)
Split a list of Eithers into (the Lefts, the Rights), each lazy.
(!) : LazyList a -> Nat -> Maybe a
Safe subscript xs[i]? — Nothing if i is out of range.
index : LazyList a -> Nat -> a
Direct subscript xs[i] — panics if i is out of range.
set : LazyList a -> Nat -> a -> LazyList a
set xs i v — the list with position i set to v (unchanged if i is out of range), lazily.