% CS 340: Programming Paradigms and Patterns
% Lect 04 - Lists
% Michael Lee
> module Lect.Lect04Complete where
> import Data.Char
Lists
=====
Agenda:
- The List type
- Constructing lists
- Syntactic sugar
- List comprehensions
- Common list functions
- List processing functions
- Pattern matching
- Structural recursion
The List type
-------------
Haskell's built-in list type might be defined something like this:
[a] = [] | a : [a]
Read as: A list containing instances of type 'a' ([a]) is either an empty
list ([]) or an instance of type 'a' followed by ':' and a list
containing instances of type 'a' ([a]).
Takeaways:
- a list is defined recursively, i.e., in terms of itself
- the list type is polymorphic
- lists are homogeneous (all elements of a given list are of the same type)
Constructing lists
------------------
`[]` and `:` are examples of value constructors (aka data constructors); i.e.,
they are functions that return values of the associated type (in this case, the
polymorphic list type).
`[]` is called "empty list" and the `:` operator is called "cons":
[] :: [a]
(:) :: a -> [a] -> [a]
We can call `:` in prefix form to build lists:
(:) 1 []
(:) 1 ((:) 2 [])
(:) 1 ((:) 2 ((:) 3 []))
But we usually prefer to use `:` in infix form:
1 : (2 : (3 : []))
And `:` is right-associative, so we can just write:
1 : 2 : 3 : []
E.g., lists of integers:
[]
100 : []
20 : -3 : 8 : -15 : []
E.,g., lists of Chars (aka strings):
[]
'a' : []
'h' : 'e' : 'l' : 'l' : 'o' : []
---
Functions that construct lists typically:
- operate recursively
- use one of the list value constructors (`[]` or `:`) in each recursive call
- when using `:`, add one element to the front of the list and use recursion
to construct the rest of the list
- use `[]` in the base (non-recursive) case, if it exists
> replicate' :: Int -> a -> [a]
> replicate' 0 _ = []
> replicate' n x = x : replicate' (n-1) x
>
> enumFromTo' :: (Ord a, Enum a) => a -> a -> [a]
> enumFromTo' x y | x <= y = x : enumFromTo' (succ x) y
> | otherwise = []
>
> -- and now for some infinite lists
>
> ones :: [Int]
> ones = 1 : ones
>
> repeat' :: a -> [a]
> repeat' x = x : repeat' x
>
> enumFrom' :: Enum a => a -> [a]
> enumFrom' x = x : enumFrom' (succ x)
Note: to limit the number of values drawn from an infinite list, we can use
`take` (we'll implement it later)
Syntactic sugar
---------------
Instead of constructing lists with `:`, Haskell gives us syntactic shortcuts:
E.g., for simple itemized lists, [...]
[1,2,3,4,5,6,7,8,9,10] == 1:2:3:4:5:6:7:8:9:10:[]
[[1, 2, 3], [4, 5, 6]] == (1:2:3:[]) : (4:5:6:[]) : []
[(2, True), (1, False)] == (2,True) : (1,False) : []
E.g., for lists of characters (string), "...":
"hello world" == 'h':'e':'l':'l':'o':[]
["hello", "world"] == ('h':'e':'l':'l':'o':[]) : ('w':'o':'r':'l':'d':[]) : []
E.g., for types that are instances of `Enum`, [I..J] and [I,J..K] and [I..]:
[1..10] == [1,2,3,4,5,6,7,8,9,10]
['a'..'z'] == "abcdefghijklmnopqrstuvwxyz"
[2,4..10] == [2,4,6,8,10]
[10,9..1] == [10,9,8,7,6,5,4,3,2,1]
E.g., for infinite lists of `Enum` types, [I..] and [I,J..]
[1..] == enumFrom 1
[3,6..] == enumFromThen 3 6
List comprehensions
-------------------
Syntax:
[ Expression | Generator, ... , Predicate, ... ]
- which produces a list of values computed by the Expression
- where each Generator is of the form "var <- List"
- and each Predicate is a Boolean expression
- you can also use `let` to create local vars (without `in`)
E.g.,
> evens = [2*x | x <- [1..]]
>
> evens' = [x | x <- [1..], x `mod` 2 == 0]
>
> sudokuBoxes = [[[r,c] | r <- rs, c <- cs] | rs <- ["ABC", "DEF", "GHI"],
> cs <- ["123", "456", "789"]]
>
> integerRightTriangles p = [(a,b,c) | a <- [1..p],
> b <- [a..(p-a)],
> let c = p-(a+b),
> a^2 + b^2 == c^2]
>
> factors :: Integral a => a -> [a]
> factors n = [f | f <- [1..n], n `mod` f == 0]
>
> cartesianProduct :: [a] -> [b] -> [(a,b)]
> cartesianProduct xs ys = [(x,y) | x <- xs, y <- ys]
>
> concat' :: [[a]] -> [a]
> concat' ls = [x | l <- ls, x <- l]
Common list functions
---------------------
The "Prelude" module defines many useful list functions (some of which we
implemented above). They include:
- Basic operations:
head :: [a] -> a
tail :: [a] -> [a]
null :: [a] -> Bool
length :: [a] -> Int
last :: [a] -> a
(++) :: [a] -> [a] -> [a]
(!!) :: [a] -> Int -> a
- Building lists:
repeat :: a -> [a]
replicate :: Int -> a -> [a]
cycle :: [a] -> [a]
- Lists -> Lists:
concat :: [[a]] -> [a]
reverse :: [a] -> [a]
zip :: [a] -> [b] -> [(a,b)]
- Extracting sublists:
take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
splitAt :: Int -> [a] -> ([a], [a])
break :: (a -> Bool) -> [a] -> ([a], [a])
- Class specific:
elem :: Eq a => a -> [a] -> Bool
maximum :: Ord a => [a] -> a
minimum :: Ord a => [a] -> a
sum :: Num a => [a] -> a
product :: Num a => [a] -> a
lines :: String -> [String]
words :: String -> [String]
Note: many of these functions operate on a type class that includes lists and
other recursive data types (We'll see how this works later.)
List processing functions
-------------------------
-- Pattern matching
`[]` and `:` can be used to pattern match against lists (we'll see that all
value constructors can be used for pattern matching). So the first three basic
operations are trivial to re-implement:
> head' :: [a] -> a
> head' (x:_) = x
>
> tail' :: [a] -> [a]
> tail' (_:xs) = xs
>
> null' :: [a] -> Bool
> null' [] = True
> null' _ = False
But most other list-processing functions need to potentially extract multiple
values from the list. A common technique for doing this is structural recursion.
-- Structural recursion
Structural recursion loosely describes a pattern for writing functions that
handle recursively defined data types (like the list). When called with a value
of such a type, a structurally recursive function will:
1. start by determining how the value was constructed
2. if the value is not a recursive instance of the data type, simply process
its immediate contents
3. if the value is a recursive instance of the data type, "deconstruct" it to
process its immediate contents, then recurse on the nested value(s)
Pattern matching in Haskell helps with both (1) and (3).
E.g., to compute the length of a list:
> length' :: [a] -> Int
> length' [] = 0
> length' (x:xs) = 1 + length' xs
E.g., more built-in functions:
> last' :: [a] -> a
> last' (x:[]) = x
> last' (_:xs) = last' xs
>
>
> (+++) :: [a] -> [a] -> [a]
> [] +++ ys = ys
> (x:xs) +++ ys = x : xs +++ ys
>
>
> (!!!) :: [a] -> Int -> a -- the ! in its name is an implicit warning as to its inefficiency!
> (x:_) !!! 0 = x
> (_:xs) !!! n = xs !!! (n-1)
>
>
> reverse' :: [a] -> [a]
> reverse' [] = []
> reverse' (x:xs) = reverse' xs +++ [x] -- is there a more efficient way?
>
>
> take' :: Int -> [a] -> [a]
> take' 0 _ = []
> take' _ [] = []
> take' n (x:xs) = x : take' (n-1) xs
>
>
> splitAt' :: Int -> [a] -> ([a], [a])
> splitAt' _ [] = ([],[])
> splitAt' 0 xs = ([], xs)
> splitAt' n (x:xs) = let (ys,zs) = splitAt' (n-1) xs
> in (x:ys, zs)
>
>
> break' :: (a -> Bool) -> [a] -> ([a], [a])
> break' _ [] = ([],[])
> break' p l@(x:xs) | p x = ([], l)
> | otherwise = let (ys, zs) = break' p xs
> in (x:ys, zs)
>
>
> words' :: String -> [String]
> words' [] = []
> words' l@(c:cs) | isSpace c = words' cs
> | otherwise = let (w, ws) = break' isSpace l
> in w : words' ws
E.g., the Caesar cipher is an encryption scheme that takes a plain text input
string P and a shift value N, and produces an encrypted version of the string
by replacing each letter in P with one N letters away in the alphabet (wrapping
around, if needed).
For the string "HELLO WORLD" and a shift value of 5:
Plain: H E L L O W O R L D
Encrypted: M J Q Q T B T W Q I
To implement the Caesar cipher, we need to be able to convert characters from/to
their corresponding ASCII codes. `ord`/`chr` do this. `isLetter` can be used to
determine if a character is a letter. We'll convert all letters to uppercase
for simplicity with `toUpper`.
> caesar :: Int -> String -> String
> caesar _ [] = []
> caesar n (x:xs) = (if isLetter x then encrypt x else x) : caesar n xs
> where encrypt x = n2l ((l2n x + n) `mod` 26)
> l2n c = ord (toUpper c) - ord 'A'
> n2l n = chr (n + ord 'A')