Lazy computing

One of Haskell’s “business cards” is deferred, or lazy, calculations. This feature of the language not only opens up many possibilities, but also creates some problems, especially with the speed of the programs.

In this article I will try to explain what lazy calculations are, what they can be used for and how to avoid performance loss when using them.

What is lazy computing?

In ordinary, not lazy programming languages, computations are strict — that is, the function arguments are evaluated before the function itself is executed.
For example, in some abstract strict programming language:

max(5+3, 4*4) ->
max(8, 4*4) ->
max(8, 16)
16

And in lazy languages, including Haskele, calculations are postponed. All calculations (except for some I / O functions) are not performed immediately, but, as it were, are postponed until real need.
The same example in Haskell:
')
max (5+3) (4*4) ->
let x = 5+3; y = 4*4 in if x >= y then x else y ->
let x = 8; y = 4*4 in if 8 >= y then 8 else y ->
let x = 8; y = 16 in if 8 >= 16 then 8 else 16 ->
16

In this example, it is clearly seen that the calculation of the subexpressions (5 + 3 and 4 * 4) was postponed until the last, namely until the moment when they had to be compared.
Here, the “force” that caused the calculation to execute can be considered the console output, i.e Io. But this is not the only way.

Promises

Take this example:

let z = (sum [1..10], reverse "haskell") in ...
(we assume below that z is used in the in part, otherwise the let expression will not be evaluated at all)

z is a promise (thunk), just not a calculated value.
And what will happen if we compare it with sample z?

 let z = (sum [1..10], reverse "haskell") (x, y) = z in ... 

At first, z is a simple promise, as in the previous example, but in order for the compiler to check that z really matches the pattern, it has to “unfold” z to the form: (**, **) . x and y here are promises corresponding to the components of the pair z.
Add another comparison with the sample:

 let z = (sum [1..10], reverse "haskell") (x, y) = z 'l':ys = y in ... 

To check that y is a list, the compiler evaluates it to the form: ** : **
Then, it calculates the first promise: 'l' : **
And after making sure that y is a list starting with 'l', it performs pattern matching: 'l':ys = 'l':**
In this example, ys will be a promise corresponding to the rest of the y list.

Let's look at how the depth of calculation for z has changed throughout all the examples:

**
(**, **)
(**, 'l':**)

z was partially computed, and as you can guess, almost all values ​​in Haskell can be computed in this way. For example, the minimum possible calculation for a pair is simply to calculate the constructor: (**, **) . For a list, this is **:** or []. And for the numbers of this form does not exist - they are either computed or not.
When a value is not fully computed, it is said to be in the Weak Head Normal Form (WHNF), and when fully, it is said to be in the Normal Form . The value in WHNF, when fully computed, “transitions” to the Normal Form. For example, if we print z to the screen, then its Normal Form will be (55,"lleksah") . Obviously, values ​​whose constructor has no arguments cannot be in WHNF. That is, such types as Bool, Ord, Int, etc. do not have WHNF, and the types Maybe, [a], Either, etc. have

Lazy features

Functions are lazy and strict in their arguments. Lazy - do not calculate their arguments, and rigorous - calculate, to any depth. It is worth noting that a function can be lazy in one argument and strict in another. Of course, most functions need to somehow use their arguments, which implies their calculation. For example, the function length. To find out the length of a list, it has to calculate its constructors, but not its values. That is, length ** "opens" into something like: length (** : ** : ** : []) .

There is an easy way to check if a function is lazy in any argument. You just need to pass it the argument undefined instead of it, and if the result is an error, then the function is strict in this argument, and if not, it is lazy.
Will not lead to an error:

const 5 undefined
Just undefined

And these will lead:

length undefined
head undefined

Lazy pattern comparison

Lazy can be not only functions, but also comparisons with the sample. In contrast to the strict pattern comparisons that we have already considered, the lazy ones do not force promises to be calculated, that is, they do not “unfold” them during compilation.
For example:

