» CS 330 Lecture 19 – Functions and Lists

CS 330 Lecture 19 – Functions and Lists

March 15, 2017 by Chris Johnson. 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:

Parallelogram
Write a function pcomplete that completes a parallelogram. Suppose you are given three points in 2D space. Compute a fourth that when combined with the others yields a paralellogram. Recall this common structure for defining functions:
```
f p1 p2 = some-expr
  where l1 = some-expr
        l2 = some-expr
```
Pattern matching is encouraged.

And here are the problems we’ll solve:

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)
```
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 : []
```
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!

Sincerely,