# Notes week of 1 Oct

import Control.Monad

# if-then-else expression

We have used Boolean expressions to determine outcomes using the guard notation:

fact n
| n < 0 = error "Negative"
| n == 0 = 1
| otherwise = n * fact (n-1)

Here’s an alternative with nested if-then-else expressions:

factIf n =
if n < 0
then error "Negative"
else if n == 0
then 1
else n * factIf (n-1)

# case expression

We have used pattern matching for function clauses. We can also use the case keyword. The individual cases must be indented and aligned underneath the case keyword.

myAppend xs [] = []
myAppend [] ys = ys
myAppend (x:xs) ys = x : myAppend xs ys
myAppendCase xs ys =
case ys of
[] -> []
_ -> case xs of
[] -> ys
(h:t) -> h : myAppendCase t ys

Instead of nested cases to process each argument, we could process patterns on the pair of arguments (xs,ys):

myAppendCase2 xs ys =
case (xs, ys) of
(_ , []) -> []
([], _) -> ys
(h:t, _) -> h : myAppendCase2 t ys

# More on Maybe

A total function is a function that is defined (returns a value) for every element in its domain (argument type). A function that is not total is called partial.

take and drop are total functions because they produce a result when given any integer and any list:

ghci> take 5 [3,2]
[3,2]
ghci> take (-10) [3,2]
[]

Some examples of partial functions are head and tail (because they fail on empty lists), or div (due to division by zero):

ghci> head [3,5,7]
3
ghci> tail [3,5,7]
[5,7]
ghci> tail []
*** Exception: Prelude.tail: empty list
ghci> div 8 3
2
ghci> div 8 0
*** Exception: divide by zero

One way to transform a partial function into a total one is to have it return a Maybe value. Then we can use Nothing to represent the failure explicitly, or Just to represent a legitimate value. Here is a version of head that is total:

headMay :: [a] -> Maybe a
headMay (h:_) = Just h
ghci> headMay [3,5,7]
Just 3
Nothing

Having the Maybe there forces us to deal with the possibility of failure or missing data. We consider this to be a distinct advantage of typed functional programming. Suppose we want to use headMay to compose strings from parts of other strings:

myName = "Chris"
ghci> headMay myName : "arl"
<interactive>:273:19-23: error:
• Couldn't match type ‘Char’ with ‘Maybe Char’

The error here is telling us that we can’t directly use headMay myName as a character, because perhaps myName was the empty string and so retrieving its head element would fail.

There are a couple ways to deal with this. We can explicitly use a case statement to provide an expression to use in case of failure:

newName1 =
Nothing -> Nothing
Just c -> Just (c : "arl")

That pattern — returning Nothing if the result was Nothing, but applying some operation if the result was Just — is encapsulated into a handy function called fmap. It’s like the map on lists, but applies more generally to other data structures too, including Maybe.

newName2 = fmap (: "arl") (headMay myName)

The parenthesized (: "arl") is an operator section partially applying the list constructor. That means it’s a function which takes the character and joins it to the beginning of the string "arl". The function fmap can also be accessed symbolically with (<$>): newName3 = (:"arl") <$> headMay myName

and then we don’t need the parentheses around headMay myName. We do still need the parens around (:"arl") because it’s an operator section.

tailMay :: [a] -> Maybe [a]
tailMay [] = Nothing
tailMay (_:t) = Just t

# Constructors with arguments

data Point = Point Float Float
deriving Show

Define ‘selectors’ (getters)

getX :: Point -> Float
getX (Point x _) = x
getY :: Point -> Float
getY (Point _ y) = y

Can use a record selector syntax like this:

data Point2 = Point2 { getX2 :: Float, getY2 :: Float }
deriving Show

# Recursive data types

This is equivalent to how the built-in list is defined, but the type name and constructor names are different to avoid conflict:

data List a
= Empty
| Cons a (List a)
deriving Show
myList1 = Cons 8 (Cons 4 (Cons 2 Empty))
myList2 = Cons 8 $Cons 4$ Cons 2 Empty
builtinList1 = 8 : 4 : 2 : []
myString1 = Cons 'C' $Cons 'A'$ Cons 'T' Empty
myLength :: List a -> Int
myLength Empty = 0
myLength (Cons _ xs) = 1 + myLength xs
data BTree a
= Nil
| Node {value :: a, left :: BTree a, right :: BTree a}
deriving Show
myTree =
Node 3 (Node 4 (Node 6 Nil Nil)
(Node 7 Nil Nil))
(Node 5 Nil Nil)
preorder :: BTree a -> [a]
preorder Nil = []
preorder (Node val left right) =
[val] ++ preorder left ++ preorder right
inorder :: BTree a -> [a]
inorder Nil = []
inorder (Node val left right) =
inorder left ++ [val] ++ inorder right

# Function composition

half x = x div 2
square x = x * x

Function composition is denoted by a single dot (.), which we usually surround with spaces.

ghci> (half . square) 6
18
ghci> (square . half) 6
9

The functions are applied right-to-left, so we have:

  (half . square) 6 ↪ half (square 6) ↪ half 36 ↪ 18

(square . half) 6 ↪ square (half 6) ↪ square 3 ↪ 9

You can compose any number of functions in this way. The (.) operator is right-associative.

ghci> (square . half . square . half) 10
144
ghci> (square . square . half . half) 12
81

Here is the derivation for that first example:

  (square . half . square . half) 10
↪ square (half (square (half 10)))
↪ square (half (square 5))
↪ square (half 25)
↪ square 12
↪ 144

# Composing Maybes

Suppose we have versions of the above two functions that return Maybe values to represent some sort of failure. Maybe half only works on even numbers, and square refuses to multiply numbers that are “too large”:

mhalf :: Int -> Maybe Int
mhalf x
| even x = Just (x div 2)
| otherwise = Nothing
msquare :: Int -> Maybe Int
msquare x
| x > 100 = Nothing   -- Too lazy to multiply
| otherwise = Just (x*x)

These can’t directly compose, because one returns a Maybe Int and the next one expects just an Int:

ghci> (mhalf . msquare) 4
<interactive>:320:10-16: error:
• Couldn't match type ‘Maybe Int’ with ‘Int’

However, there is a variant of the composition operator that composes functions returning Maybe values. To access it, we may need this line at the top of our program (or you can type it into GHCI).

import Control.Monad

Then we can do this:

ghci> (mhalf <=< msquare) 4
Just 8

It applies the square and then the half. Assuming both succeed, we get a Just result. But what if one fails? I could apply that to 5:

ghci> (mhalf <=< msquare) 5
Nothing

This squared 5 to get 25, but then mhalf found that 25 is not even, so it produced Nothing. The first operation can fail too. Here’s an example of that:

ghci> (mhalf <=< msquare) 128
Nothing

In this case, msquare refused to multiply and produced Nothing. So then the “pipeline” came to a halt — there was nothing available to pass to mhalf.

# Either data type

data Either a b = Left a | Right b
main = return ()