[SOLVED] CS Haskell PowerPoint Presentation

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)]

Lets 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 well 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 3Output function: function that applies to the members of the list we indicate. Another way to map!The pipe separates input list from output functionThe input set: a generator list and a variable that represents the elements that will be drawn from that listThis 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, continuedList 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 weve 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, continuedTo 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, continuedList comprehensions can use multiple generator lists:[x^y | x <- [1..10], y <- [2,3]][1,1,4,8,9,27,16,25,125]Whats 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 comprehensionsclosely follow setbuilder notation from math19Using List Comprehensions in FunctionsYou 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.AnswersFunction CompositionA 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 CompositionYou can compose functions in Racket, too:(define (find3MostFreqWds ls)(take (sortListDescFreq (frequencyLs (sortListAlphab (mapToLowercase ls)))) 3))In Haskell, theres 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]true1.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.Integralincludes only integral (whole) numbers. In this typeclass areIntandInteger. Integer is an arbitrary precision type: it will hold any number no matter how big, up to the limit of your machines 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