🎓 A1Learner
🔍
0 of 47 lessons completed

Haskell Optimization Notes

Optimization is changing a program so it does less unnecessary work. The safest optimizations keep the result identical while removing wasted passes, repeated work, or slow shapes.

Cons onto an accumulator reverses in one pass

Each element is consed onto the front. The result is the input in reverse order.

main :: IO ()
main = print (foldl (flip (:)) [] [1,2,3])

A length computed once can be reused

The length is bound to a name. The sum is printed beside it without recomputing the length.

main :: IO ()
main = do
  let xs = [10,20,30,40]
  let n = length xs
  print n
  print (sum xs)

A concrete Int type keeps arithmetic plain

The total is declared as Int. The sum of the numbers from 1 to 100 is printed.

total :: Int
total = sum [1..100]
main :: IO ()
main = print total

Example

import Data.List (foldl')
countEvenSum :: [Int] -> (Int, Int)
countEvenSum xs = foldl' step (0, 0) xs
  where step (c, s) x = if even x then (c + 1, s + x) else (c, s)
main :: IO ()
main = do
  let (c, s) = countEvenSum [1..50]
  print c
  print s

Key points

  • Optimization: changing a program to do less unnecessary work.
  • Single pass: one walk over a list that computes every summary at once.
  • Use an accumulator with cons instead of appending lists in a loop.
  • Compute a length once and reuse it instead of recomputing it.
  • Use a concrete type such as Int when the values are plain whole numbers.

In this example, the program folds once over the numbers from 1 to 50, counting the even numbers and adding them in the same pass, then prints the count and the sum.

Note

an optimization is only good when the result stays identical, so every claim here is checked against a printed result.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Haskell Playground

Exercise

Why is appending lists inside a loop a slow shape?