Haskell

Haskell is a purely functional statically typed lazy programming language.

functions have no side effects
functions are referential transparent (same result for calls with the same parameters)
Haskell has type inference
you can’t set a variable to one value and then set it to something else later on
Haskell won’t execute functions until it needs to show you a result
Haskell doesn’t have a concept of pointers, just values

GHCi

:l <source-file-without-.hs-suffix>  -- load a source code
:r                                   -- reload the file
:t <expression>                      -- type of the expression
:k <type>                            -- kind of the type
:m + <module>,<module>,...           -- import modules

ghc --make <source-file-without-.hs-suffix>  -- compile a program

Basics

Functions

doubleMe x = x + x
doubleMe 4         -- 8

doubleUs x y = x * 2 + y * 2
doubleUs 4 9       -- 26
doubleUs 2.3 34.2  -- 73.0

Every function in Haskell officially takes only one parameter. All the functions that accepted multiple parameters are curried functions.

-- :t max
max :: Ord a => a -> a -> a  -- same as `a -> (a -> a)`

-- These two calls are equivalent:
max 4 5
(max 4) 5

max4 = max 4
max4 5
5

divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

divideByTen 200  -- 20.0

(/10) 200  -- 20.0

isUpperAlphanum :: Char -> Bool
isUpperAlphanum = (`elem` ['A'..'Z'])

isUpperAlphanum 'A'  -- True
isUpperAlphanum 'a'  -- False

Generally, a function like foo a = bar b a, can be rewrited as foo = bar b because of currying:

sum' :: (Num a) => [a] -> a
sum' xs = foldl (+) 0 xs

sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0

High-order functions

applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

applyTwice (+2) 1  -- 5

Lambdas

Lambdas are anonymous functions that we use when we need a function only once.

\<parameters> -> <body>

map (\x -> x + 3) [1,2,3]  -- [4,5,6]
-- is same as `map (+3) [1,6,3,2]`

map (\(a,b) -> a + b) [(1,2),(3,5)]  -- [3,8]

-- These two functions are equivalent:
addThree :: Int -> Int -> Int -> Int
addThree x y z = x + y + z.

addThree :: Int -> Int -> Int -> Int
addThree' = \x -> \y -> \z -> x + y + z

When ommiting parentheses, everything to the right of the arrow -> belongs to the lambda.

flip' :: (a -> b -> c) -> b -> a -> c
flip' f = \x y -> f y x

Function Application Operator `$`

($) :: (a -> b) -> a -> b
f $ x = f x

Function application with a space is left-associative (so f a b c is the same as ((f a) b) c), while function application with $ is right-associative.

$ function has the lowest precedence:

sum (map sqrt [1..130])
sqrt (3 + 4 + 9)
-- could be rewitten as:
sum $ map sqrt [1..130]
sqrt $ 3 + 4 + 9

$ function is right-associative: f $ g $ x is equivalent to f $ (g $ x):

sum (filter (> 10) (map (*2) [2..10]))
-- could be rewitten as:
sum $ filter (> 10) $ map (*2) [2..10]

$ lets us treat function application like just another function:

map ($ 3) [(4+), (10*), (^2), sqrt]  -- [7.0,30.0,9.0,1.7320508075688772]

Function Composition `.`

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

(+1) . (*100) $ 4  -- 401

map (\x -> negate (abs x)) [1,2,-3]  -- [-1,-2,3]
map (\xs -> negate (sum (tail xs))) [[1..5],[3..6]]  -- [-14,-15]
-- is equivalent to:
map (negate . abs) [1,2,-3]
map (negate . sum . tail) [[1..5],[3..6]]

-- these lines are equivalent:
sum (replicate 3 (max 1 2))  -- can be understood as `(sum . replicate 3) max 1 2`
sum . replicate 3 $ max 1 2

Functions in point-free style

Because of currying we can ommit the parameter in the function definition:

fn x = ceiling (negate (tan (cos (max 50 x))))  -- definition with the parameter
fn = ceiling . negate . tan . cos . max 50      -- same function in point-free style

plusThreeTimesTwo :: Num c => c -> c
plusThreeTimesTwo = (*) 2 . (+) 3
plusThreeTimesTwo 2  -- 10

If

the else clause is mandatory

if x > 100 then x else x * 2

Lists

Lists in Haskell are homogeneous data structure.

strings are just lists of chars
[1,2,3] is just syntactic sugar for 1:2:3:[]

