class: center, middle

Functional programming in Haskell

Lesson 3

Clément Hurlin

https://github.com/smelc/tn-fp-haskell-course

Previously

How to define types
How to define constants (in the REPL)

Now:

Define functions, i.e. things that transforms values into values.

Forget:

mutable variables
pointers and references
dynamic dispatch

Remember:

Simple high school equations
Functions as seen in high school (fonctions affines anyone?)

Functions

Plain function

add :: Int -> Int -> Int  -- Type signature
add x y = x + y           -- Syntax: name params = body

public static int add(int x, int y) { return x + y; }

???

Note the difference with tupleAdd:

tupleAdd :: (Int, Int) -> Int
tupleAdd (x, y) = x + y

Pattern matching function

add2 :: Int -> Int -> Int
add2 0 y = y
add2 x 0 = x

What's the problem?

    Pattern match(es) are non-exhaustive
    In an equation for ‘add2’:
        Patterns not matched:
            p q where p is not one of {0}
                      q is not one of {0}

The function is not total

Totality is the property that, for any input, the function returns normally: without returning an exception or crashing the program.

add2 :: Int -> Int -> Int
add2 0 y = y
add2 x 0 = x
add2 x y = x + y

Order matters!

???

Highlight how the last member of the type signature is asymmetrical: it's an output. Other members are inputs.

Pattern matching function

Back in course 1:

data Version =
    Alpha
  | Beta
    -- | Version number of the form "x.y.z"
  | SemVer Int Int Int

Pattern matching mirrors the type's definition:

isSafe :: Version -> Bool
isSafe Alpha          = False
isSafe Beta           = False 
isSafe (SemVer 1 0 _) = False -- Bug #172, fixed in 1.1.*
isSafe (SemVer 1 1 2) = False -- Bug #175
isSafe _              = True

Pattern matching expression: `case`

-- | The 'Show' class, akin to the 'toString()' method in Java
class Show a where
  -- | Print a value
  show :: a -> String

print :: Version -> String
print v =
  case v of
    Alpha        -> "Alpha"
    Beta         -> "Beta"
    SemVer x y z -> show x ++ "." ++ show y ++ "." ++ show z

lastv :: Version -> Version -> Version
lastv v1 v2 =
  case (v1, v2) of
    (Alpha, _)    -> v2
    (Beta, Alpha) -> Beta
    (Beta, Beta)  -> Beta
    (Beta, SemVer _ _ _) -> v2
    (SemVer x1 _ _, SemVer x2 _ _)   | x1 < x2             -> v2
    (SemVer x1 y1 _, SemVer x2 y2 _) | x1 == x2 && y1 < y2 -> v2
    _ -> error "TODO"

???

Remove the _ catch all, look at the error message
What is the type of error?
How would you do last in Java/python?
- With a case/if, elif, ..., else
- What is the flaw?
  - If you want to apply something to the result of the case
  - breaks finality

Functions with guards

data Sign = Negative | Zero | Positive

sign :: Int -> Sign
sign 0             = Zero
sign n | n < 0     = Negative
       | otherwise = Positive

Execution model

Remember equations from high school?

safeHead :: String -> Maybe Char
safeHead []      = Nothing
safeHead (x : _) = Just x

-- fromMaybe takes the value from a Maybe, or use the default
fromMaybe :: a -> Maybe a -> a
fromMaybe a Nothing  = a
fromMaybe _ (Just a) = a

Use the definitions as rewriting rules:

   fromMaybe '?' (safeHead "Clément")

→ fromMaybe '?' (safeHead ('C' : "lément"))
→ fromMaybe '?' (Just 'C')
→ 'C'

Functional toolbox: recursion

To solve problems functionally:

Recursion: divide a problem into smaller subproblems
Fold: iterate over data, accumulate a value along the way

data Tree a = ...

map :: (a -> b) -> Tree a -> Tree b
map f t = undefined

find :: (a -> Bool) -> Tree a -> Maybe a
find f t = undefined

???

data Tree a = Node a [Tree a]  -- Discuss alternatives

treeFind :: (a -> Bool) -> Tree a -> Maybe a
treeFind f (Node x children) =
  if f x then Just x
  else firstJust (map (treeFind f) children)
  where
    firstJust =
      \case
         [] -> Nothing
         (Just x) : _ -> Just x
         Nothing : xs -> firstJust xs

instance Functor Tree where
  fmap f (Node x children) = Node (f x) (map (fmap f) children)

Ask whether map rings a bell. It's Functor's fmap from the previous course!
Ask about parallelization. Is it easy? Why?

Functional toolbox: folding

> :type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

wordCount :: [[String]] -> Int
wordCount files = undefined

data Operation = Debit Int | Credit Int

balance :: [Operation] -> Int
balance = undefined

???

wordCount :: [[String]] -> Int
wordCount files = foldr (\words soFar -> (length words) + soFar) 0 files

balance' :: [Operation] -> Int
balance' = foldr (\op soFar -> toInt op + soFar) 0
  where
    toInt = \case Debit x -> -x; Credit x -> x

Ask who knows about map/reduce

Partial application

> :type map
map :: (a -> b) -> [a] -> [b]
> :type show
show :: Show a => a -> String

What is the type of map show?

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

What is map2? How would you explain it to a coworker?

When writing functions:

- Order arguments so that partial application makes sense

Composition

Because functions are so central in functional programming, it is crucial to combine them easily.

