Recap
We have integers, floating point numbers, characters, and strings.
What's new?
Lists are collections of a single type of data.
What does a list look like?
A simple list of integers looks like:
| code: |
[1, 2, 3, 4] |
Of course, a simple range like this can be more succinctly represented as:
| code: |
[1 .. 4] |
How is a list defined?
This really deals with the very first operator/function we'll see for dealing with lists.
| code: |
1 : [2, 3, 4] |
Yields:
| code: |
[1, 2, 3, 4] |
So, really, we can rewrite that as:
| code: |
1 : 2 : 3 : 4 : [] |
| code: |
[] |
Of course, is an empty list.
That's nice, but...
Lists are roughly analogous to arrays in other languages, and there are similar operations available.
Finding the length of a list:
| code: |
length ["hello", "world"] |
Getting the first element:
| code: |
head [42.3, 57.6, 98.2] |
Getting everything else:
| code: |
tail [42.3, 57.6, 98.2] |
Adding two lists together:
| code: |
[1, 2, 3] ++ [4, 5] |
Finding any element in a list (in this case, the 3rd):
| code: |
[1 .. 5] !! 2 |
Finding if an element is in a list:
| code: |
elem "foo" ["foo", "bar", "baz"] |
Or, using the infix form of any function which takes two arguments:
| code: |
"foo" `elem` ["foo", "bar", "baz"] |
Which should read as "is foo an element of this list".
Now, if we want to apply a function to each element in a list, to square each:
| code: |
(** 2) `map` [1 .. 6] |
Or say we want to filter a list:
| code: |
(> 2) `filter` [1 .. 4] |
Another look at the last two
Haskell offers a special bit of syntactic sugar for list operations, called the list comprehension. Python borrowed this feature.
Squaring 1 through 6 can look like:
| code: |
[x ** 2 | x <- [1 .. 6]] |
And the filter operation can look like:
| code: |
[x | x <- [1 .. 4], x > 2] |
What about loops?
Loops and lists (or arrays) usually go hand in hand. Haskell has no looping construct. So how is "map" possible?
Recursion
Let's consider the map function again.
How do you suppose they do that?
Well, they apply the function to the first item in the list, then recursively do the same to the rest of the list. Obviously the result of mapping a function to an empty list is another empty list.
| code: |
map _ [] = [] |
The _ in this case indicates an argument, but one whose value we don't care about. In this case we're going to get the same result, no matter what function we pass to map.
| code: |
map f (x:xs) = f x : map f xs |
The function argument in this case is "f".
| code: |
(x:xs) |
Might look a bit familiar. It has that ":" we associated with building a list. Indeed, x is the first element of a list, and xs is the rest of the list.
| code: |
f x : map f xs |
We call the function f with argument x, and merge it to the list returned by calling the function recursively for the rest of the list.
So, breaking down:
| code: |
map (** 2) [1, 2, 3, 4, 5] |
We get:
| code: |
1 ** 2 : (2 ** 2 : (3 ** 2 : (4 ** 2 : (5 ** 2 : ([])))))
1 ** 2 : 2 ** 2 : 3 ** 2 : 4 ** 2 : 5 ** 2 : [] 1 : 4 : 9 : 16 : 25 : [] [1, 4, 9, 16, 25] |
Take another look
| code: |
map _ [] = []
map f (x:xs) = f x : map f xs |
This is a basic pattern you'll find when it comes to recursion, and it provides all the power of a loop in an imperative language.
Another example: sum
The problem: given a list of numbers, find their sum.
First analysis: summing an empty list will always give us zero.
| code: |
sumList [] = 0 |
Second analysis: we can calculate the sum by adding the first element of the list to the sum of the rest of the list.
| code: |
sumList (x:xs) = x + sumList xs |
| code: |
sumList [1 .. 4] |
Breaks down to:
| code: |
1 + (2 + (3 + (4 + (0))))
1 + (2 + (3 + (4))) 1 + (2 + (7)) 1 + (9) 10 |
Now a different take on this
So far we've been doing pretty simple recursion, and handling the recursion ourselves. There's a method which avoids this, called "folding".
Consider a deck of 52 cards which can represent a list metaphorically. They each have a number on them. To count them, we could add the top two cards and put a card with that value back on top of the deck. We then do the same thing all over again until we're left with one card with the final result.
One of the things we need in a fold is a function which takes two arguments which represent the two cards. Since our list might only have one element, we provide a starting value for the first time around. For a sum, we should start out with an intial value of zero.
| code: |
foldl (\a b -> a + b) 0 [1 .. 4] |
| code: |
\a b -> a + b |
Is a function. The only thing it lacks is a name.
Of course, we can simplify this even further by realizing that we don't need to construct the extra function.
| code: |
foldl (+) 0 [1 .. 4] |
And we can partially apply the function to create a general sumList function.
| code: |
sumList = foldl (+) 0 |
Or even:
| code: |
sumList = (+) `foldl`0 |
One last thing
The "l" in "foldl" stands for "left". It starts on the left side of a list and works its way to the other end. The "foldr" function works identically except that it works through the list in the opposite direction.
Take some time...
I realize all of this will take some time to digest, so sit back and think about it a bit. Another good idea is to try the code I've posted to see that as weird as it looks, it works.