[]                   -- empty list
0:[1,2]              -- [0,1,2]
[1,2] ++ [3,4,5]     -- [1,2,3,4,5]
'A':" SMALL CAT"     -- "A SMALL CAT"
"Steve Buscemi" !! 6 -- B
[1,2,3] !! 0         -- 1
[1,2,3] !! 1         -- 2
[1,2,3] !! 3         -- *** Exception: index too large

b = [[1,2,3,4],[5,3,3,3],[1,2,2,3,4],[1,2,3]]
b ++ [[1,1,1,1]]  -- [[1,2,3,4],[5,3,3,3],[1,2,2,3,4],[1,2,3],[1,1,1,1]]
[6,6,6]:b         -- [[6,6,6],[1,2,3,4],[5,3,3,3],[1,2,2,3,4],[1,2,3]]
b !! 2            -- [1,2,2,3,4]

[3,2,1] > [2,10,100]  -- True
[3,4,2] > [2,4]       -- True
[3,4,2] == [3,4,2]    -- True

-- [head][--------tail----------]
-- [----------init--------][last]

head [5,4,3,2,1]  -- 5
tail [5,4,3,2,1]  -- [4,3,2,1]
last [5,4,3,2,1]  -- 1
init [5,4,3,2,1]  -- [5,4,3,2]

length [1,2,3]    -- 3
null [1,2,3]      -- False
null []           -- True
reverse [1,2,3]   -- [3,2,1]
take 2 [1,2,3]    -- [1,2]
take 0 [1,2,3]    -- []
take 9 [1,2,3]    -- [1,2,3]
drop 2 [1,2,3]    -- [3]
drop 0 [1,2,3]    -- [1,2,3]
drop 9 [1,2,3]    -- []
maximum [1,2,3]   -- 3
minimum [1,2,3]   -- 1
sum [1,2,3,4]     -- 10
product [1,2,3,4] -- 24
elem 2 [1,2,3]    -- True
elem 2 [3,4,5]    -- False

[1..10]          -- [1,2,3,4,5,6,7,8,9,10]
['a'..'z']       -- "abcdefghijklmnopqrstuvwxyz"
[2, 4..10]       -- [2,4,6,8,10]
take 5 [13, 26..]       -- [13,26,39,52,65]
take 10 (cycle [1,2,3]) -- [1,2,3,1,2,3,1,2,3,1]
take 12 (cycle "LOL ")  -- "LOL LOL LOL "
take 10 (repeat 5)      -- [5,5,5,5,5,5,5,5,5,5]
replicate 3 10          -- [10,10,10]
[0.1, 0.3 .. 1]         -- [0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]

List comprehensions

[x*2 | x <- [1..10]]            -- [2,4,6,8,10,12,14,16,18,20]
[x*2 | x <- [1..10], x*2 >= 12] -- [12,14,16,18,20]

boomBangs xs = [ if x < 10 then "BOOM!" else "BANG!" | x <- xs, odd x]
boomBangs [7..13]  -- ["BOOM!","BOOM!","BANG!","BANG!"]

[ x | x <- [10..20], x /= 13, x /= 15, x /= 19] -- [10,11,12,14,16,17,18,20]

[x+y | x <- [10,100], y <- [1,2,3]]  -- [11,12,13,101,102,103]

length' xs = sum [1 | _ <- xs]  -- underscore `_` is a temporary variable we don't care about

Map

map (+3) [1,2,3]                -- [4,5,6]
map (++ "!") ["Bang", "Pow"]    -- ["Bang!","Pow!"]
map (replicate 3) [3..5]        -- [[3,3,3],[4,4,4],[5,5,5]]
map (map (^2)) [[1,2],[3,4,5]]  -- [[1,4],[9,16,25]]

Mapping Functions with Multiple Parameters

listOfFncs = map (*) [0..]  -- we will get back a list of functions
(listOfFncs !! 4) 5
-- Getting the element with the index 4 returns a function equivalent to (4*). 
-- Then we just apply 5 to that function, which is the same as (4*) 5.

Filter

filter (>3) [5,3,2,4]     -- [5,4]
filter (==3) [1,2,3,4,5]  -- [3]
filter (`elem` ['a'..'z']) "u LaUgH aT mE"  -- "uagam"
filter (<15) (filter even [1..10])  -- [2,4,6,8,10]

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerOrEqual = filter (<= x) xs
        larger = filter (> x) xs
    in quicksort smallerOrEqual ++ [x] ++ quicksort larger