> let f ~(x, y) = 1
> f undefined
1

Here ~(x, y) is a lazy pattern. It has the same property as the argument of the lazy function: when we pass undefined there, an error does not occur.
Such a comparison with the sample can be found in Control.Arrow:

(***) fg ~(x, y) = (fx, gy)

> (const 1 *** const 2) undefined
(1, 2)

But we must remember that a lazy sample should be used only when the type has one constructor.
For example:

head' :: [a] -> a
head' ~[] = undefined
head' ~(x:xs) = x

Since we indicated that it is not necessary to calculate the function argument until it is needed, it is not possible to know what is before us: an empty list or one of its links. The function will always return undefined, because in the first expression we used an irrefutable sample.

Using lazy computing

Calculation on demand

The most obvious plus of lazy calculations is that if something is not required, it will not be calculated.
For example:

(&&) False _ = False
(&&) True a = a

If the first argument of the function and is False, why calculate the second, if it is clear that the result is False? It is possible to find out the value of the second argument, you will need to make a lot of time-consuming calculations, which, using lazy calculations, can be avoided.

Imagine that you want to find the 3 smallest list items.
In Haskell it can be done like this:

take 3 (sort xs)

But in a strict language it is wasteful, because you have to sort the entire list. But with lazy calculations, we will sort the list down to the third item and stop, because it doesn't make sense to continue the calculation.

Memoization

Consider this function:

plus a = a+a

> plus (5+3)
16

How many times was the sum of 5 and 3 calculated? The correct answer is: once. At first (5 + 3) was just a promise, but when it was passed to the plus function, it was calculated and its answer replaced the promise itself. When the value of a was needed a second time, the program simply took the finished result from the former promise, without performing any calculations. This is one of the most important properties of lazy computing - memoization. A promise in a lazy language is calculated only once, and then the result of the calculation "overwrites" the promise, thereby allowing the program to simply find out the answer, without having to calculate it again.
This property of lazy computing is used in dynamic programming, which was well shown in the article Dynamic programming and lazy computing .

Infinite and cyclic data structures

Another fairly well known application of deferred computation is the creation of infinite data structures.

> [1, 3..] !! 10
21

Here we create an infinite list of odd numbers, and take its 10th element.

The example is more complicated:

> fibs = 1:1:zipWith (+) fibs (tail fibs)
> fibs !! 100
573147844013817084101

Creating endless lists is possible only because they are not calculated immediately. In the second example, fibs will first be 1:1:** , but when we request the following items from this list, the program will have to fulfill promises until our needs are met. One promise can spawn others, so from a small list and a promise, fibs can turn into a huge chain of Fibonacci numbers.

We now turn to cyclic data structures.

data List a = List {value :: a, next :: List a}

How do we tie two elements of this type into a ring, so that the next field of one object points to another?
If we wanted to implement this in an imperative language, we would use pointers, but in Haskell there are no pointers. So how to create such a structure?
Very simple:

let x = List "x" y
y = List "y" x
in x

That's all. Since the List field next is lazy (we must remember that the type constructor is the same function and its arguments can be lazy) creating such a “ring” will not cause the program to freeze in attempts to calculate the entire structure.

> value . next $ x
"y"

Lazy I / O

Only simple I / O functions are really strict, and the rest are lazy. This makes it possible to read and write to files on the fly, as a pipeline, without the use of buffers.
For example:

import Data.Char

main = print . map toUpper =<< getContents

The program will display text in upper case as it becomes available.

Problems associated with the use of lazy computing

Throughout the article, I used the term “promise” to denote a unit of lazy evaluation, but the fact is that this is not just an abstract concept. The compiled program on Haskell actually uses promises that take place in memory and on the stack. That is, garbage collection, memory allocation, and unfolding of promises are added to the cost of ordinary calculations. This is the main problem of lazy calculations - you can pay for their illiterate use by a strong decrease in performance, stack overflows and large memory consumption.

