Infinite Data Structures:



first100Ints = [1 .. 100]
allIntegers = [1 ..]
--defining infinite lists in instantaenous because it doesnt involve evaluation
--you can even use subsets of infinite lists and thats fine
--you can also try to print an infinite list but obviously that will never terminate.

--numbering characters in a string
numberChars :: String -> [(Int, Char)]
numberChars s = zip [1 .. n] s
    where
        n = length s
-- with infinite data structs:
numberChars :: String -> [(Int, Char)]
numberChars s = zip [1 ..] s


The list of all fibonacci numbers:
infinite data structures can refer to themselves:

fibonaccis:: [Integer]
fibonaccis = 0 : 1 : zipWith ( + ) (tail fibonaccis) fibonaccis


Because of lazy evaluation, we dont need to know the entire list of fibonacci numbers. We can take the expression (unevealuated) and pass it to a function that calculates fibonacci numbers.

Asking for the first or second is explicit, either 0 or 1.
In order to figure out the third entry in the list is, you need to figure out the head of the second expression.
ZipWith is essentially ‘map’ generalized to two lists.
zipWith f [x,1,x2,...] [y1, y2,...]
= [fx1y1, fx2y2,...]
Take the list of fibonacci numbers, and the list of fibos minus its head, to get the list of fibonaccis.

tail fibonaccis: 1 1 2
fibonaccis: 0 1 1 2
fibonaccis: 0 1 1 2

If not for lazy eval, we would have to fully evaluate fibonaccis, in order to use it recursively in fibonaccis.

x = x+1
-- no error, it has not been evaluated at all yet.
-- printing it would cause an error, since x can't be evaluated.


fibonacciWrong = 0 : 1 : zipWith (+) fibonacciWrong fibonacciWrong
--no error until you try to evaluate something:
take 100 fibonacciWrong
[0, 1, 0, 2, 0 ,4 ,0, powers of 2...]
fibonacciWrong = zipWith (+) fibonacciWrong fibonacciWrong
--infinite loop, never prints anything.


Lazy evaluation can make dynamic programming extremely elegant.
















Index