Haskell Book Chapter 5 Notes and Exercises

haskellbook-chapter-5-notes.md

Notes and Exercises from Chapter 5 of Haskell Book

Benefits of a type system:

• Many errors caught before program execution, at compile time
• Compiler optimizations
• Documentation of programs
• Less code to write because you don't have to validate data at every step

Many, perhaps most, programming languages have type systems that feel like haggling with a petty merchant. Haskell provides a type system that more closely resembles a quiet, pleasant conversation with a colleague than an argument in the bazaar.

Much of what we suggest with regards to putting code in a file, loading it in a REPL, querying types in the REPL, and so forth, is about creating habits conducive to having this pleasant back and forth with your type system.

Numbers are not concretely typed until they need to be.

:type inspection does not need to execute to return a value

:type 1 + 2 + 3
1 + 2 + 3 :: Num a => a

Can't do :type for (=>) or (->). Can't do :info for (=>).

The operator -> is right associative, so

a -> b -> c -> d
a -> (b -> (c -> d))

But function application is left associative, so

f g h x
((f g) h) x

Since all the arrows have same precedence, the associativity does not change the precedence or order of evaluation.

The compiler gives the least specific and most general type it can.

Error message language feels reminiscent of Victorian barristers

(1 :: Int) + (2 :: Double)
• Couldn't match expected type ‘Int’ with actual type ‘Double’
• In the second argument of ‘(+)’, namely ‘(2 :: Double)’
  In the expression: (1 :: Int) + (2 :: Double)
  In an equation for ‘it’: it = (1 :: Int) + (2 :: Double)

Currying vs Partial Application vs Sectioning

Currying is the nesting of multiple functions, each taking a single parameter and returning a single result, to give the illusion of accepting multiple parameters.

Partial Application is using currying to get a function with some of the parameters already specified.

Sectioning is partial application of infix operators with only one operand specified.

Exercises: Type Arguments

let f :: a -> a -> a -> a; f = undefined
let x :: Char, x = undefined
:type f x

Char -> Char -> Char

let g :: a -> b -> c -> b; g = undefined
:type g 0 'c' "woot"

Char

let h :: (Num a, Num b) => a -> b -> b; h = undefined
:type h 1.0 2

Num a => a

:type h 1 (5.5 :: Double)

Double

let jackal :: (Ord a, Eq b) => a -> b -> a; jackal = undefined
:type jackal "keyboard" "has the word jackal in it"

[Char]

:type jackal "keyboard"

Eq b => b -> [Char]

let kessel :: (Ord a, Num b) => a -> b -> a; kessel = undefined
:type kessel 1 2

(Num a, Ord a) => a

:type kessel 1 (2 :: Integer)

(Num a, Ord a) => a

:type kessel (1 :: Integer) 2

Integer

Polymorphism

• Parametric Polymorphism, like a -> b -> a
• Constrained Polymorphism, like (Num a, Ord a) => a

What are all the possible implementations of f given the following type signature:

f :: a -> a
f = ???

What are all the possible implementations of g given the following type signature:

g :: Bool a => a -> a
g = ???

A function is polymorphic when its type signature has variables that can represent more than one type.

Exercises: Parametricity

The behavior of a function with respect to the types of its parametrically polymorphic arguments is uniform.

What are the two possible implementations of f :: a -> a -> a?

f1 :: a -> a -> a
f1 x y = x

f2 :: a -> a -> a
f2 x y = y

How many implementations can g :: a -> b -> b have?

g :: a -> b -> b
g x y = y

Typecasting

fromIntegral :: (Integral a, Num b) => a -> b converts Integrals to Nums.

Exercises: Type Inference

(++) :: [a] -> [a] -> [a]

myConcat x = x ++ " yo"

:type myConcat
[Char] -> [Char]

(*) :: Num a => a -> a -> a

myMult x = (x / 3) * 5

:type myMult
Fractional a => a -> a

take :: Int -> [a] -> [a]

myTake x = take x "hey you"

:type myTake
Int -> [Char]

(>) :: Ord a => a -> a -> Bool

myCom x = x > (length [1..10])

:type myCom
Int -> Bool

(<) :: Ord a => a -> a -> Bool

myAlph x = x < 'z'

:type myAlph
Char -> Bool

Chapter Exercises

1. A value of type [a] is: c. a list whose elements are all of type a
2. A function of type [[a]] -> [a] could: a. take a list of strings as an argument
3. A function of type [a] -> Int -> a: b. returns one element of type a from the list
4. A function of type (a, b) -> a: c. takes a tuple argument and returns the first value

• (* 9) 6 ==> 54 :: Num a => a
• head [(0, "doge"), (1, "kitteh")] ==> (0, "doge") :: Num a => (a, [Char])
• head [(0 :: Integer, "doge"), (1, "kitteh")] ==> (0, "doge") :: (Integer, [Char])
• if False then True else False ==> False :: Bool
• length [1, 2, 3, 4, 5] ==> 5 :: Int
• (length [1, 2, 3, 4]) > (length "TACOCAT") ==> False :: Bool

x = 5
y = x + 5
w = y * 10

w :: Num a => a

x = 5
y = x + 5
z y = y * 10

z :: Num a => a -> a

x = 5
y = x + 5
f = 4 / y

f :: Fractional a => a

x = "Azavea"
y = " <3 "
z = "Haskell"
f = x ++ y ++ z

f :: [Char]

???

bigNum = (^) 5 $ 10
wahoo = bigNum $ 10

???

x = print
y = print "woohoo!"
z = x "hello world!"

a = (+)
b = 5
c = a b 10
d = a c 200

f :: zed -> Zed -> Blah

-- zed :: fully polymorphic
-- Zed :: concrete
-- Blah :: concrete

f :: Enum b => a -> b -> C

-- a :: fully polymorphic
-- b :: constrained
-- C :: conrete

f :: f -> g -> C

-- f :: fully polymorphic
-- g :: fully polymorphic
-- C :: concrete

functionH :: [a] -> a
functionH (x:_) = x

functionC :: (Ord a, Ord b) => a -> b -> Bool
functionC x y = if (x > y) then True else False

functionS :: (a, b) -> b
functionS (x, y) = y

i :: a -> a
i x = x

c :: a -> b -> a
c x y = x

c'' :: b -> a -> b
c'' x y = x

c' :: a -> b -> b
c' x y = y

r :: [a] -> [a]
r xs = xs         -- same list
r xs = reverse xs -- reversed list
r xs = tail xs    -- tail list

co :: (b -> c) -> (a -> b) -> a -> c
co bToC aToB a = bToC $ aToB a

a :: (a -> c) -> a -> a
a xToZ x = x

a' :: (a -> b) -> a -> b
a' xToY x = xToY x

module Sing where

fstString :: [Char] -> [Char]
fstString x = x ++ " in the rain"

sndString :: [Char] -> [Char]
sndString x = x ++ " over the rainbow"

sing :: [Char]
sing = if (x < y) then fstString x else sndString y
       where x = "Singin"
             y = "Somewhere"

module Arith3Broken where

main :: IO ()
main = do
    print (1 + 2)
    print 10
    print (negate (-1))
    print ((+) 0 blah)
    where blah = negate 1

f :: Int -> String
f = undefined

g :: String -> Char
g = undefined

h :: Int -> Char
h i = g $ f i

data A
data B
data C

q :: A -> B
q = undefined

w :: B -> C
w = undefined

e :: A -> C
e a = w (q a)

data X
data Y
data Z

xz :: X -> Z
xz = undefined

yz :: Y -> Z
yz = undefined

xform :: (X, Y) -> (Z, Z)
xform (x, y) = ((xz x), (yz y))

munge :: (x -> y) -> (y -> (w, z)) -> x -> w
munge xy ywz x = fst (ywz (xy x))