Lazy evaluation is evaluation by need: an expression is deferred until its value is demanded, and its computed value is shared for subsequent demands of the same suspended computation.
Its two key properties here are avoiding evaluation of unused expressions and sharing demanded computations. For example, the first component of
(3, undefined) can be obtained without evaluating the second. A suspended expression is represented by a thunk; after evaluation its result can be reused. This supports productive infinite lists: take 5 [0..] demands only a finite prefix. It does not guarantee that a demanded computation terminates.Enumerate finite shells of constant coordinate sum:Here natural numbers include zero. Every generated coordinate is nonnegative. Conversely, a given triple occurs in exactly the shell and at exactly those loop indices . Each shell contains only finitely many triples, so every triple is reached after finitely many earlier outputs. This is fair enumeration, unlike nesting three unrestricted infinite lists. For the positive-integer convention, add one to each generated coordinate.
triples :: [(Integer, Integer, Integer)]
triples =
[(a, b, k-a-b) |
k <- [0..],
a <- [0..k],
b <- [0..k-a]]For the requested On its intended input,
Int-typed operation, remove the first element as well as its later multiples:sieve :: [Int] -> [Int]
sieve [] = []
sieve (p:xs) = [x | x <- xs, x `rem` p /= 0]p is positive, so the remainder is defined. An arbitrary list headed by zero lies outside this convention.To enumerate literally all prime numbers, use unbounded At each stage, the smallest remaining number has no smaller prime divisor and is therefore prime. Removing its larger multiples preserves every later prime and removes any composite number once its least prime divisor is processed. Lazy evaluation makes each requested finite prefix available. This implements the given repeated-filtering form of the sieve of Eratosthenes. A bounded
Integer arithmetic:primes :: [Integer]
primes = go [2..]
where
go :: [Integer] -> [Integer]
go [] = []
go (p:xs) =
p : go [x | x <- xs, x `rem` p /= 0]Int stream can only cover representable values; Integer supplies the all-primes interpretation.Enumerate by the hypotenuse and test finitely many shorter legs:The equality selects Pythagorean triples, and the greatest common divisor test makes them primitive. The bounds enforce , removing the duplicate obtained by exchanging the legs. Each fixed has a finite search, so the outer loop gives ascending hypotenuse order and reaches every qualifying triple. Infinite families supplied by Euclid's formula ensure that the stream has arbitrarily many outputs. Its first five entries areUsing
primitiveTriples :: [(Integer, Integer, Integer)]
primitiveTriples =
[(a, b, c) |
c <- [1..],
b <- [1..c-1],
a <- [1..b-1],
a*a + b*b == c*c,
gcd a (gcd b c) == 1][(3,4,5),(5,12,13),(8,15,17),(7,24,25),(20,21,29)]Integer avoids overflow in the squared values. The construction prioritizes a direct correctness argument; it does not claim an optimal enumeration cost. Articles by others on the same topic
There are currently no matching articles.