Laziness and eager evaluation: Haskell and C++
Reading five elements out of a million is the smallest question a language can be asked about evaluation order, and the two languages answer it differently by default. C++ evaluates when it is told to: a vector of a million squares is a million calls, and taking five of them afterwards changes nothing. Haskell evaluates when a value is needed: take 5 of an infinite list calls the producer five times, and the rest of the list is never built.
C++ has the lazy answer too, since C++20 ranges: a view composes iota, transform and take without building anything. The difference is which one you get when you write nothing special, and what the lazy one costs when the plan changes.
An eager vector and a lazy view
One program, the same five values computed twice. The first way builds a vector of the first million squares and then takes five; the second pipes an iota through a transform and a take into a loop. A counter in square says how many calls each way made, and steady_clock says how long each took.
#include <chrono>
#include <cstdio>
#include <ranges>
#include <vector>
long calls = 0;
int square(int n) {
++calls;
return n * n;
}
int main() {
using clock = std::chrono::steady_clock;
constexpr int limit = 1000000;
calls = 0;
const auto eager_start = clock::now();
std::vector<int> all;
all.reserve(limit);
for (int n = 1; n <= limit; ++n) {
all.push_back(square(n));
}
int eager_sum = 0;
for (int i = 0; i < 5; ++i) {
eager_sum += all[i];
}
const auto eager_end = clock::now();
const long eager_calls = calls;
const long eager_us = std::chrono::duration_cast<std::chrono::microseconds>(eager_end - eager_start).count();
calls = 0;
const auto lazy_start = clock::now();
int lazy_sum = 0;
for (int value : std::views::iota(1, limit) | std::views::transform(square) | std::views::take(5)) {
lazy_sum += value;
}
const auto lazy_end = clock::now();
const long lazy_calls = calls;
const long lazy_us = std::chrono::duration_cast<std::chrono::microseconds>(lazy_end - lazy_start).count();
std::printf("eager calls %ld time %ld us first five sum %d\n", eager_calls, eager_us, eager_sum);
std::printf("lazy calls %ld time %ld us first five sum %d\n", lazy_calls, lazy_us, lazy_sum);
}
The program was run twice so that the reader can see the numbers are stable to the millisecond and not a single lucky run:
g++ -std=c++23 -Wall -Wextra -O2 lazy.cpp -o lazy
./lazy; ./lazy; echo "status $?"
eager calls 1000000 time 4590 us first five sum 55
lazy calls 5 time 0 us first five sum 55
eager calls 1000000 time 4533 us first five sum 55
lazy calls 5 time 0 us first five sum 55
status 0
A million calls against five, and about four and a half milliseconds against nothing measurable. The vector also holds a million integers, which the second way never allocates; the memory page measures that side.
An infinite list
[1 ..] is a list with no end and no special syntax for it: it is the enumeration from 1, and nothing computes its elements until somebody asks. map square [1 ..] is the list of every square, and take 5 asks for five. The trace calls in the two functions print when a value is actually computed, which turns the output into the evaluation order.
module Main (main) where
import Debug.Trace (trace)
import System.IO (BufferMode (LineBuffering), hSetBuffering, stdout)
square :: Int -> Int
square n = trace ("square " ++ show n) (n * n)
isEven :: Int -> Bool
isEven n = trace ("even " ++ show n) (even n)
main :: IO ()
main = do
hSetBuffering stdout LineBuffering
putStrLn "first five squares"
mapM_ print (take 5 (map square [1 ..]))
putStrLn "first five even squares"
mapM_ print (take 5 (filter isEven (map square [1 ..])))
trace writes to standard error, and a program whose output is redirected buffers standard output, so the program sets LineBuffering to keep the two streams in order. The run merges them with 2>&1:
ghc -Wall -O1 -o lazy-hs Lazy.hs
./lazy-hs 2>&1; echo "status $?"
[1 of 2] Compiling Main ( Lazy.hs, Lazy.o )
[2 of 2] Linking lazy-hs
first five squares
square 1
1
square 2
4
square 3
9
square 4
16
square 5
25
first five even squares
square 1
even 1
square 2
even 4
4
square 3
even 9
square 4
even 16
16
square 5
even 25
square 6
even 36
36
square 7
even 49
square 8
even 64
64
square 9
even 81
square 10
even 100
100
status 0
Five calls for the first five squares, and ten for the first five even squares: the filter had to look at ten values to find five that pass. Every number is printed as soon as it is computed, so the interleaving is not decoration: it is the order the program did the work in.
Default against opt-in
In Haskell laziness is the default, which is why an infinite list is an ordinary value and why a function can return before it has looked at its argument. In C++ eagerness is the default and laziness is a property of the range adaptors: a views::transform is lazy, a std::transform into a vector is not, and the compiler will not tell you which one you meant.
Being lazy by default costs space. A value that is promised and never demanded is free, a value that is promised and demanded later is a closure on the heap, and a chain of a million promises is a chain of a million closures. The classic accident is a fold whose accumulator is never forced, which the course lesson on space leaks and +RTS -s measures with real numbers, and the fix is foldl' or a bang pattern.
Being eager by default costs work. The vector above is a million squares where five were wanted, and a program that takes the first match out of a large file reads the file. The C++ answer is to reach for a view, and that works until the algorithm needs random access or two passes, at which point the view is materialised and the laziness is gone.
The work that did not happen
Laziness also means that work a reader sees in the source may never happen. The program below asks for the length of the list of a million squares and then for the sum of three of them, and the trace shows which calls were made:
module Main (main) where
import Debug.Trace (trace)
import System.IO (BufferMode (LineBuffering), hSetBuffering, stdout)
square :: Int -> Int
square n = trace ("square " ++ show n) (n * n)
main :: IO ()
main = do
hSetBuffering stdout LineBuffering
putStrLn ("length of a million squares: " ++ show (length (map square [1 .. 1000000])))
putStrLn ("sum of three squares: " ++ show (sum (map square [1 .. 3])))
ghc -Wall -O1 -o skipped-hs Skipped.hs
./skipped-hs 2>&1; echo "status $?"
[1 of 2] Compiling Main ( Skipped.hs, Skipped.o )
[2 of 2] Linking skipped-hs
length of a million squares: 1000000
square 1
square 2
square 3
sum of three squares: 14
status 0
length does not need the values, only the spine, so square is called zero times for a million elements. sum needs every value, so the three calls appear. The same program with a strict function behaves the other way: take 5 (sort xs) forces all of xs, because a sort cannot produce its first element without ordering everything. Lazy does not mean cheap, it means cheap until a function needs its input.
The practical rule for a measurement is therefore the one the throughput page follows: force the result and print it, because a benchmark that returns a length measures the mapping not at all. In C++ the same trap exists in the optimiser, which deletes a computation whose result nobody uses, and the counter in the first program is there for the same reason.
The Haskell lesson on the subject is laziness and infinite lists, and the next page in this set is Type classes, templates and concepts.
The C++ program was built with g++ 15.2.0 (Alpine 15.2.0) using -std=c++23 -Wall -Wextra -O2 and the Haskell program with GHC 9.10.3 using -Wall -O1, both run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev