🎓 A1Learner
🔍
0 of 47 lessons completed

Haskell Fusion Idea

Fusion is a compiler rewrite that turns two passes over a list into one pass. The result stays the same while the intermediate list disappears.

Two maps give the same result as one map

The first line maps twice. The second line maps once with the combined function.

main :: IO ()
main = do
  print (map (+1) (map (*2) [1,2,3]))
  print (map (\x -> x * 2 + 1) [1,2,3])

A mapped sum is still a plain sum

Mapping doubles every element. The sum and the length describe the mapped list.

main :: IO ()
main = do
  print (sum (map (*2) [1..10]))
  print (length (map (*2) [1..10]))

Taking early stops the pipeline early

Only five results are taken. The take limits how much of the list the pipeline needs.

main :: IO ()
main = do
  print (take 5 (map (*3) [1..100]))
  print (length (take 5 (map (*3) [1..100])))

Example

main :: IO ()
main = do
  let evens = filter even [1..20]
  print (length evens)
  print (sum (map (^2) evens))

Key points

  • Fusion: a compiler rewrite that merges list passes into one pass.
  • Use fusion reasoning to keep a pipeline readable without fearing extra passes.
  • Intermediate list: a list built only to be consumed by the next pass.
  • Result check: two pipelines give the same result when fusion applies.

In this example, the program filters the numbers from 1 to 20 down to the even ones, prints how many there are, then squares each even number and prints the sum of the squares.

Note

fusion is a compiler behaviour, so a program proves it only through identical results, never through a claimed time.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Haskell Playground

Exercise

What does map (+1) (map (*2) [1,2,3]) produce?