Super quick introduction to Haskell
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs)
| x > maxTail = x
| otherwise = maxTail
where maxTail = maximum' xs
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
repeat' :: a -> [a]
repeat' x = x:repeat' x
zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
quicksort [a | a <- xs, a <= x] ++ [x] ++ quicksort [a | a <- xs, a > x]
Questions?
Types and type classes
List Types
- A list is a sequence of values of the same type
- [t] is the type of lists with elements of type t
[False, True, False] :: [Bool]
['a', 'b', 'c', 'd'] :: [Char]
[['a'], ['b', 'c']] :: [[Char]]
Tuples
Some list functions
Making infinite lists
concat with ++
> [1,2,3,4] ++ [9,10,11,12]
[1,2,3,4,9,10,11,12]
get element by index with !!
> "Steve Buscemi" !! 6
'B'
> take 100 (repeat 7)
repeat
A tuple is a sequence of values of different types
head
[7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7]
tail
> tail [1,2,3,4,5]
[2,3,4,5]
> 'a': " small cat"
"a small cat"
add an element to the
beginning with :
cycle
> take 100 (cycle ['h', 'e', 'l', 'l', 'o', ' '] )
take
> take 3 [5,4,3,2,1]
[5,4,3]
"hello hello hello hello hello hello hello hello hello hello hello hello hello hello hello hello hell"
drop
> drop 3 [5,4,3,2,1]
[2,1]
some others: length, sum, product, elem, minimum, maximum
(False, True) :: (Bool, Bool)
(False, 'a', True) :: (Bool, Char, Bool)
(True, ['a', 'b']) :: (Bool, [Char])
Basic Types
a :: t means a has type t
- Bool
- Char
- String
- Int
- Integer
- Float
:t on ghci tells us the type of an expression
ghci > :t True
True :: Bool
Type classes
- A type class is an interface that defines some behavior (specifies a bunch of functions)
- when we make a type an instance of a type class, we define what those functions mean for that type
Function types
A function is a mapping from values of one type to values of another type
Some common type classes
not :: Bool -> Bool
isDigit :: Char -> Bool
add:: (Int, Int) -> Int
add x y = x + y
We could use tuples or lists to pass or return multiple values:
Partially applied functions
Curried Functions
ghci> [3 .. 5]
[3,4,5]
ghci> succ 'B'
'C'
Eq
- for types that support equality
- ==, /=
Ord
- for types whose values can be put in some order
- >, <, >=, <=, compare
Show
- for types whose values can be represented as strings
- show
Read
- takes a string and returns a value whose type is an instance of Read
- read
Enum
- sequentially ordered types - their values can be enumerated
- its values can be used in list ranges
- defined successors and predecessors:
- succ, pred
Bounded
- types that have an uppoer bound and a lower bound
- minBound, maxBound
Num
- numeric type class. Its instances act like numbers
Floating
- includes the Float and Double types
Integral
- only integral (whole) numbers
- includes the Int and Integer types
If we call a function with too few arguments we get back a function
Functions with multiple arguments are possible by returning functions as results
minBound :: Int
-2147483648
ghci> maxBound :: Bool
True
add' :: Int -> Int -> Int
add' x y = x + y
add :: Int -> Int -> Int
add x y = x + y
addFive= add 5
divideByTen :: (Floating a) => a -> a
divideByTen = (/10)
:t (*)
(*) :: (Num a) => a -> a -> a
Curried functions take their arguments one at a time.
Functions that use type variables are called polymorphic functions
ghci> :t length
length :: [a] -> Int
Defining your own types
data Bool = False | True
Value constructors are functions that return a value of a data type
data Shape = Circle Float Float Float | Rectangle Float Float Float Float
We can pattern match against constructors
area :: Shape -> Float
area (Circle _ _ r) = pi * r ^ 2
area (Rectangle x1 y1 x2 y2) = (abs $ x2 - x1) * (abs $ y2 - y1)
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
deriving (Eq, Ord, Show, Read, Bounded, Enum)
Using type parameters
Record syntax
data Maybe a = Nothing | Just a
Defining functions
data Person = Person { firstName :: String
, lastName :: String
, age :: Int
, height :: Float
, phoneNumber :: String
, flavor :: String
} deriving (Show)
Maybe Int, Maybe String, ..
Maybe is a type constructor
- It can produce types
- No value can have type of just Maybe.
- That's not a type, it's a type contructor
let guy = Person "Buddy" "Finklestein" 43 184.2 "526-2928" "Chocolate"
ghci> firstName guy
"Buddy"
data List a = Empty | Cons a (List a)
Without record syntax we'd have to define this function:
Conditional expressions
data Tree a = EmptyTree | Node a (Tree a) (Tree a)
Guarded Equations
firstName :: Person -> String
firstName (Person firstname _ _ _ _ _) = firstname
Pattern matching
abs :: Int -> Int
abs n = if n >= 0 then n else -n
List Patterns
(&&) :: Bool -> Bool -> Bool
True && True = True
True && False = False
False && True = False
False && False = False
abs n | n >= 0 = n
| otherwise = -n
means
[1,2,3,4]
1:(2:(3:(4:[])))
or just:
head :: [a] -> a
head (x:_) = x
True && True = True
_ && _ = False
tail :: [a] -> [a]
tail (_:xs) = xs
or without evaluating the second argument:
True && b = b
False && _ = False
must always have an else branch
Integer Patterns
pred :: Int -> Int
pred (n+1) = n
Lambdas
Sections
- Lambdas are anonymous functions that we use when we need a function only once
λ
\x -> x + x
- An infix function can be converted to a curried prefix function by using parentheses
λ
- People who don't understand how currying and partial application work often use lambdas where they are not necessary:
\ kind of looks like a lambda
map (\x -> x + 3) [1,6,3,2]
is the same as
map (+3) [1,6,3,2]
odds n = map f [0..n-1]
where
f x = x*2 + 1
odds n = map (\x -> x*2 + 1) [0..n-1]
- To section an infix function, surround it with parentheses and supply a parameter on only one side:
divideByTen :: (Floating a) => a -> a
divideByTen = (/10)
this creates a function that takes one parameter and then applies it to the side that's missing an operand
Some higher-order functions
- A function that can take functions as parameters or return functions as return values is called a higher order function.
twice :: (a -> a) -> a -> a
twice f x = f (f x)
List Comprehensions
Folds
filter
zipWith
map
ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]
[5,6,4]
- Folds allow you to reduce a data structure to a single value
- Can be used to implement any function where you traverse a list once element by element, and return something based on that
ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]
[6,8,7,9]
Implementation:
ghci> map (+20) [5,6,7,8,9]
[25,26,27,28,29]
A fold takes a binary function (that takes two parameters, such as + ), a starting value (often called the accumulator), and a list to fold up.
Implementation:
Implementation:
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
A way to filter, transform and combine lists
- right and left folds:
foldr, foldl
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
or using a list comprehension:
How can we implement with folds the following?
Folding infinite lists
or using a list comprehension:
- foldr will work on infinite lists when the binary function we're passing to it doesn't always need to evaluate its second parameter.
- foldl can't.
filter p xs = [x | x <- xs, p x]
map f xs = [f x | x <- xs]
sum xs = foldl (\acc x -> acc + x) 0 xs
product
length
reverse
filter
map
last
f (1, f(2, f(3, f(4, f (5, z)))))
example: creating an infinite list of Fibonacci numbers
fibs = 0 : 1 : <thunk>
tail fibs = 1 : <thunk>
zipWith (+) fibs (tail fibs) = <thunk>
False && (True && (True && (False && True)))
answers
fibs = 0 : 1 : 1: <thunk>
tail fibs = 1 : 1 : <thunk>
zipWith (+) fibs (tail fibs) = 1 : <thunk>
product = foldl (*) 1
length = foldl (\acc _ -> acc + 1) 0
reverse = foldl (\acc x -> x:acc) []
- or reverse = foldl (flip (:)) []
filter p xs = foldr (\x acc -> if p x then x : acc else acc) [] xs
map f xs = foldr (\x acc -> f x : acc) [] xs
reverse = foldl (\acc x -> x : acc) []
True && b = b
False && _ = False
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Haskell:
Math:
[x^2 | x <- [1..5]]
generator
Some recursive functions
Dependant Generators:
Which right triangle that has integers for all sides and all sides equal to or smaller than 10 has a perimeter of 24?
ghci> let rightTriangles = [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a+b+c == 24]
ghci> rightTriangles
[(6,8,10)]
Why is recursion useful?
ghci> [(x,y) | x <- [1..3], y<-[x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
- in Haskell rather than specifying how to compute something, we declare what it is, often recursively
- properties of recursive functions can be proved by induction
Using guards to restrict the values produced:
ghci> [x | x <- [1..10], even x]
[2,4,6,8,10]