teaching machines

CS 330: Lecture 26 – Ways of Making Functions: Composition and Lambdas

April 11, 2018 by . Filed under cs330, lectures, spring 2018.

Dear students:

There are at least four ways of defining functions in Haskell:

We’ve seen the first two. Now let’s turn to composition. You’ve almost certainly worked with composition in your math classes. What is meant by (f . g)(x)? It means g is evaluated at x, and the result of calling g is used to further evaluate f.

Composing means to chain operations together, much like pipelining at the shell. The difference between composition and pipelining (or Haskell’s $ operator) is a matter of precedence. Haskell’s compose operator lets us chain functions together before applying any parameters. We can produce new functions by composing old ones together:

h = f . g
h 5         -- these three calls
(f . g) 5   -- will produce the
f (g 5)     -- same result

That means we can eliminate a lot of clutter from our code! Those gauntlets of function calls that our data must pass through can be shrunk down to a single meaningful name.

Time for some examples:

  1. Let’s write rsort which sorts a list in reverse:
    rsort = Ord a => [a] -> [a]
    rsort = reverse . sort
  2. Let’s write a function that gives us the second element of a list, the neck:
    neck :: [a] -> a
    neck = head . tail
  3. Let’s write a function to compute the square of the sum of a list:
    squareOfSum = (^2) . sum
  4. Let’s write a function to compute the number of negatives in a list:
    nnegatives :: [Integer] -> Int
    nnegatives = length . filter isNegative
      where isNegative x = x < 0
  5. Let’s write scalebias to map a value using a linear function:
    scalebias :: Double -> Double -> Double -> Double
    scalebias scale bias x = scale * x + bias     -- without composition
    scalebias' scale bias = (+ bias) . (* scale)  -- with composition
    Now we write calc2fahren like we should have back in high school:
    c2f :: Double -> Double
    c2f = scalebias' 1.8 32
  6. Let’s write a function that gives us a list of the unique items within another list:
    onlies :: Ord a => [a] -> [a]
    onlies = concat . filter single . group . sort
      where single list = length list == 1
  7. Let’s write a function that gives us the mode in a list of data:
    onlies :: Ord a => [a] -> a
    onlies = head . head . reverse . sortWith length . group . sort

Both partial evaluation and composition eliminate a lot of the overhead that we programmers find ourselves doing. Much of our development life is spent gluing together abstractions into some mega-abstraction, and these two techniques give us some of our life back.

See you then!


P.S. It’s time for a haiku!

P.P.S. Here’s the code we wrote together:


import Data.List
import Data.Char

toLowercase :: String -> String
toLowercase "" = ""
toLowercase (first:rest) = toLower first : toLowercase rest

tango :: Ord a => (a, a) -> a
tango (a, b) = max a b

rsort :: Ord a => [a] -> [a]
-- rsort list = reverse (sort list)
-- rsort list = (reverse . sort) list
rsort = reverse . sort

neck :: [a] -> a
-- neck list = (head . tail) list
neck = head . tail

nnegatives :: [Int] -> Int
nnegatives = length . filter (< 0)