Can an endless list still be used?
Recursion means a function calls itself on a smaller problem. Lazy evaluation means Haskell works out a value only when something needs it.
Together they let you use a list with no end, such as all the whole numbers, by taking only the part you want. In this lesson you count down, raise a number to a power and take values from an endless list.
By the end of this lesson
Note
I can write a recursive function and say why an infinite list can still be used.
Key words
| Word | What it means | Example |
|---|---|---|
| Recursion | a function that calls itself on a smaller problem | |
| Base case | the input where the function stops calling itself | |
| Lazy evaluation | working out a value only when it is needed | |
| Infinite list | a list with no end, such as all the whole numbers | [1 ..] |
| Generator | a Python function that gives one value at a time, when asked |
The cells students fill in are left blank in this preview.
A recursive function solves a smaller problem
To count down from 3, say 3, then count down from 2. To count down from 2, say 2, then count down from 1. The job gets smaller each time until it reaches 0, where you stop.
The stopping point is the base case. Every recursive function needs one, or it never ends.
The recursion file: countdown and power
countdown :: Int -> [Int]
countdown 0 = []
countdown n = n : countdown (n - 1)
power :: Int -> Int -> Int
power _ 0 = 1
power base n = base * power base (n - 1)
Save the recursion file
docker exec haskell sh -c "printf '%s\n' 'countdown :: Int -> [Int]' 'countdown 0 = []' 'countdown n = n : countdown (n - 1)' '' 'power :: Int -> Int -> Int' 'power _ 0 = 1' 'power base n = base * power base (n - 1)' '' 'fibs :: [Int]' 'fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)' > Rec.hs"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Count down from 5
docker exec haskell ghc -e "countdown 5" Rec.hsShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Work out 2 to the power 10
docker exec haskell ghc -e "power 2 10" Rec.hsShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: countdown 3
| Call | Which line applies | What it becomes |
|---|---|---|
| countdown 3 | the second line | 3 : countdown 2 |
| countdown 2 | the second line | 2 : countdown 1 |
| countdown 1 | the second line | 1 : countdown 0 |
| countdown 0 | the first line: the base case | [] |
| All together | 3 : 2 : 1 : [] | [3, 2, 1] |
The cells students fill in are left blank in this preview.
Haskell works out a value only when needed
Haskell is lazy. It does not work out an expression until something needs the answer. That is lazy evaluation.
So [1 ..], the list of all whole numbers from 1, is allowed. Haskell does not build it. It builds just as much as you ask for. take 5 of it asks for five items.
Take five from an endless list
docker exec haskell ghc -e "take 5 [1 ..]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Double a number again and again
docker exec haskell ghc -e "take 4 (iterate (* 2) 1)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A value that is never asked for
docker exec haskell ghc -e "fst (1, length [1 ..])"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: what each call asks for
| Expression | What it needs | Answer |
|---|---|---|
| take 5 [1 ..] | the first five items | [1,2,3,4,5] |
| take 4 (iterate (* 2) 1) | four doublings | [1,2,4,8] |
| fst (1, length [1 ..]) | only the first part of the pair | 1 |
| length [1 ..] | every item, which never ends | no answer |
The cells students fill in are left blank in this preview.
A list can be defined by itself
The Fibonacci numbers start 0, 1, and each next number is the sum of the two before. In Haskell the whole endless list is one line.
The function zipWith (+) adds two lists item by item. The list is built from its own earlier items, and laziness makes that work.
Take ten Fibonacci numbers
docker exec haskell ghc -e "take 10 fibs" Rec.hsShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Try it: a lazy stream in Python
def naturals():
n = 1
while True:
yield n
n = n + 1
stream = naturals()
print(next(stream))
print(next(stream))
print(next(stream))
# Each next asks for one more value. Nothing is worked out before.
# Add two more print(next(stream)) lines and press Run.
A common mistake
Warning
Many people think an infinite list fills the memory or makes the program run for ever. A lazy language builds only the part you use, so take 5 of it holds five items. What never ends is asking for all of it, such as the length of an endless list.