> import Data.Function
> :type (&)
(&) :: a -> (a -> b) -> b

(&) means it is an operator (like +, -, etc.), so it is written between its arguments: x & f, in infix position.

???

Ask whether they see the relationship with function application

Composition

> :type filter
filter :: (a -> Bool) -> [a] -> [a]
> :type map
map :: (a -> b) -> [a] -> [b]

data Account = MkAccount {
    balance :: Int,
    email :: String,
    name :: Maybe String
  }

-- | Given a list of 'Account', returns the emails of the accounts with more
-- than one million 'balance', 'email' is dubious, and 'name' is omitted.
dubious :: [Account] -> [String]
dubious accounts =
  accounts
    & filter (\account -> account.balance > 1000000)
    & filter (\account -> "ponzi" `isInfixOf` account.email)
    & filter (\account -> case account.name of Nothing -> True; Just _ -> False)
    & map email

???

If you were to make this type support multiple currencies, how would you do it?
What constructs would you use in an imperative language to implement dubious?
- Would you rather have 3 loops or one loop?

Composition on steroids

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

Let's test that in the repl:

> ((+) 1) <$> (Just (42 :: Int))

> ((+) 1) <$> ([0, 1, 2, 3] :: [Int])

Let's combine functions:

(.) :: (b -> c) -> (a -> b) -> a -> c

> :type (show . ((+) (1 :: Int)))

> (show . ((+) 1)) <$> ([0, 1, 2, 3] :: [Int])

???

Remember how cool it was to chain & before (accounts & filter ...)

Applicative

class Functor f => Applicative f where
  pure :: a -> f a

  (<*>) :: f (a -> b) -> f a -> f b

<*> is function application generalized
- To an arbitrary context f

> pure (+) <*> Just 1 <*> Just 2
Just 3
> pure (+) <*> Nothing <*> Just 2
Nothing

Applicative

class Functor f => Applicative f where
  pure :: a -> f a

  (<*>) :: f (a -> b) -> f a -> f b

  -- Inherited from @Functor f@ constraint
  (<$>) :: Functor f => (a -> b) -> f a -> f b

Combining <*> and <$> lifts pure under the hood:

> pure (+) <*> Just 1 <*> Just 2
Just 3
> (+) <$> Just 1 <*> Just 2
Just 3

Applicative

class Functor f => Applicative f where
  pure :: a -> f a

  (<*>) :: f (a -> b) -> f a -> f b

  -- Inherited from @Functor f@ constraint
  (<$>) :: Functor f => (a -> b) -> f a -> f b

Tying it all together, we have container-agnostic transformations:

> :type (++)
String -> String -> String
> :type ((++) <$> Just "Philippe")
Maybe (String -> String)
> (++) <$> Just "Philippe" <*> Just " Katerine"
Just "Philippe Katerine"
> (++) <$> ["Philippe"] <*> [" Katerine"]
["Philippe Katerine"]

Recap

How to build functions from:

Pattern matching (case ... of )
Guards (f x | cond x = ...)

Functional toolbox:

Recursion
Folding

How to compose functions:

(&): chain
(<&>) and (<*>): chain in presence of wrapping
Functor, Applicative

Where

-- | @initials "Clément" "Hurlin"@ returns "CH"
initials :: String -> String -> String
initials firstname lastname =
  [extract firstname, extract lastname]
  where
    -- extract returns the initial or '?'
    extract :: String -> Char
    extract name = fromMaybe '?' (safeHead name)
    -- fromMaybe takes the value from a Maybe, or use the default
    fromMaybe :: a -> Maybe a -> a
    fromMaybe a Nothing  = a
    fromMaybe _ (Just a) = a
    -- Returns the first element of a list, or 'Nothing'
    safeHead :: String -> Maybe Char
    safeHead []      = Nothing
    safeHead (x : _) = Just x

The order in the where clause does not matter
It is idiomatic to have a small function body and a long where clause

???

Ask for the generalization of the type of safeHead

Indentation matters 😢:

Nested expressions should be intended
function body is intended w.r.t. the function name
members of the where clause are intended from the where

Let

Contrary to where, let can be used in the body of functions:

-- | 'mkEmail "clement" "hurlin" "tweag" "io"' returns my email
mkEmail firstName lastName domain ext =
  let left = firstName ++ "." ++ lastName in
  let right = domain ++ "." ++ ext in
  left ++ "@" ++ right

Its syntax is: let varName = expression in expression

???

What is the type of mkEmail?
- How does inference work?

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Functional programming in Haskell

Lesson 3

Previously

Functions

Plain function

Pattern matching function

Pattern matching function

Pattern matching expression: `case`

Functions with guards

Execution model

Functional toolbox: recursion

Functional toolbox: folding

Partial application

Composition

Composition

Composition on steroids

Applicative

Applicative

Applicative

Recap

Recommended Reading

Where

Let

FilesExpand file tree

course-03.md

Latest commit

History

course-03.md

File metadata and controls

Functional programming in Haskell

Lesson 3

Previously

Functions

Plain function

Pattern matching function

Pattern matching function

Pattern matching expression: case

Functions with guards

Execution model

Functional toolbox: recursion

Functional toolbox: folding

Partial application

Composition

Composition

Composition on steroids

Applicative

Applicative

Applicative

Recap

Recommended Reading

Where

Let

Pattern matching expression: `case`