Folds

Folds allow you to reduce a data structure (like a list) to a single value.
A fold takes a binary function (one that takes two parameters, such as + or div), a starting value (often called the accumulator ), and a list to fold up.
A right fold over the list [1,2,3], is essentially doing this: f 1 (f 2 (f 3 acc))

sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs
-- alternatively `sum' = foldl (+) 0`

sum' [1,2,3]  -- 6

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs
-- is much cheaper than the fold-left alternative:
map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs

elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldr (\x acc -> if x == y then True else acc) False ys

reverse' :: [a] -> [a]
reverse' = foldl (\acc x -> x : acc) []

product' :: (Num a) => [a] -> a
product' = foldl (*) 1

filter' :: (a -> Bool) -> [a] -> [a]
filter' p = foldr (\x acc -> if p x then x : acc else acc) []

last' :: [a] -> a
last' = foldl1 (\_ x -> x)

`foldl` and `foldr1`

work much like foldl and foldr, except assume the first (resp. last) element to be the starting accumulator.

maximum' :: (Ord a) => [a] -> a
maximum' = foldl1 max

Scans

The scanl and scanr functions are like folds, except they report all the intermediate accumulator states in the form of a list.

scanl (+) 0 [1,2,3]  -- [0,1,3,6]
scanr (+) 0 [1,2,3]  -- [6,5,3,0]

scanl (flip (:)) [] [1,2,3]  -- [[],[1],[2,1],[3,2,1]]

Tuples

Tuples are used to store several heterogeneous elements as a single value.

(1, 3)                   -- (1,3)
(3, 'a', "hello")        -- (3,'a',"hello")
(1, 50.4, "hello", 'b')  -- (1,50.4,"hello",'b')

[(1,2),(8,11,5),(4,5)]   -- error: Couldn't match expected type `(a, b)`

Pairs

fst (8, 11)  -- 8
snd (8, 11)  -- 11

zip [1,2,3] [5,5,5]       -- [(1,5),(2,5),(3,5)]
zip [1,2,3,4,5] ["a","b"] -- [(1,"a"),(2,"b")]
zip ["a","b","c"] [1..]   -- [("a",1),("b",2),("c",3)]

Dictionaries (Association Lists)

phoneBook = [("betty","555-2938"), ("bonnie","452-2928"), ("wendy","939-8282")]
--
findKey :: (Eq k) => k -> [(k, v)] -> v
findKey key xs = snd . head . filter (\(k, v) -> key == k) $ xs

findKey "wendy" phoneBook  -- "939-8282"
findKey "diana" phoneBook  -- "*** Exception: head: empty list
--
findKey :: (Eq k) => k -> [(k, v)] -> Maybe v
findKey key xs = foldr (\(k, v) acc -> if key == k then Just v else acc) Nothing xs

findKey "wendy" phoneBook  -- Just "939-8282"
findKey "diana" phoneBook  -- Nothing

