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.
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:
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:
')
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.
Take this example:
(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?
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:
Add another comparison with the sample:
To check that y is a list, the compiler evaluates it to the form:
Then, it calculates the first promise:
And after making sure that y is a list starting with 'l', it performs pattern matching:
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:
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:
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
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,
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:
And these will lead:
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:
Here
Such a comparison with the sample can be found in Control.Arrow:
But we must remember that a lazy sample should be used only when the type has one constructor.
For example:
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.
The most obvious plus of lazy calculations is that if something is not required, it will not be calculated.
For example:
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:
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.
Consider this function:
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 .
Another fairly well known application of deferred computation is the creation of infinite data structures.
Here we create an infinite list of odd numbers, and take its 10th element.
The example is more complicated:
Creating endless lists is possible only because they are not calculated immediately. In the second example, fibs will first be
We now turn to cyclic data structures.
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:
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.
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:
The program will display text in upper case as it becomes available.
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.
Consider this simple example:
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:
Why does a stack overflow occur? Let's see how the sum 'function will be calculated:
Since the calculation of
First, let's rewrite the sum function to use tail recursion:
Now to force addition to be calculated will not be difficult:
Seq forces the sum to be calculated, instead of postponing the addition until later.
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.
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
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:
The deepseq function calculates values completely, up to the Normal Form.
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:
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:
SPair is a strict pair. The values in its fields will always be computed, which, again, does not allow promises to accumulate.
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.
Haskell / Laziness
Profiling and optimization
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
Source: https://habr.com/ru/post/131910/
All Articles