Before you begin
Why this matters
Haskell values last as long as something can reach them, and memory can hold work that has not happened yet. Knowing this explains when values are shared safely, and why a program can use more memory than its results seem to need.
What this helps you reason about
- Predict whether a value is computed once and shared, or computed again.
- Recognize that a binding may hold work that has not happened yet.
- Ask what can still reach a value before assuming its memory is free.
The stack-and-heap picture is a correct, useful model for languages that run each call in a frame, such as C and Java. Haskell does not promise frames. So this lesson follows which values are needed and what can still reach them, not which frame a variable lives in.
Already know this? The short version
- Haskell promises non-strict evaluation, not frames: an expression is evaluated when its value is needed, and the stepper shows one evaluation location per stop.
- Values live on GHC’s heap while they are reachable, and immutable structure such as the tail of a list is shared safely.
- A binding can hold a thunk that never runs if nothing needs it, so memory can fill with pending work as well as with values.
- The garbage collector reclaims values once they are unreachable, including through thunks. Measure a compiled program with +RTS -s, because optimization changes what is allocated.
Words in this lesson (7)
- frame
- In the common picture, the memory for one running function call: its parameters and local variables. Haskell does not promise frames.
- heap
- An area of memory for values that must outlive the code that created them. GHC keeps Haskell values and unfinished work there.
- non-strict evaluation
- The Haskell rule that an expression is evaluated only when its value is needed. A binding that nothing needs is never evaluated. GHC implements the rule as lazy evaluation: a named value is usually computed at most once and then shared.
- sharing
- Two values using the same part in memory, such as the rest of a list. It is safe because ordinary Haskell values cannot change.
- thunk
- GHC’s stored description of work that has not happened yet. When the value is needed, GHC runs the work and replaces the thunk with the result.
- reachable
- A value is reachable when the program can still get to it by following references from what is still running, including thunks that refer to it.
- garbage collector
- The part of GHC’s runtime that finds values that are no longer reachable and reuses their memory.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / The common picture
What do people mean by stack and heap?
Most programmers learn a picture called stack and heap. In it, each function call gets a frame, a block of memory for its parameters and local variables, kept on a stack; values that must outlive their call are kept in a separate area of memory, called the heap.
Haskell does not promise this picture. It does not promise a frame per call, and its ordinary values cannot be changed. (Types such as IORef are explicit exceptions.) GHC’s runtime, the code that GHC adds to every program to manage evaluation and memory, does use a stack and a heap, but not in the way the picture suggests.
The picture is still a correct model for many other languages, and worth knowing. In Haskell, follow two things instead: which values are needed, and what can still reach them.
Most languages use frames for calls and a heap for longer-lived values. Haskell does not promise either.
02 / Frames
If not frames, what should you follow?
Haskell’s rule is non-strict evaluation: an expression is evaluated only when its value is needed. So instead of frames, follow what is needed. print needs outer, and outer needs inner 4. Each is evaluated when its value is needed. The stepper shows where evaluation is happening, not a stack of calls.
inner :: Int -> Int
inner n = n * 2
outer :: Int
outer = inner 4 + 1Follow which values are needed, not which calls are active.
Experiment
Follow evaluation instead of frames
Haskell does not promise a frame per call. print needs the value of outer, which needs inner 4. Each is evaluated when its value is needed.
Why it matters The stack-and-heap picture describes how many languages run calls. For Haskell, ask instead which values are needed and when.
Predict what prints. Then change outer to use inner 10 and predict again.
inner :: Int -> Int
inner n = n * 2
outer :: Int
outer = inner 4 + 1
main :: IO ()
main = print outer
What to look for
Watch which definition each stop is in. GHCi shows one location per stop, not a stack of frames: you see outer, then inner with n = 4, as their values are needed. 9 appears when the run ends, once print has the value.
Expected output
903 / Outliving a call
How long does a value last, and when is it shared?
The Variables lesson showed that a new value can reuse part of an old one, safely, because no value can change. This reuse is called sharing. This section asks how long a value lasts, and when two uses share it.
Values are kept on GHC’s heap for as long as something can reach them, even after the function that built them has finished. A name is one value: once first has been computed, every use of first shares that result. A call is new work: makeValues 3 written twice builds two lists, even though they are equal.
first = makeValues 3
second = makeValues 3 -- a second list, built again
same = first -- the same list as firstOne name, two calls. This is a model of what each value depends on, not of how GHC stores it.
A conceptual model, not a physical memory layout or live code execution.
1 / 3
Define
- first, second
- makeValues 3 each
- same
- first
first, second, and same describe values. Nothing is computed yet.
A named value such as first is computed at most once and then shared; each call is new work.
Coming from JavaScript: In JavaScript, makeValues(3) written twice also runs twice; Haskell does not remember the results of calls for you either. Only a name is computed once.
Precisely: when a name is computed again
A name whose type has a class constraint, such as total :: Num a => a, is a function underneath: it can be computed again at each use. An optimizing build may also copy work into several places. The names in this section have the plain type [Int], so GHC computes each of them at most once.
Experiment
Call a function twice, or share one value
A call to makeValues is new work that builds a new list. A name is one value: once first has been computed, every use of first shares that result. Sharing is safe because no list can change.
Why it matters Values in Haskell last as long as something can still reach them, like in other garbage-collected languages. To compute something once, give it a name and use the name.
Predict how many times GHCi stops in makeValues. Then change second = makeValues 3 to second = first and predict again.
makeValues :: Int -> [Int]
makeValues n = [n, n + 1]
main :: IO ()
main = do
let first = makeValues 3
second = makeValues 3
print (first, second)
What to look for
Count the stops in makeValues. The output shows ( before anything is computed, because print writes as it goes. GHCi stops in first, then twice in makeValues; then in second, then twice in makeValues again: two calls, two lists. After the edit, GHCi stops in second once, where first already shows [3,4], and never again in makeValues: second is the same list. Both versions print ([3,4],[3,4]).
Expected output
([3,4],[3,4])04 / Refining the picture
Where does the picture need refining?
Here the picture needs a different model. A binding does not have to hold a finished value. It can hold a description of work that has not happened yet, which GHC calls a thunk. The work is done only if something needs its result.
So memory can hold unfinished work as well as values. A program that builds up a lot of unfinished work can use far more memory than its results need.
let small = sum [1, 2, 3] :: Int
unused = length [1 .. 1000000 :: Int]
-- only small is ever computedMemory can hold work that has not been done yet.
Coming from Python: In Python, small = sum([1, 2, 3]) runs at once; a Haskell let only describes the work, which runs when the value is needed.
Experiment
Define a value that is never computed
A binding names work that may happen later. GHC keeps a description of that work until the value is needed, and never does it if nothing needs it.
Why it matters Memory in Haskell can hold work that has not happened yet, not just finished values. That is a different picture from frames and objects.
Predict what prints. Then print (small, unused) instead and predict again.
main :: IO ()
main = do
let small = sum [1, 2, 3] :: Int
unused = length [1 .. 1000000 :: Int]
print small
What to look for
Watch where GHCi stops. It stops in small, which print needs, and never in unused: nothing needs it, so its work never happens. 6 appears when the run ends.
Expected output
605 / Releasing memory
Who decides when memory can be reused?
GHC’s runtime has a garbage collector: a part that finds memory the program can no longer use and makes it available again.
A value is reachable when the program can get to it by following references from what is still running, including unfinished work. The garbage collector reuses the memory of values that are no longer reachable. A binding going out of scope does not free anything by itself. A value is freed some time after nothing the program can still reach refers to it.
Values last as long as something can reach them, including unfinished work that refers to them.
06 / The implementation
What may the compiler or runtime change?
GHC is the compiler: it translates your Haskell into machine instructions. When it optimizes, it can remove intermediate lists, evaluate values early when it can prove that is safe, and represent values in different ways.
With optimization (ghc -O), a binding such as unused, which nothing needs, is usually removed completely, so no thunk is ever created for it. The stepper runs code in GHCi, which does not optimize. Non-strict evaluation is the language rule; how much work and memory a program uses is a property of the compiled program.
Precisely: measure a real program
Save the program from Try it as Example.hs, compile it with ghc -rtsopts Example.hs, and run it with ./Example +RTS -s. With GHC 9.0.2 in the stepper’s container, the first line of the statistics read 52,024 bytes allocated in the heap. Adding print unused as the last line raised it to 72,053,504 bytes: building and counting a million list cells. Compiled with ghc -O, that same version allocated 52,696 bytes, because the optimizer counted without building the list. Each figure describes one executable, including the runtime’s own memory, and a tiny example cannot show a general rule.
07 / Try it
Which values are computed, and which are shared?
Predict the output, then follow demand: which bindings does print need, and how many times?
makeValues :: Int -> [Int]
makeValues n = [n, n + 1, n + 2]
main :: IO ()
main = do
let values = makeValues 3
total = sum values
unused = length [1 .. 1000000 :: Int]
print (head values)
print totalWhat prints? Which of values, total, and unused are ever computed, and how many times is makeValues 3 computed?
Reveal the reasoning
3, then 12. print (head values) needs only the first element of values. print total needs total, which needs every element of values. values is a name, so makeValues 3 is computed once, and total shares the list that head already started. unused is never needed, so its work never happens: in GHCi it stays an unevaluated thunk, and an optimized build usually removes it. The million-element list is never built.
Practice tickets
- STK-101 · Keep each shelf label as it was printed → Free
- STK-102 · Hand out a receipt snapshot that stays as it was → Sign in · Pro
- STK-103 · Open one connection and close it → Sign in · Pro
Keep exploring
Investigate a minimal reproduction →