But there are ways to make calculations less lazy, which we now consider.

Seq

Consider this simple example:

 main = print . sum' $ [1..1e6] sum' [] = 0 sum' (l:ls) = l + sum' ls 

Here we find the sum of the numbers from 1 to 1e6 and output it to the console. But if you try to start the program, you will see the following message:

$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

Why does a stack overflow occur? Let's see how the sum 'function will be calculated:
1 + (1 + (1 + ... (1 + sum' [])))

Since the calculation of sum' ls postponed, we get a lot of nested promises that occupy space on the stack. To get rid of this, we must somehow make promises to be calculated, and not accumulated. And for this we have the seq function. It takes two arguments, the first of which is calculated, and the second is returned. Let's try applying it here.

First, let's rewrite the sum function to use tail recursion:

 main = print . sum' $ [1..1e6] sum' ls = go 0 ls where go n [] = n go n (l:ls) = go (l + n) ls 

Now to force addition to be calculated will not be difficult:

 main = print . sum' $ [1..1e6] sum' ls = go 0 ls where go n [] = n go n (l:ls) = let s = l + n in s `seq` go s ls 

Seq forces the sum to be calculated, instead of postponing the addition until later.

$ ./test
5.000005e11

Now the error does not occur.

Let's try a slightly complicated example: in addition to the sum of the elements, we calculate their number.

 main = print . sum' $ [1..1e6] sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let t = (l + n, d + 1) in t `seq` go t ls 

$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

Again the same mistake. But why? After all, we made the amounts calculated?
It’s time to talk about one seq property: it calculates the value before the WHNF. Ordinary numbers, as mentioned earlier, do not have WHNF, so addition has been completely calculated by seq. But in this case we are trying to calculate a pair that has the WHNF, namely (**, **) . So the promises still accumulate, which leads to a stack overflow. We can force the fields to be calculated using seq:

 main = print . sum' $ [1..1e6] sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let s = l + n d' = d + 1 in s `seq` d' `seq` go (s, d') ls 

$ ./test
(5.000005e11,1000000)

A little ugly, but it works. The situation when you need to calculate something completely is not so rare, so a special module was created for this. Let's try it out:

 import Control.DeepSeq (deepseq) main = print . sum' $ [1..10^6] sum' :: [Integer] -> (Integer, Int) sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let t = (l + n, d + 1) in t `deepseq` go t ls 

The deepseq function calculates values ​​completely, up to the Normal Form.

Bang patterns

For a more convenient indication of strictness, a compiler extension, Bang patterns, was created. It allows you to specify the severity of the arguments just an exclamation point. Using this extension, we can rewrite our code like this:

 {-# LANGUAGE BangPatterns #-} main = print . sum' $ [1..10^6] sum' :: [Integer] -> (Integer, Int) sum' ls = go (0, 0) ls where go (!n, !d) [] = (n, d) go (!n, !d) (l:ls) = go (l + n, d + 1) ls 

Everything will work as before.
Bang patterns allow us to specify the severity of not only the arguments of the functions, but also the fields of the data structures, for example:

 {-# LANGUAGE BangPatterns #-} data SPair ab = SPair !a !b deriving Show main = print . sum' $ [1..10^6] sum' :: [Integer] -> SPair Integer Int sum' ls = go (SPair 0 0) ls where go (SPair nd) [] = SPair nd go (SPair nd) (l:ls) = go (SPair (l + n) (d + 1)) ls 

$ ./test
SPair 500000500000 1000000

SPair is a strict pair. The values ​​in its fields will always be computed, which, again, does not allow promises to accumulate.

Conclusion

In this article, I tried to explain how to cope with lazy calculations. I hope after reading it you will begin to understand where and how best to use deferred calculations, why they are needed at all.

List of materials used

Haskell / Laziness
Profiling and optimization