Lecture: Haskell

Dear students:

A new language is upon us. New languages require us to regress to infancy. The world around is filled with expressions that we can't understand, and we are uncomfortable. Today we embrace that discomfort and start babbling in Haskell by solving some programming challenges together.

Inventory

To solve these problems, we'll to make use of some of Haskell's builtin functions. These are the ones from the reading plus a few more that you might find useful:

head items: get first element of a list
tail items: get all elements but the head of a list
take n items: get first n elements of a list
drop n items: get list without first n elements
fst pair: get first component of a 2-tuple
snd pair: get second component of a 2-tuple
item : items: prepend a new head onto a list
these ++ those: concatenate two lists
div a b: integer division
mod a b: integer modulus

PairSum

Write a function pairSum that, given a pair of numbers, returns their sum. For example:

pairSum (5, 6) → 11
pairSum (-3, -6) → -9
pairSum (0, 0) → 0

Here's one way to write it:

Haskell

pairSum :: (Int, Int) -> Int
pairSum pair = fst pair + snd pair

pairSum :: (Int, Int) -> Int
pairSum pair = fst pair + snd pair

Maybe you prefer local variables?

Haskell

pairSum :: Num a => (a, a) -> a
pairSum pair = x + y
  where x = fst pair
        y = snd pair

pairSum :: Num a => (a, a) -> a
pairSum pair = x + y
  where x = fst pair
        y = snd pair

What happens if we write pairSum (3.0, -2.0)? Our definition only allows pairs of Int to be added. We'd have to make a separate pairSumDouble to add a pair of Double. Or we could loosen up the type signature. Instead of targeting Int, we target wildcard a:

Haskell

pairSum :: (a, a) -> a

pairSum :: (a, a) -> a

We didn't have to use a. Any lowercase letter is legal. Just as in Java. We don't have to use T for a generic type. This is too loose, however. Not just any type supports adding. Types that support addition fall under the Num typeclass (the “numbrella”). We must put a constraint on a:

Haskell

pairSum :: Num a => (a, a) -> a

pairSum :: Num a => (a, a) -> a

Now we have a polymorphic pairSum.

Majority

Write a function majority that, given a population as an Int, returns the number of people that are needed to count as a majority in that people. For example:

majority 100 → 51
majority 99 → 50
majority 98 → 50
majority 1 → 1
majority 2 → 2

Here's one solution:

Haskell

majority :: Int -> Int
majority n = div n 2 + 1

majority :: Int -> Int
majority n = div n 2 + 1

Recall that Haskell operators and functions are the same thing. Functions default to prefix fixity, but they can be moved to an infix position with backticks:

Haskell

majority :: Int -> Int
majority n = n `div` 2 + 1

majority :: Int -> Int
majority n = n `div` 2 + 1

I don't find this terribly readable, but there are occasions in which changing the fixity is handy. See partial application, which we'll discuss in a later chapter.

Neck

Write a function neck that, given a list, returns its second element. For example:

neck [5, 3, 1] → 3
neck "guarantee" → 'u'
neck [10..20] → 11
neck [0,5..100] → 5

Here's one solution:

Haskell

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

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

Parentheses are annoying to balance and can make code hard to read. Haskell provides an alternative in $. It yields the value of everything to its right, allowing expressions of the form f (g (x)) to be rewritten as f $ g $ x.

Haskell

neck :: [a] -> a
neck xs = head $ tail xs

neck :: [a] -> a
neck xs = head $ tail xs

Write a function next that accepts two numbers in an arithmetic sequence and returns the next number. For example:

next 5 8 → 11
next 2 2 → 2
next 10 0 → -10
next 5.3 5.4 → 5.5

Here's one solution:

Haskell

next :: Num a => a -> a -> a
next a b = b + delta
  where delta = b - a

next :: Num a => a -> a -> a
next a b = b + delta
  where delta = b - a

Big Head

Write a function bigHead that, given a pair of lists, returns the one that has a bigger first element. For example:

bigHead ("bless", "other") → "other"
bigHead ([1..5], [3, 7]) → [3, 7]
bigHead ([-10, -20, -30], [-20, -10, -30]) → [-10, -20, -30]

Here's one solution:

Haskell

bigHead :: Ord a => ([a], [a]) -> [a]
bigHead pair = if a0 >= b0 then a else b
  where
    a = fst pair
    b = snd pair
    a0 = head a
    b0 = head b

bigHead :: Ord a => ([a], [a]) -> [a]
bigHead pair = if a0 >= b0 then a else b
  where
    a = fst pair
    b = snd pair
    a0 = head a
    b0 = head b

Slice