### Pattern Matching
Pattern matching is used to specify patterns to which some data should conform and to deconstruct the data according to those patterns.
```haskell
lucky :: Int -> String
lucky 7 = "LUCKY NUMBER SEVEN!"
lucky x = "Sorry, you're out of luck, pal!"
lucky 1   -- "Sorry, you're out of luck, pal!"
lucky 7   -- "LUCKY NUMBER SEVEN!"

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
factorial 8  -- 40320

addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)
addVectors (1,2) (10,20)  -- (11,22)

first (x, _, _) = x
first (1,2,3)  -- 1

As-patterns

As-patterns allow you to break up an item according to a pattern, while still keeping a reference to the entire original item.

firstLetter "" = "Empty string, whoops!"
firstLetter myParam@(x:xs) = "The first letter of " ++ myParam ++ " is " ++ [x]
firstLetter "Dracula" -- "The first letter of Dracula is D"

Where

initials :: String -> String -> String
initials firstname lastname = [f] ++ ". " ++ [l] ++ "."
where (f:_) = firstname
      (l:_) = lastname

Expressions `let..in`

cylinder :: Double -> Double -> Double
cylinder r h =
    let sideArea = 2 * pi * r * h
        topArea = pi * r ^ 2
    in sideArea + 2 * topArea

can be used anywhere in the code:

4 * (let a = 9 in a + 1) + 2   -- 42
[let square x = x * x in (square 5, square 3, square 2)]  -- [(25,9,4)]

can be separated with semicolons:

(let a = 2; b = 5 in a*b, let foo="Hey "; bar = "there!" in foo ++ bar)  -- (10,"Hey there!")

Guards

max' a b
  | a <= b = b
  | otherwise = a
max' 2 5  -- 5

weightTell :: Int -> String  
weightTell weight
  | weight <= 50 = "You're underweight, you emo, you!"  
  | weight <= 75 = "You're supposedly normal. Pffft, I bet you're ugly!"  
  | weight <= 95 = "You're fat! Lose some weight, fatty!"  
  | otherwise   = "You're a whale, congratulations!"
weightTell 60  -- "You're supposedly normal. Pffft, I bet you're ugly!"

bmiTell :: Double -> Double -> String
bmiTell weight height
  | bmi <= 18.5 = "You're underweight, you emo, you!"
  | bmi <= 25.0 = "You're supposedly normal. Pffft, I bet you're ugly!"
  | bmi <= 30.0 = "You're fat! Lose some weight, fatty!"
  | otherwise = "You're a whale, congratulations!"
  where bmi = weight / height ^ 2

Cases

case expression of pattern -> result
     pattern -> result
     ...

head' :: [a] -> a
head' xs = case xs of [] -> error "No head for empty lists!"
                      (x:_) -> x

Pattern matching on function parameters can be done only when defining functions, but case expressions can be used anywhere:

describeList :: [a] -> String
describeList ls = "The list is " ++ case ls of [] -> "empty."
                                               [x] -> "a singleton list."
                                               xs -> "a longer list."

Because pattern matching in function definitions is the same as using case expressions, we could have also defined the describeList function like this:

describeList ls = "The list is " ++ what ls
    where what [] = "empty."
          what [x] = "a singleton list."
          what xs = "a longer list."

Recursion

Maximum in a list

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list!"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)

`reverse`

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

`replicate`

replicate' :: Int -> a -> [a]
replicate' n x
    | n <= 0 = []
    | otherwise = x : replicate' (n-1) x

`take`

take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
    | n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs

Quicksort

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerOrEqual = [a | a <- xs, a <= x]
        larger = [a | a <- xs, a > x]
    in quicksort smallerOrEqual ++ [x] ++ quicksort larger

quicksort "the quick brown fox jumps over the lazy dog"
"        abcdeeefghhijklmnoooopqrrsttuuvwxyz"

Data Types

data Bool = False | True

data Point = Point Float Float deriving (Show)
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

area :: Shape -> Float
area (Circle _ r) = pi * r ^ 2
area (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 - x1) * (abs $ y2 - y1)

area $ Circle (Point 0 0) 10                  -- 314.15927
area $ Rectangle (Point 0 0) (Point 100 100)  -- 10000.0

baseRect :: Float -> Float -> Shape
baseRect width height = Rectangle (Point 0 0) (Point width height)

Record Syntax

data Person = Person { 
    firstName :: String, 
    lastName :: String,
    age :: Int} deriving (Show)

guy = Person "Charles" "Bukowski" 74  -- alternatively: 
guy = Person{ age=74, lastName="Bukowski", firstName="Charles" }  -- any order

firstName guy  -- "Charles" // the function is generated automatically

describePerson :: Person -> String
describePerson (Person {firstName = first, lastName = last, age = age}) =
    "Person " ++ first ++ " " ++ last ++ " is " ++ show age 

describePerson guy  -- "Person Charles Bukowski is 74"

Type Parameters

data Maybe a = Just a | Nothing  -- the `a` here is the type parameter

Depending on what we want this data type to hold when it's not Nothing, this type constructor can end up producing a type of Maybe Int, Maybe Person, and so on. No value can have a type of just Maybe, because that’s not a type—it's a type constructor.

Just "abc"     -- Just "abc"
:t Just "abc"  -- Just "abc" :: Maybe [Char]

Just 84        -- Just 84
:t Just 84     -- Just 84 :: (Num a) => Maybe a

Just 1 :: Maybe Double  -- Just 1.0

:t Nothing     -- Nothing :: Maybe a

We say that a type is concrete if it doesn’t take any type parameters at all (like Int or Bool), or if it takes type parameters and they’re all filled up (like Maybe Char). If you have some value, its type is always a concrete type.

data IntMaybe = INothing | IJust Int

Like functions, type constructors can be partially applied.

Derived Instances

Classes in Haskell are defining a behavior. First we create our type and then we make it an instance of a class depending what behavior we need.

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
    deriving (Eq, Ord, Show, Read, Bounded, Enum)

Wednesday                   -- Wednesday
show Wednesday              -- "Wednesday"
read "Wednesday" :: Day     -- Wednesday
Saturday == Sunday          -- False
Saturday > Friday           -- True
Monday `compare` Wednesday  -- LT
minBound :: Day             -- Monday
maxBound :: Day             -- Sunday
succ Monday                 -- Tuesday
pred Saturday               -- Friday
[Thursday .. Saturday]      -- [Thursday,Friday,Saturday]

Type Synonyms

type String = [Char]

type PhoneNumber = String
type Name = String
type PhoneBook = [(Name, PhoneNumber)]

Parameterizing Type Synonyms

type AssocList k v = [(k, v)]

data Either a b = Left a | Right b 
    deriving (Eq, Ord, Read, Show)

Right 20     -- Right 20
:t Left 'a'  -- Left 'a' :: Either Char b

Recursive Data Structures

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x == a = Node x left right
    | x < a = Node a (treeInsert x left) right
    | x > a = Node a left (treeInsert x right)

treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
    | x == a = True
    | x < a = treeElem x left
    | x > a = treeElem x right

numsTree = foldr treeInsert EmptyTree [1,5,4,2]
numsTree
Node 2 
    (Node 1 EmptyTree EmptyTree) 
    (Node 4 EmptyTree 
        (Node 5 EmptyTree EmptyTree)
    )

treeElem 1 numsTree  -- True
treeElem 8 numsTree  -- False

Type Classes

-- define a new type class:
class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool
    x == y = not (x /= y)
    x /= y = not (x == y)

-- create an instance of that class:
data TrafficLight = Red | Yellow | Green

instance Eq TrafficLight where
    Red == Red = True
    Green == Green = True
    Yellow == Yellow = True
    _ == _ = False

Red == Red     -- True
Red == Yellow  -- False

Red  -- error: No instance for (Show TrafficLight)

instance Show TrafficLight where
    show Red = "Red light"
    show Yellow = "Yellow light"
    show Green = "Green light"

Red  -- Red light

Because == was defined in terms of /= and vice versa in the class declaration, we needed to overwrite only one of them in the instance declaration.

Subclassing

class (Eq a) => Num a where
    ...

This is just like writing class Num a where, but we state that our type a must be an instance of Eq. That’s all there is to subclassing — it’s just a class constraint on a class declaration!

Parameterized Types As Instances of Type Classes

For example Maybe is not a concrete type, it's a type constructor that takes one parameter and then produces a concrete type (so you can't have a function of the type a -> Maybe, but it's okay to have a -> Maybe a or Maybe Int -> Maybe String).

-- instance Eq Maybe where -- doesn't compile
-- make all types of the form `Maybe something` an instance of `Eq`:
instance (Eq m) => Eq (Maybe m) where
    Just x == Just y = x == y
    Nothing == Nothing = True
    _ == _ = False

We use == on the contents of the Maybe, so we have the assurance that what the Maybe contains can be used with Eq - that's why we needed to add the class constraint.

-- (==) :: Maybe -> Maybe -> Bool  -- doesn’t make much sense
(==) :: (Eq m) => Maybe m -> Maybe m -> Bool  -- okay

Kinds

A kind is more or less the type of a type.

* indicates that the type is a concrete type
concrete type is a type that doesn’t take any type parameters
values can have only types that are concrete types

:k Int  -- Int :: *

-- `Maybe` type constructor takes one concrete type (like Int) and returns a concrete type (like Maybe Int):
:k Maybe      -- Maybe :: * -> *
:k Maybe Int  -- Maybe Int :: *

-- Either takes two concrete types as type parameters to produce a concrete type:
:k Either             -- Either :: * -> * -> *
:k Either Int         -- Either Int :: * -> *
:k Either Int String  -- Either Int String :: *

Functors

The Functor type class is for things that can be mapped over (e.g. list).

class Functor f where
    fmap :: (a -> b) -> f a -> f b

fmap takes a function from one type to another and a functor value applied with one type and returns a functor value applied with another type.

-- `map` is a `fmap` that works only on lists:
map :: (a -> b) -> [a] -> [b]
-- the list's instance of the Functor type class:
instance Functor [] where
    fmap = map

Here’s how Maybe is a functor:

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing
-- If it’s an empty value of Nothing, then just return a Nothing.
-- If it’s a single value packed in a `Just`, then we apply the function on the contents of the `Just`

fmap (*2) Nothing     -- Nothing
fmap (*2) (Just 200)  -- Just 400

We wrote instance Functor Maybe where instead of instance Functor (Maybe m) where because a functor wants a type constructor that takes one type, and not a concrete type.

The Functor type class wants a type constructor that takes only one type parameter, but Either takes two - we’ll partially apply Either by feeding it only one parameter, so that it has one free parameter:

data Either a b = Left a | Right b

instance Functor (Either a) where
    fmap f (Right x) = Right (f x)
    fmap f (Left x) = Left x

We can think of the Left part as sort of an empty box with an error message written on the side telling us why it’s empty.

Functor Laws

if we map the id function over a functor value, the functor value that we get back should be the same as the original functor value. fmap id = id
composing two functions and then mapping the resulting function over a functor should be the same as first mapping one function over the functor and then mapping the other one. fmap (f . g) = fmap f . fmap g

Applicative Functor

Applicative type class, in the Control.Applicative module defines two functions: pure and <*>.

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Applicative instance implementation for Maybe:

instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something

Just (+3) <*> Just 9          -- Just 12
pure (+3) <*> Just 9          -- Just 12
Just (++"hahah") <*> Nothing  -- Nothing

pure (+) <*> Just 3 <*> Just 5   -- Just 8
pure (+) <*> Nothing <*> Just 5  -- Nothing 
pure (+) <*> Just 3 <*> Nothing  -- Nothing

Control.Applicative exports a function called <$>, which is just fmap as an infix operator:

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x

(++) <$> Just "hey" <*> Just "ho"  -- Just "heyho"

Applicative Functor Laws

pure f <*> x = fmap f x
pure id <*> v = v
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u

Monads

Monads are just beefed-up applicative functors, much like applicative functors are beefed-up functors.

Monads are a natural extension of applicative functors, and they provide a solution to the following problem: If we have a value with a context, m a, how do we apply to it a function that takes a normal a and returns a value with a context? In other words, how do we apply a function of type a -> m b to a value of type m a? Essentially, we want this function:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b  -- `>>=` function is called *bind*.

class Monad m where
    return :: a -> m a                  -- pure function

    (>>=) :: m a -> (a -> m b) -> m b   -- bind function

    (>>) :: m a -> m b -> m b
    x >> y = x >>= \_ -> y

    fail :: String -> m a
    fail msg = error msg

Maybe is an instance of Monad:

instance Monad Maybe where
    return x = Just x
    Nothing >>= f = Nothing
    Just x >>= f = f x
    fail _ = Nothing

return "WHAT" :: Maybe String   -- Just "WHAT"
Just 9 >>= \x -> return (x*10)  -- Just 90
Nothing >>= \x -> return (x*10) -- Nothing

`do` Notation

For gluing together monadic values in sequence.

foo :: Maybe String
foo = Just 3 >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))
-- is the same as:

foo :: Maybe String
foo = do
    x <- Just 3
    y <- Just "!"
    Just (show x ++ y)

foo  -- Just "3!"

do expressions are just different syntax for chaining monadic values.

In a do expression, every line that isn’t a let line is a monadic value
To inspect its result, we use <- (except the last monadic value)

Pattern Matching

In do notation, when we bind monadic values to names, we can utilize pattern matching, just as in let expressions and function parameters:

justH :: Maybe Char
justH = do
    (x:xs) <- Just "hello"
    return x

Failures

When pattern matching fails in a do expression, the fail function (part of the Monad type class) enables it to result in a failure in the context of the current monad, instead of making the program crash.

-- the default implementation does make the program crash
fail :: (Monad m) => String -> m a
fail msg = error msg
```haskell
-- implementation for `Maybe` ignores the error message and makes a `Nothing`:
fail _ = Nothing

