Haskell 101

ibobyr@, nicuveo@
go/haskell-101-slides-mtv

April 20, 2019

Today’s menu

▶ 101
▶ Concepts and generalities
▶ Syntax overview
▶ Data structures
▶ Declaring functions

1 / 32
Not today

▶ Project environment
▶ Cabal?
▶ Stackage? Stack?
▶ Haskell in Google3?
▶ Advanced stuff
▶ Functors?
▶ Monads?
▶ Monad Transformers?

2 / 32
Prerequisites

▶ Programming knowledge
▶ Functional programming is a plus
▶ Imperative programming is enough
▶ Compiler
▶ apt-get install haskell-platform

3 / 32
GHCI is your new best friend

▶ Type expressions, get results.

▶ Test and debug your code.
▶ :t

4 / 32
Haskell is...

▶ Strongly statically typed

▶ Purely functional
▶ Lazily evaluated
▶ General purpose

5 / 32
Haskell is NOT...

▶ A silver bullet
▶ Only for category theorists

6 / 32
Haskell is NOT...

▶ A silver bullet
▶ Only for category theorists
▶ Hard!

6 / 32
Haskell is NOT...

▶ A silver bullet
▶ Only for category theorists
▶ Hard! Just different...

6 / 32
Purely functional

▶ Functions are everywhere - similar to math

f :: Int -> Int f : Z → Z

f x = x + 1 f(x) = x + 1

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression

1 + 2

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression

let a = 1
in a + 2

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression

let a = if someBool then 1 else 0

in a + 2

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression

let a = if someBool then 1 else 0

in a + (let b = 2 in b)

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression

let offset = case color of

Red -> 0
Green -> 8
Blue -> 16
in baseValue + offset

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression
▶ Everything is immutable

let a = 3
in a = a + 1 -- compile error

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression
▶ Everything is immutable
▶ No side effects!

numberToWords :: Int -> String

7 / 32
Purely functional

▶ Functions are everywhere - similar to math

▶ Almost everything is an expression
▶ Everything is immutable
▶ No side effects unless explicitly stated

readFile :: String -> IO String

7 / 32
Purity...

▶ All side effects are in IO

8 / 32
Purity...

▶ All side effects are in IO

▶ Functions ∈ / IO are deemed pure

8 / 32
Purity...

▶ All side effects are in IO

▶ Functions ∈ / IO are deemed pure
▶ Functions ∈ IO are deemed impure

8 / 32
...and corruption

▶ ∃ f :: a -> IO a (from pure to impure)

▶ ∄ f :: IO a -> a (from impure to pure)

9 / 32
...and corruption

▶ ∃ f :: a -> IO a (from pure to impure)

▶ ∄ f :: IO a -> a (from impure to pure)

IO corrupts.

9 / 32
...and corruption

▶ ∃ f :: a -> IO a (from pure to impure)

▶ ∄ f :: IO a -> a (from impure to pure)
▶ ∃ f :: IO a -> IO a (from impure to impure)

IO corrupts.

9 / 32
Lazy

▶ Deferred expression evaluation

▶ Not used ⇒ not computed

10 / 32
Lazy

▶ Deferred expression evaluation

▶ Not used ⇒ not computed

Quiz

10 / 32
Lazy

▶ Deferred expression evaluation

▶ Not used ⇒ not computed

(C++)
if (obj != NULL && obj->value > 0)

10 / 32
Reduction steps

▶ Strict evaluation: inner to outer

add( x , y ) = x + y

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

add( x , y ) = x + y

add( 12 + 8 , 20 + 2 )

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

add( x , y ) = x + y

add( 12 + 8 , 20 + 2 )
add( 20 , 22 )

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

add( x , y ) = x + y

add( 12 + 8 , 20 + 2 )
add( 20 , 22 )
20 + 22

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

add( x , y ) = x + y

add( 12 + 8 , 20 + 2 )
add( 20 , 22 )
20 + 22
42

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

▶ Lazy evaluation: outer to inner
add( x , y ) = x + y

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

▶ Lazy evaluation: outer to inner
add( x , y ) = x + y

add( 12 + 8 , 20 + 2 )

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

▶ Lazy evaluation: outer to inner
add( x , y ) = x + y

add( 12 + 8 , 20 + 2 )
12 + 8 + 20 + 2

11 / 32
Reduction steps

▶ Strict evaluation: inner to outer

▶ Lazy evaluation: outer to inner
add( x , y ) = x + y

add( 12 + 8 , 20 + 2 )
12 + 8 + 20 + 2
42

11 / 32
Laziness pros and cons

- Memory pitfalls

Delayed computations (but escape hatches)

12 / 32
Laziness pros and cons

- Memory pitfalls
- IO and parallelism pitfalls

Delayed computations (but escape hatches)

12 / 32
Laziness pros and cons

- Memory pitfalls
- IO and parallelism pitfalls
+ Huge optimizations

Equation reduction and short-circuiting

12 / 32
Laziness pros and cons

- Memory pitfalls
- IO and parallelism pitfalls
+ Huge optimizations
+ Greater expressivity (e.g. infinite structures)

