λ Lessons

λ Lessons

Pattern matching, first-class functions, and abstracting over recursion in Haskell

This is a short, interactive lesson that teaches core functional programming concepts. It was designed to transform the way you think about performing operations on lists of things, by showing you how functions are executed.
You can explore the way map and fold (foldr and foldl) are defined and computed. Feel free to re-define any of the functions used in this document in the Function Editor.
This document implements a small, dynamically-typed, subset of Haskell that includes integers, lists, functions, pattern matching and recursion.
Built by Jan Paul Posma & Steve Krouse at YC Hacks '14 with React.js & PEG.js. Inspired by Bret Victor & Brent Yorgey. Check out the source.

map
map is a function that performs some operation on every element in a list. 
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
map takes 2 inputs
  • function of type (a -> b)
  • list of type [a]
and returns
  • list of type [b]
The base-case of map pattern matches on [] and returns [].

The recursive-case of map pattern matches on the first list element x and returns (f x) : map f xs.
fold
fold describes 2 functions that "summarize" the elements in a list.
  • foldr - "fold right", applies f to x and the result of folding f over the rest (remember: foldr moves to the right as it computes with the computation on the outside)
  • foldl - "fold left", evaluates f x i immediately and uses that as the new initial value for folding f over the rest (remember: foldl stays on the left as it computes with the computation on the inside)
foldr 
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f i [] = i
foldr f i (x:xs) = f x (foldr f i xs)
foldr takes 3 inputs
  • function of type (a -> b -> b)
  • initial value of type b
  • list of type [a]
and returns
  • accumulated value of type b
The base-case of foldr pattern matches on [] and returns i.

The recursive-case of foldr pattern matches on the first list element x and returns f x (foldr f i xs).
foldl 
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f i [] = i
foldl f i (x:xs) = foldl f (f i x) xs
foldl takes 3 inputs
  • function of type (a -> b -> a)
  • initial value of type a
  • list of type [b]
and returns
  • accumulated value of type a
The base-case of foldl pattern matches on [] and returns i.

The recursive-case of foldl pattern matches on the first list element x and returns foldl f (f i x) xs.