Lecture: Embracing Functions

Dear students:

In this chapter you read about four different ways of making functions in Haskell: named definitions, lambdas, partial application, and composition. These four tools are like the hammer and saw used by a carpenter. You use them to assemble functions into algorithms. Today we'll employ them to solve a handful of programming challenges. We'll also see pattern matching and revisit the canonical higher-order functions map, filter, and fold.

Warmup

Let's start with a warmup. With your tablemates, simplify the Haskell snippets below using partial application, composition, lambdas, and pattern matching.

1. content_copy

   curl (dye (trim hair))

   curl (dye (trim hair))

2. content_copy

   map (\x -> x + x + x) xs

   map (\x -> x + x + x) xs

3. content_copy

   startsWith letter text = letter == head text
   startsWithC text = startsWith 'c' text
   spicesC spices = filter startsWithC spices

   startsWith letter text = letter == head text
   startsWithC text = startsWith 'c' text
   spicesC spices = filter startsWithC spices

4. content_copy

   twiceWidth dims = (2 * fst dims, snd dims)

   twiceWidth dims = (2 * fst dims, snd dims)

5. content_copy

   half x = div x 2
   halves xs = map half xs

   half x = div x 2
   halves xs = map half xs

6. content_copy

   firstOfHead pairs = fst $ head pairs

   firstOfHead pairs = fst $ head pairs

Head

In the most recent lab, you wrote the head utility. Likely it was more complex than it needed to be. That's because you hadn't yet learned about pattern matching and higher-order functions! Now that you have them in your repertoire, you can rewrite it like this:

import System.Environment

main = do
  file : nString : _ <- getArgs
  text <- readFile file
  let n = read nString :: Int
  mapM_ putStrLn $ take n $ lines text

import System.Environment

main = do
  file : nString : _ <- getArgs
  text <- readFile file
  let n = read nString :: Int
  mapM_ putStrLn $ take n $ lines text

See that gauntlet on the last line? We could have written that as this composition:

(mapM_ putStrLn . take n . lines) text

(mapM_ putStrLn . take n . lines) text

Map, Filter, and Fold

Before we dive into more complex programs, let's solve a few higher-order function problems together. Use map, filter, and foldl to solve these challenges:

I find map operations easiest to write. The time conversion is a map, and here's how I'd write it:

millisToSeconds :: [Double] -> [Double]
millisToSeconds millis = map (* 1000) millis

millisToSeconds :: [Double] -> [Double]
millisToSeconds millis = map (* 1000) millis

If I recognize that I'm just building a function from other functions, I can assign to millisToSeconds rather than “define” a function:

millisToSeconds = map (* 1000)

millisToSeconds = map (* 1000)

This is point-free style. I've partially applied the map function. We're still waiting on the list parameter.

Filter is the next easiest. We want to take the characters of the string that are not in "aeiou". The elem function tests if a value is in a list. That leads us to this point-free definition:

consonants :: String -> String
consonants = filter (\c -> not $ elem c "aeiou")

consonants :: String -> String
consonants = filter (\c -> not $ elem c "aeiou")

Lastly we have the fold operation. We want to sum up the areas, so we write a lambda that destructures a rectangle, computes its area, and tacks it on to the accumulator:

area :: [(Double, Double)] -> Double
area = foldl (\accum (w, h) -> accum + w * h) 0

area :: [(Double, Double)] -> Double
area = foldl (\accum (w, h) -> accum + w * h) 0

Advent of Code 2015, Day 1

Write a program that solves Advent of Code 2015, Day 1. Accept the input text as a command-line argument.

Here's one possible solution:

import System.Environment

deliver :: String -> Int -> Int
deliver directions floor =
  if directions == "" then
    floor
  else
    deliver rest floor'
    where
      first = head directions
      rest = tail directions
      offset = if first == '(' then 1 else -1
      floor' = floor + offset

main = do
  args <- getArgs
  let directions = head args
  print $ deliver directions 0

import System.Environment

deliver :: String -> Int -> Int
deliver directions floor =
  if directions == "" then
    floor
  else
    deliver rest floor'
    where
      first = head directions
      rest = tail directions
      offset = if first == '(' then 1 else -1
      floor' = floor + offset

main = do
  args <- getArgs
  let directions = head args
  print $ deliver directions 0

Note that this follows the fold pattern. We'd save ourselves some effort and recursive thinking if we used foldl. However, many fold operations have already been canonized for us. Here the fold sums up the 1s and -1s, so we can use Haskell's sum function:

import System.Environment

main = do
  directions : _ <- getArgs
  let offsets = map (\p = if p == '(' then 1 else -1) directions
  let floor = sum offsets
  print floor

import System.Environment