> let naturalNumbers = [0,1..]

> let squaredNumbers = map (^2) naturalNumbers
> take 5 squaredNumbers
[0,1,4,9,16]

12 / 32
Function types

f :: Int -> Int -> Int

13 / 32
Function types

f :: Int -> Int -> Int

f x y = x + y

13 / 32
Function types

f :: Int -> Int -> Int

f x y = x + y
f 1 2 :: Int

13 / 32
Function types

f :: Int -> Int -> Int

f x y = x + y
f 1 2 :: Int
3

13 / 32
Codelab - Section 1

▶ Codelab - Section 1
▶ Compiler
▶ apt-get install haskell-platform
▶ Source
▶ git clone \
https://github.com/google/haskell-trainings.git
cd haskell-trainings/haskell_101/codelab
▶ go/haskell-101-codelab-mtv
▶ Zip on X20
/google/data/ro/users/ib/ibobyr/haskell_101_codelab.zip
▶ Piper
//google3/experimental/users/ibobyr
haskell/grow/101/codelab
14 / 32
Curried functions, partial application

f :: Int -> Int -> Int

15 / 32
Curried functions, partial application

f :: Int -> ( Int -> Int )

f :: Int -> Int -> Int

15 / 32
Curried functions, partial application

f :: Int -> ( Int -> Int )

f :: Int -> Int -> Int
f 1 :: Int -> Int

15 / 32
Curried functions, partial application

f :: Int -> ( Int -> Int )

f :: Int -> Int -> Int
f 1 :: Int -> Int

(f 1) 2 :: Int

15 / 32
Curried functions, partial application

f :: Int -> ( Int -> Int )

f :: Int -> Int -> Int
f 1 :: Int -> Int
f 1 2 :: Int
(f 1) 2 :: Int

15 / 32
Quizz!

??? :: (a -> b) -> [a] -> [b]

16 / 32
Quizz!

??? :: (a -> b) -> [a] -> [b]

Lowercase letter: type parameter

16 / 32
Quizz!

??? :: (a -> b) -> [a] -> [b]

(a -> b) function from type A to type B

[a] list of values of type A
[b] list of values of type B

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

(a -> b) function from type A to type B

[a] list of values of type A
[b] list of values of type B

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

?????? :: (a -> Bool) -> [a] -> [a]

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]
($) :: (a -> b) -> a -> b

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]
($) :: (a -> b) -> a -> b

let a = fun (x + y)

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]
($) :: (a -> b) -> a -> b

let a = fun $ x + y

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]
($) :: (a -> b) -> a -> b
(.) :: (b -> c) -> (a -> b) -> (a -> c)

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]
($) :: (a -> b) -> a -> b
(.) :: (b -> c) -> (a -> b) -> (a -> c)

(f ◦ g)(x) = f(g(x))

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]
($) :: (a -> b) -> a -> b
(.) :: (b -> c) -> (a -> b) -> (a -> c)

show :: Stuff -> String

length :: String -> Int
length . show :: Stuff -> Int

16 / 32
Quizz!

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]
($) :: (a -> b) -> a -> b
(.) :: (b -> c) -> (a -> b) -> (a -> c)

cat input | grep token | sed stuff | tee output

16 / 32
Quizz with a vengeance!

foldl :: (a -> b -> a) -> a -> [b] -> a

17 / 32
Quizz with a vengeance!

foldl :: (a -> b -> a) -> a -> [b] -> a

(a -> b -> a) combines accumulator and value

a initial accumulator
[b] list of values
a result

17 / 32
Quizz with a vengeance!

foldl :: (a -> b -> a) -> a -> [b] -> a

(a -> b -> a) combines accumulator and value

a initial accumulator
[b] list of values
a result

”reduce”

17 / 32
Algebraic data types

▶ Type composition
▶ Product and sum types
▶ Cardinality expressions

18 / 32
Type synonyms

type Point = (Int, Int) -- tuple

19 / 32
Type synonyms

type Point = (Int, Int) -- tuple

type Polygon = [Point] -- list

19 / 32
Type synonyms

type Point = (Int, Int) -- tuple

type Polygon = [Point] -- list

type Map k v = [(k, v)] -- type parameters

19 / 32
Immutable data structures...

What do they consist of ?

20 / 32
Immutable data structures...

What do they consist of ?

▶ No methods...

20 / 32
Immutable data structures...

What do they consist of ?

▶ No methods...
▶ No modifiers...

20 / 32
Immutable data structures...

What do they consist of ?

▶ No methods...
▶ No modifiers...
▶ No private members...

20 / 32
Immutable data structures...

What do they consist of ?

▶ No methods...
▶ No modifiers...
▶ No private members...

What’s left?

20 / 32
Immutable data structures...

What do they consist of ?

▶ No methods...
▶ No modifiers...
▶ No private members...

What’s left? Constructors!

20 / 32
The almighty ”data” keyword

data None = None

None :: None

21 / 32
The almighty ”data” keyword

data None = None

data Minutes = Minutes Int

Minutes :: Int -> Minutes

