PowerPoint Presentation
Let us pray.
Today:
Pattern matching on lists (review)
List comprehensions
Composed functions
Useful list features in Haskell
Make a list with a range:
[1..10] is same as [1,2,3,4,5,6,7,8,9,10]
But, do [10,9..1] for [10,9,8,7,6,5,4,3,2,1]
If a pattern can be achieved by adding or subtracting a number, you can specify a step:
[2,4..10] is same as [2,4,6,8,10]
[1,3..11] is same as [1,3,5,7,9,11]
Useful built-in functions on lists:
sum[1,2,3] -> 6
product[2,3,4] -> 24
elem 4 [1..10] -> True
take 3 [1..10] -> [1,2,3]
drop 3 [1..10] -> [4,5,6,7,8,9,10]
Pattern Matching on Lists
[a, b, c] = a : b : c : []
(x:xs)
Pattern Matching on Lists
[a, b, c] = a : b : c : []
(x:xs)
myLength :: Num a => [b] -> a
myLength [] = 0
myLength (x:xs) = 1 + myLength xs
Head of the list
consed onto
the tail of the list
Implementing zip: myZip
zip is a built-in function that will create tuples from two lists, such that the indices of the elements are the same:
> zip [1,4,9,16,25] [1,8,27,64,125]
[(1,1), (4,8), (9,27), (16,64), (25,125)]
Let’s implement our own zip, called myZip.
Implementing zip: myZip
So long as both lists are not empty, we should cons a tuple of the heads of the two lists:
myZip (x:xs) (y:ys) = (x,y) : myZip xs ys
The base case will be reached when we reach the end of either of the input lists, upon which we’ll return an empty list:
myZip [] _ = []
myZip _ [] = []
Solution
Pattern Matching on Lists: uncouple
How would we write a function that takes a list of pairs of the same type, and creates a list of uncoupled items?
uncouple :: [(a,a)] -> [a]
uncouple [(1,2),(3,4),(5,6)]
[1,2,3,4,5,6]
Pattern Matching on Lists: uncouple
Base case:
uncouple [] = []
Recursive case:
uncouple (????) = a : b : uncouple c
The challenge here is to think of how to express the “head of the list” and the “tail of the list” as a pattern, especially given that we have a list of tuples.
Pattern Matching on Lists: uncouple
Solution:
Pattern Matching on Lists: myElem
elem is a built-in function that returns “true” if the argument can be found in the list:
elem 3 [1,2,3,4,4,6]
True
elem “hi” [“abc”, “boo”, “bar”, “hi” “fizz”]
True
How would you implement myElem using pattern matching?
Pattern Matching on Lists: myElem
myElem :: Eq t => t -> [t] -> Bool
myElem _ [] = False
myElem x (y:ys)
| x == y = True
| otherwise = myElem x ys
List Comprehensions
List Comprehensions
List comprehensions are a means of generating a new list from a list or lists. The output of a list comprehension is always a new list.
They come directly from the concept of set comprehensions in math, including similar syntax. Another way Haskell is “mathy”!
A simple list comprehension:
[x^2 | x <- [1..10]]
1 2 3
Output function: function that applies to the members of the list we indicate. Another way to map!
The pipe separates input list from output function
The input set: a “generator” list and a variable that represents the elements that will be drawn from that list
This list comprehension produces a new list that includes the square of every number from 1 to 10: [1,4,9,16,25,36,49,64,81,100]
List comprehensions, continued
List comprehensions can contain predicates, which make list comprehensions act like filters, because the predicate limits the elements drawn from the generator list:
[x^2 | x <- [1..10], mod x 2 == 0]
Here we’ve specified that the only elements to take from the generator list as x are those that are even.
[4, 16, 36, 64, 100]
You can have multiple predicates, separated by commas.
List comprehensions, continued
To be clear, the output function could simply be the identity function:
[x | x <- [1..10], mod x 2 == 0]
[2,4,6,8,10]
List comprehensions, continued
List comprehensions can use multiple generator lists:
[x^y | x <- [1..10], y <- [2,3]]
[1,1,4,8,9,27,16,25,125]
What’s going on here? [12, 13, 22, 23, 32, 33, 42, 43 etc.]
You can still add predicates with multiple generators:
[x^y | x <- [1..10], y <- [2,3], mod x 2 == 0]
[4,8,16,64,36,216,64,512,100,1000]
[x * 2 | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]
[x | x <- [10..], x*x < 200]
[10,11,12,13,14]
[x | x <- [1..200], mod x 53 == 0]
[53,106,159]
List comprehensions
closely follow set
builder notation
from math
19
Using List Comprehensions in Functions
You can define functions that take a list or several lists as arguments and return the result of a list comprehension:
> evens :: [Int] -> [Int]
> evens ls = [x | x <- ls, mod x 2 == 0]
> evens [1..10]
[2,4,6,8,10]
Participation Quiz:
List Comprehensions
List Comprehensions, Reviewed
[x^y + a | x <- [1..3], a <- [3,4], y <- [2,3]]
What order?
One possibility:
12 + 3, 12 + 4, 13 + 3, 13 + 4, 22 + 3, 22 + 4, 23 + 3, 23 + 4 (etc)
Another possibility:
12 + 3, 13 + 3, 12 + 4, 13 + 4, 22 + 3, 23 + 3, 22 + 4, 23 + 4 (etc)
List Comprehensions, Reviewed
[x^y + a | x <- [1..3], a <- [3,4], y <- [2,3]]
What order?
Answer:
12 + 3, 13 + 3, 12 + 4, 13 + 4, 22 + 3, 23 + 3, 22 + 4, 23 + 4 (etc)
Keep the innermost values constant and vary the outer values.
Answers
Function Composition
A “composed” function passes the result of applying one function as an argument to another function.
f ° g
(f (g x))
h(x) = (f (g x))
Function Composition
You can compose functions in Racket, too:
(define (find3MostFreqWds ls)
(take (sortListDescFreq (frequencyLs (sortListAlphab (mapToLowercase ls)))) 3))
In Haskell, there’s a clean syntax for composing functions, using this “dot” operator:
(p . f . g ) x = (p (f (g x)))
(even.negate.sum) [1,2,3,4]
true
1. sum [1,2,3,4] -> 10
2. negate 10 -> -10
3. even -10 -> true
Function Composition
f = even.negate.sum
f [1,2,3,4]
true
What is the type of f?
Well, what type does sum take, what type does even take, and what does even return?
f :: Integral a => [a] -> Bool
Num p => [p] -> p
sum [] = 0
sum (x:xs) = x + sum xs
Sum takes Nums, while Even takes only whole numbers (Integrals), a subcategory of Nums. Integral includes only integral (whole) numbers. In this typeclass are Int and Integer. “Integer” is an arbitrary precision type: it will hold any number no matter how big, up to the limit of your machine’s memory. “Int” is the more common 32 or 64 bit integer.
27
What would happen?
(sum.map even.filter (<100)) [1..200]
Type error: sum expects a list of Nums, not Booleans.
(sum.map (+ 1).filter (<100)) [1..200]
5049
/docProps/thumbnail.jpeg