main = do
  directions : _ <- getArgs
  let offsets = map (\p = if p == '(' then 1 else -1) directions
  let floor = sum offsets
  print floor

parseInts

In many forthcoming problems, we are going to read in a bunch of whole numbers from a file. We'll need to convert a list of String to a list of Int. Let's write a helper method to perform this collective conversion. To make it reusable, we'll put it in a module in Utilities.hs:

module Utilities where

parseInts :: [String] -> [Int]
parseInts = map read

module Utilities where

parseInts :: [String] -> [Int]
parseInts = map read

Advent of Code 2018, Day 1

Write a program that solves Advent of Code 2018, Day 1. Accept a file name containing the input as a command-line argument.

Here's one possible solution:

import System.Environment
import Utilities

main = do
  first : _ <- getArgs
  text <- readFile first
  let strippedText = filter (/= '+') text
  let frequencies = parseInts $ lines strippedText
  print $ sum frequencies

import System.Environment
import Utilities

main = do
  first : _ <- getArgs
  text <- readFile first
  let strippedText = filter (/= '+') text
  let frequencies = parseInts $ lines strippedText
  print $ sum frequencies

Advent of Code 2022, Day 1

Write a program that solves Advent of Code 2022, Day 1. Accept a file name containing the input as a command-line argument.

Here's one possible solution:

import System.Environment
import Data.List.Split
import Utilities

main = do
  path : _ <- getArgs
  text <- readFile path
  let chunks = map lines $ splitOn "\n\n" text
  let loads = map (sum . parseInts) chunks
  let max = maximum loads
  print max

import System.Environment
import Data.List.Split
import Utilities

main = do
  path : _ <- getArgs
  text <- readFile path
  let chunks = map lines $ splitOn "\n\n" text
  let loads = map (sum . parseInts) chunks
  let max = maximum loads
  print max

Count

Ruby has a nice method named count that applies a predicate to a collection and reports how many items pass the predicate. Haskell doesn't have this method. How can we write it?

Here's one possible solution:

count :: (a -> Bool) -> [a] -> Int
count predicate = length . filter predicate

count :: (a -> Bool) -> [a] -> Int
count predicate = length . filter predicate

Advent of Code 2021, Day 1

Write a program that solves Advent of Code 2021, Day 1. Accept a file name containing the input as a command-line argument.

Here's one possible solution:

import System.Environment
import Utilities

main = do
  path : _ <- getArgs
  text <- readFile path
  let readings = parseInts $ lines text
  let pairs = zip readings $ tail readings
  let nbiggers = count (\(a, b) -> b > a) pairs
  print nbiggers

import System.Environment
import Utilities

main = do
  path : _ <- getArgs
  text <- readFile path
  let readings = parseInts $ lines text
  let pairs = zip readings $ tail readings
  let nbiggers = count (\(a, b) -> b > a) pairs
  print nbiggers

Sorting

We frequently need to sort collections. Haskell has the sort function that sorts a list of Ord elements, but sometimes we have to sort elements by custom criteria. If that's the case, we can write our own compare function that returns an Ordering. Then we pass the function and our list to sortBy.

Write a program that sorts a list of rectangles by their area. Each rectangle is a pair of its dimensions.

Here's one possible solution:

import Data.List

orderRectangles (w1, h1) (w2, h2)
  | area1 < area2 = LT
  | area1 > area2 = GT
  | otherwise = EQ
  where
    area1 = w1 * h1
    area2 = w2 * h2

main = do
  let rects = [(5, 6), (4, 7)]
  let sortedRects = sortBy orderRectangles rects
  mapM_ print sortedRects

import Data.List

orderRectangles (w1, h1) (w2, h2)
  | area1 < area2 = LT
  | area1 > area2 = GT
  | otherwise = EQ
  where
    area1 = w1 * h1
    area2 = w2 * h2

main = do
  let rects = [(5, 6), (4, 7)]
  let sortedRects = sortBy orderRectangles rects
  mapM_ print sortedRects

But we can do better by knowing the standard library. The comparing function of Data.Ord lets us pass a function to compute the sorting criteria. It applies that function to the two values and returns the Ordering for us. Here's a simpler version:

import Data.List
import Data.Ord

orderRectangles = comparing (\(w, h) -> w * h)
main = do
  let rects = [(5, 6), (4, 7)]
  let sortedRects = sortBy orderRectangles rects
  mapM_ print sortedRects

import Data.List
import Data.Ord

orderRectangles = comparing (\(w, h) -> w * h)
main = do
  let rects = [(5, 6), (4, 7)]
  let sortedRects = sortBy orderRectangles rects
  mapM_ print sortedRects

TODO

Here's your list of things to do before we meet next:

See you next time.