Monad Laws

Left Identity

If we take a value, put it in a default context with return, and then feed it to a function by using >>=, that’s the same as just taking the value and applying the function to it.

return x >>= f is same as f x.

return 3 >>= (\x -> Just (x+100000))  -- Just 100003
(\x -> Just (x+100000)) 3  -- Just 100003

Right Identity

If we have a monadic value and we use >>= to feed it to return, the result is our original monadic value.

m >>= return is same as just m

Just "abc" >>= (\x -> return x)  -- Just "abc"

Associativity

When we have a chain of monadic function applications with >>=, it shouldn’t matter how they’re nested.

doing (m >>= f) >>= g is just like doing m >>= (\x -> f x >>= g) When we look at the law as a law of compositions, it states that f <=< (g <=< h) should be the same as (f <=< g) <=< h.

Monadic Functions

liftM :: (Monad m) => (a -> b) -> m a -> m b  -- pretty like `fmap`
liftM f m = m >>= (\x -> return (f x))

liftM (*3) (Just 8)  -- Just 24

join :: (Monad m) => m (m a) -> m a  -- flatts monadic values
join mm = do
    m <- mm
    m

join (Just (Just 9))  -- Just 9
join (Just Nothing)   -- Nothing
join Nothing          -- Nothing

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a

binSmalls :: Int -> Int -> Maybe Int
binSmalls acc x
    | x > 9 = Nothing
    | otherwise = Just (acc + x)

