teaching machines

CS 330 Lecture 19 – Functions and Lists

March 15, 2017 by . Filed under cs330, lectures, spring 2017.

Dear students,

Today we solve more problems in Haskell together. Along the way we will discover some of the peculiarities of functional programming, like the supremacy of linked lists.

First, an exercise to complete with a neighbor:

And here are the problems we’ll solve:

  1. Let’s write a parallelogram completer. Suppose you are given three points. Find a fourth that joins up with the three to yield a parallelogram.
    parallelogram (x1, y1) (x2, y2) (x3, y3) = (x, y)
      where x = (x2 + x3 - x1)
            y = (y2 + y3 - y1)
  2. Let’s write a function to generate initials for someone with three names. Not everyone has three names, so this function probably will disenfranchise them. If you are designing a website, consider providing just one textbox for the name. We could write it like this:
    initials first middle last = f : m : l : []
      where f = head first
            m = head middle
            l = head last
    But suppose we wanted to force the letters to lowercase. Data.Char.toLower to the rescue:
    initials first middle last = f : m : l : []
      where f = toLower (head first)
            m = toLower (head middle)
            l = toLower (head last)
    We used the parentheses to force associativity. Parentheses are not our only option in Haskell. Anytime we have code like
    f (expr p1 p2 p3)
    we can rewrite it as
    f $ expr p1 p2 p3
    Consider this expression, which is a silly way of extracting out the digit in the 10s place:
    head (tail (reverse (show 9876)))
    That’s more parentheses that we might like to write. We can use the $ to simplify:
    head $ tail $ reverse $ show 9876
    In the case of initials, we could write
    initials first middle last = f : m : l : []
      where f = toLower $ head first
            m = toLower $ head middle
            l = toLower $ head last
    Still, this is a lot of repetition. We’re apply toLower in the same way to each letter. If we need to apply the same operation to every element of a collection, what can we do? We have two options. One is called map and we will discuss in great detail later. The other way you read about for today: a list comprehension. Let’s bundle the letters up in a list, and then generate a new list from that:
    initials first middle last = [toLower c | c <- fml]
      where f = toLower $ head first
            m = toLower $ head middle
            l = toLower $ head last
            fml = f : m : l : []
  3. What do you think? Are there more integer numbers than there are even numbers? John Green wrote this in The Fault in Our Stars:
    There are infinite numbers between 0 and 1. There’s .1 and .12 and .112 and an infinite collection of others. Of course, there is a bigger infinite set of numbers between 0 and 2, or between 0 and a million. Some infinities are bigger than other infinities. A writer we used to like taught us that. There are days, many of them, when I resent the size of my unbounded set. I want more numbers than I’m likely to get, and God, I want more numbers for Augustus Waters than he got. But, Gus, my love, I cannot tell you how thankful I am for our little infinity. I wouldn’t trade it for the world. You gave me a forever within the numbered days, and I’m grateful.
    Early 1900s mathematician Georg Cantor said that infinity indeed had levels, but two infinite sets were at the same level if there was a one-to-one mapping between them. Is there a relationship between the integers and the even numbers? If we can write a list comprehension to turn one into the other, than they live in the same level. And we can:
    evens upto = [2 * n | n <- [0..upto]]
    We stick with the positives. Speaking of infinities, we can actually produce infinite things in Haskell:
    evens = [2 * n | n <- [0..]]
    This only works because Haskell doesn’t evaluate most expressions until the value is absolutely needed. It is lazy. We must careful to never need everything. We can use take to specify how many evens we need:
    take $ evens 100

See you next time!