Haskell

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

> head [1,2,3,4,5]

1

[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:

ghci> read 8.2 + 3.8

12.0

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]

> 1+2

3

> (+) 1 2

3

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:

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]