foldM binSmalls 0 [2,8,3,1]   -- Just 14
foldM binSmalls 0 [2,11,3,1]  -- Nothing

Functors vs. Applicatives vs. Monads

Functors: apply vanilla functions to structures.
Applicatives: also, some functions are in the structure.
Monads: also, some functions produce the structure.

Functors vs Applicatives vs Monads

Modules

A module is essentially a file that defines some functions, types, and type classes. A program is a collection of modules.

import Data.List
Data.List (nub, sort)          -- only functions `nub` and `sort`
import Data.List hiding (nub)  -- all the functions except `nub`
import qualified Data.Map      -- call the function by `Data.Map.nub`
import qualified Data.Map as M -- call the function by `M.nub`

Export a Module

module MyDir.MyModule (fce1, fce2, ...) where

fce1 :: Num a => a -> a
fce1 = (+) 2
...

Standard Libraries

`Data.Char`

digitToInt '2'  -- 2
digitToInt 'A'  -- 10

`Data.List`

ord 'a'               -- 97
chr 97                -- 'a'
words "hello world!"  -- ["hello","world!"]
sort [2,3,1]          -- [1,2,3]
tails "abc"           -- ["abc","bc","c",""]
tails [1,2,3]         -- [[1,2,3],[2,3],[3],[]]
isPrefixOf "ab" "abc" -- True
any (> 4) [1,2,3]     -- False
find (== 'a') "abc"   -- Just 'a'
find (> 4) [1,2,3]    -- Nothing
foldl' (+) 0 (replicate 1000000 1)  -- 1000000 (no stack overflow errors)