Write a function slice that, given a list, a starting index, and an ending index, returns the sublist between the given indices. For example:

slice 2 6 "romania" → "mania"
slice 0 2 [9, 3, 2, 11, 8] → [9, 3, 2]

Here's one solution:

Haskell

slice :: Int -> Int -> [a] -> [a]
slice from to xs = take n afterFroms
  where
    afterFroms = drop from xs
    n = to - from + 1

slice :: Int -> Int -> [a] -> [a]
slice from to xs = take n afterFroms
  where
    afterFroms = drop from xs
    n = to - from + 1

Abbreviate

Write a function abbreviate that, given a string and an integer length, it returns the string intact if its short or abbreviated if its long. Shortness is determine by the length parameter. For example:

abbreviate "muenster" 4 → "m...r"
abbreviate "listen" 6 → "listen"

Here's one solution:

Haskell

abbreviate :: String -> Int -> String
abbreviate text n =
  if length text <= n
    text
  else
    [head text] ++ "..." ++ [last text]

abbreviate :: String -> Int -> String
abbreviate text n =
  if length text <= n
    text
  else
    [head text] ++ "..." ++ [last text]

Quadrant

Write a function quadrant that accepts a Cartesian coordinate pair of numbers. It returns "I", "II", "III", or "IV" to indicate the pairs quadrant. If the pair doesn't lie in a quadrant, it returns "?". For example:

quadrant (1, 2) → "I"
quadrant (0, 0) → "?"
quadrant (3, -10) → "IV"

Here's one solution:

Haskell

quadrant :: (Double, Double) -> String
quadrant xy
  | x > 0 && y > 0 = "I"
  | x < 0 && y > 0 = "II"
  | x < 0 && y < 0 = "III"
  | x > 0 && y < 0 = "IV"
  | otherwise = "?"
  where
    x = fst xy
    y = snd xy

quadrant :: (Double, Double) -> String
quadrant xy
  | x > 0 && y > 0 = "I"
  | x < 0 && y > 0 = "II"
  | x < 0 && y < 0 = "III"
  | x > 0 && y < 0 = "IV"
  | otherwise = "?"
  where
    x = fst xy
    y = snd xy

Main

In a sense, Haskell is two languages: one for its pure functions and one for the messier stuff like printing and running sequences of statements. Writing functions is the clean and beautiful part of Haskell, but sometimes we do need a main routine to set the whole process in motion. Let's take a peak at some very simple mains. The reading will go into more detail about how they work.

Suppose we want a program that prompts the user for the names of two people and then prints a message confessing their love. We'd write it like this:

Haskell

main = do
  first <- getLine
  second <- getLine
  let confession = first ++ "❤️" ++ second
  putStrLn confession

main = do
  first <- getLine
  second <- getLine
  let confession = first ++ "❤️" ++ second
  putStrLn confession

There are two “assignment” operators here. The <- is for assigning messy data gained from impure I/O calls. The let and = are for assigning pure values.

Suppose we want a program that gives us a list of integers between two values. We'd write it like this:

Haskell

main = do
  startString <- getLine
  endString <- getLine
  let start = read startString :: Int
  let end = read endString :: Int
  let xs = [start..end]
  print xs

main = do
  startString <- getLine
  endString <- getLine
  let start = read startString :: Int
  let end = read endString :: Int
  let xs = [start..end]
  print xs

The read function is the opposite of show. It's like parseInt or parseDouble, but it doesn't have a type baked in. It's polymorphic. So we have to steer the type with the :: operator. We can read it as “as”.

TODO

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

Tomorrow I've got a day of phone interviews. My office hours will need to end at 10 AM.

The next chapter—on immutability and I/O—is up. There's also the chapter on expressions that I recommended you read for today. The quizzes cover both of these chapters.

Exam scores will go in Canvas soon, but you already know them. Canvas will not ever show you your total grade because I turn that off. Its calculation is misleading because it doesn't handle missing scores well and doesn't take the higher of your quiz scores. Calculating it yourself is well within your power. Use a spreadsheet.

Start learning Haskell. If you like profanity, check out Learn You a Haskell for Great Good! Share useful videos or materials on Discord. Note that some Haskell material can get quite deep. For this class, we only care about its interesting type system, its mechanisms for building functions, and its means of operating under immutability. We will not explore functors, monads, and other advanced abstractions.

See you next time.

Sincerely,

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

Latin may be dead Yet people keep learning it To speak with its ghosts

← Evaluation Order

Dear Computer

Lecture: Haskell

Inventory

PairSum

Majority

Neck

Next

Big Head

Slice

Abbreviate

Quadrant

Main

TODO