Minutes 42 :: Minutes

21 / 32
The almighty ”data” keyword

data None = None

data Minutes = Minutes Int

data Bool = False | True

True :: Bool
False :: Bool

21 / 32
Not

data Bool = False | True

not :: Bool -> Bool

not x = ???

22 / 32
Not

data Bool = False | True

not :: Bool -> Bool

not x = if x then False else True

22 / 32
Not

data Bool = False | True

not :: Bool -> Bool

not x = if x then False else True

Only for built-in type(s)

22 / 32
Not

data Bool = False | True

not :: Bool -> Bool

not True = False
not False = True

#PatternMatching

22 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

x && y = ???

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

x && y = if x
then (if y then True else False)
else False

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

x && y = if x
then (if y then True else False)
else False

Only for built-in type(s)

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

True && True = True
True && False = False
False && True = False
False && False = False

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

True && True = True
x && y = False

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

True && True = True
x && y = False

Can you spot a problem?

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

True && True = True
x && y = False

Eager in the second argument :(

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

True && y = y
x && y = False

23 / 32
And

data Bool = False | True

(&&) :: Bool -> Bool -> Bool

True && y = y
_ && _ = False

23 / 32
Deconstructors?

data Minutes = Minutes Int

add :: Minutes -> Minutes -> Minutes

add mx my = ???

24 / 32
Deconstructors?

data Minutes = Minutes Int

add :: Minutes -> Minutes -> Minutes

add mx my = mx + my

24 / 32
Deconstructors?

data Minutes = Minutes Int

add :: Minutes -> Minutes -> Minutes

add (Minutes x) (Minutes y) = ???

24 / 32
Deconstructors?

data Minutes = Minutes Int

add :: Minutes -> Minutes -> Minutes

add (Minutes x) (Minutes y) = Minutes (x + y)

24 / 32
Deconstructors?

data Minutes = Minutes Int

add :: Minutes -> Minutes -> Minutes

add (Minutes x) (Minutes y) = Minutes $ x + y

24 / 32
Codelab - Section 2

▶ Codelab - Section 2

25 / 32
The almighty ”data” keyword. Continued

data None = None

data Minutes = Minutes Int

data Bool = False | True

26 / 32
The almighty ”data” keyword. Continued

data None = None

data Minutes = Minutes Int

data Bool = False | True

data Maybe a = Nothing | Just a

Nothing :: Maybe a
Just :: a -> Maybe a
Just 42 :: Maybe Int

26 / 32
The almighty ”data” keyword. Continued

data None = None

data Minutes = Minutes Int

data Bool = False | True

data Maybe a = Nothing | Just a

data List a = Nil | Cell a (List a)

Nil :: List a
Cell :: a -> List a -> List a
Cell 0 (Cell 1 (Nil)) :: List Int

26 / 32
The almighty ”data” keyword. Continued

data None = None

data Minutes = Minutes Int

data Bool = False | True

data Maybe a = Nothing | Just a

data List a = Nil | Cell a (List a)

Nil :: List a
Cell :: a -> List a -> List a
Cell 0 $ Cell 1 $ Nil :: List Int

26 / 32
The almighty ”data” keyword. Continued

data None = None

data Minutes = Minutes Int

data Bool = False | True

data Maybe a = Nothing | Just a

data [a] = [] | (a:[a])

[] :: [a]
(:) :: a -> [a] -> [a]
0:1:[] :: [Int]

26 / 32
The almighty ”data” keyword. Continued

data None = None

data Minutes = Minutes Int

data Bool = False | True

data Maybe a = Nothing | Just a

data [a] = [] | (a:[a])

[] :: [a]
(:) :: a -> [a] -> [a]
[0,1] :: [Int]

26 / 32
Record syntax

data User = User String Int

User :: String -> Int -> User

27 / 32
Record syntax

data User = User {

userName :: String,
userAge :: Int
}

User :: String -> Int -> User

27 / 32
Record syntax

data User = User {

userName :: String,
userAge :: Int
}

User :: String -> Int -> User

userName :: User -> String

userAge :: User -> Int

27 / 32
Length

data [a] = [] | (a:[a])

length :: [a] -> Int

length l = ???

28 / 32
Length

data [a] = [] | (a:[a])

length :: [a] -> Int

length [] = ???
length (x:xs) = ???

28 / 32
Length

data [a] = [] | (a:[a])

length :: [a] -> Int

length [] = 0
length (x:xs) = ???

28 / 32
Length

data [a] = [] | (a:[a])

length :: [a] -> Int

length [] = 0
length (_:xs) = 1 + length xs

#Recursion

28 / 32
The end of the theoretical part!

Questions?

29 / 32
Links

▶ go/haskell-101-slides-mtv
▶ tryhaskell.org
▶ learnyouahaskell.com
▶ book.realworldhaskell.org
▶ haskellbook.com
▶ haskell.org/hoogle/
▶ Pragmatic types: types vs tests

30 / 32
Codelab - Sections 3, 4, 5, and 6

▶ Codelab - Sections 3, 4, 5, and 6

31 / 32
The end!

Questions?

32 / 32