`Data.Map`

fromList [("MS",1),("MS",2),("MS",3)]  -- fromList [("MS",3)]
Map.lookup "betty" phoneBook           -- Just "555-2938"
Map.lookup "diana" phoneBook           -- Nothing
newBook = Map.insert "diana" "841-9021" phoneBook
Map.lookup "diana" phoneBook           -- Just "841-9021"
Map.size phoneBook                     -- 3
Map.size newBook                       -- 4

Input and Output

:t putStrLn  -- putStrLn :: String -> IO ()

By putting I/O actions together with do syntax, we glued them into one I/O action: helloworld.hs

main = do
    putStrLn "Hello, what's your name?"
    name <- getLine
    putStrLn ("Hey " ++ name ++ ", you rock!")

If we’re taking data out of an I/O action, we can take it out only when we’re inside another I/O action.
To get the value out of an I/O action, you must perform it inside another I/O action by binding it to a name with <-

`return`

In Haskell (and in I/O actions specifically), return makes an I/O action out of a pure value.

using return doesn’t cause the I/O do block to end in execution
return is sort of the opposite of <-

I/O Functions

putStr "Hey, "
putStr "I'm "
putStrLn "Andy!"

putChar 't'

print True     -- True
print 2        -- 2
print "haha"   -- "haha"
print 3.2      -- 3.2
print [3,4,3]  -- [3,4,3]

print $ map (++"!") ["hey","ho"]  -- ["hey!","ho!"]

when takes a Bool and an I/O action, and if that value is True, it returns the same I/O action that we supplied to it. If it’s False, it returns the return () action, which doesn’t do anything.

import Control.Monad
main = do
    input <- getLine
    when (input == "SWORDFISH") $ do
        putStrLn input

sequence function takes a list of I/O actions and returns an I/O action that will perform those actions one after the other. The result that this I/O action yields will be a list of the results of all the I/O actions that were performed.

main = do
    rs <- sequence [getLine, getLine, getLine]
    print rs

sequence $ map print [1,2,3,4,5]
1
2
3
4
5
[(),(),(),(),()]

mapM takes a function and a list, maps the function over the list, and then sequences it. mapM_ does the same thing, but it throws away the result later.

mapM print [1,2,3]
1
2
3
[(),(),()]

forever function takes an I/O action and returns an I/O action that just repeats the I/O action it got forever.

import Control.Monad
import Data.Char

main = forever $ do
    putStr "Give me some input: "
    l <- getLine
    putStrLn $ map toUpper l

getContents reads everything from the standard input until it encounters an end-of-file character. It does lazy I/O.

import Data.Char

main = do
    contents <- getContents
    putStr $ map toUpper contents

interact takes a function of type String -> String as a parameter and returns an I/O action that will take some input, run that function on it, and then print out the function’s result.

main = interact shortLinesOnly

shortLinesOnly :: String -> String
shortLinesOnly = unlines . filter (\line -> length line < 10) . lines

Files

openFile :: FilePath -> IOMode -> IO Handle
type FilePath = String
data IOMode = ReadMode | WriteMode | AppendMode | ReadWriteMode

import System.IO

main = do
    handle <- openFile "data.txt" ReadMode
    contents <- hGetContents handle
    putStr contents
    hClose handle

// `withFile` makes sure that the file handle gets closed.
withFile :: FilePath -> IOMode -> (Handle -> IO a) -> IO a

import System.IO
main = do
    withFile "girlfriend.txt" ReadMode (\handle -> do
        contents <- hGetContents handle
        putStr contents)

readFile :: FilePath -> IO String
writeFile :: FilePath -> String -> IO ()

import System.IO
import Data.Char

main = do
    contents <- readFile "data.txt"
    writeFile "data.txt" (map toUpper contents)

import System.IO

main = do
    todoItem <- getLine
    appendFile "todo.txt" (todoItem ++ "\n")

Exceptions

bracket :: IO a -> (a -> IO b) -> (a -> IO c) -> IO c

withFile :: FilePath -> IOMode -> (Handle -> IO a) -> IO a
withFile name mode f = bracket (openFile name mode)
    (\handle -> hClose handle)
    (\handle -> f handle)

Program Arguments

import System.Environment
import Data.List

main = do
    args <- getArgs
    progName <- getProgName
    putStrLn "The arguments are:"
    mapM putStrLn args
    putStrLn "The program name is:"
    putStrLn progName

Resources

Miran Lipovača: Learn You a Haskell for Great Good!
O’Sullivan, Goerzen, Stewart: Real World Haskell
http://www.haskellforall.com/2018/10/detailed-walkthrough-for-beginner.html
Haskell training: https://github.com/google/haskell-trainings

Uh oh!

Haskell

GHCi

Basics

Functions

High-order functions

Lambdas

Function Application Operator $

Function Composition .

Functions in point-free style

If

Lists

List comprehensions

Map

Mapping Functions with Multiple Parameters

Filter

Folds

foldl and foldr1

Scans

Tuples

Pairs

Dictionaries (Association Lists)

As-patterns

Where

Expressions let..in

Guards

Cases

Recursion

Maximum in a list

reverse

replicate

take

Quicksort

Data Types

Record Syntax

Type Parameters

Derived Instances

Type Synonyms

Parameterizing Type Synonyms

Recursive Data Structures

Type Classes

Subclassing

Parameterized Types As Instances of Type Classes

Kinds

Functors

Functor Laws

Applicative Functor

Applicative Functor Laws

Monads

do Notation

Pattern Matching

Failures

Monad Laws

Left Identity

Right Identity

Associativity

Monadic Functions

Functors vs. Applicatives vs. Monads

Modules

Export a Module

Standard Libraries

Data.Char

Data.List

Data.Map

Input and Output

return

I/O Functions

Files

Exceptions

Program Arguments

Resources

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Function Application Operator `$`

Function Composition `.`

`foldl` and `foldr1`

Expressions `let..in`

`reverse`

`replicate`

`take`

`do` Notation

`Data.Char`

`Data.List`

`Data.Map`

`return`