Maybe PracticalHaskell

class: center, middle, inverse

# Maybe PracticalHaskell

---
# Why learn Haskell?

- Functional programming will make you think differently about programming.
  - Mainstream languages are all about state
- Haskell is “cutting edge”
  - A lot of current research is done using Haskell
  - Rise of multi-core, parallel programming likely to make minimizing state much more important
- New ideas can help make you a better programmer, in any language

---
# Why learn Haskell?

.left[![Right-aligned image](figures/hughes.png)]

.footnote[[Why Functional Programming Matters](https://www.youtube.com/watch?v=XrNdvWqxBvA)]

---
# Maybe you know Haskell already...

- If you know C, you know Python.
- If you know C++, you know Java.
--

- [Haskell]() is a completely different beast
  - It is a different way of thinking about programming.
  - It twists the brain in delightful ways.
  - It is beautiful.
--

- But can I use it to solve real-world problems like Java?

---
# Life of a research language

.center[![haskell second life](figures/death1.png)]

.footnote[[Simon Peyton Jones - A History of Haskell: being lazy with class](https://www.youtube.com/watch?v=06x8Wf2r2Mc)]

---
# Life of a "successful" research language

.center[![haskell second life](figures/death2.png)]

.footnote[[Simon Peyton Jones - A History of Haskell: being lazy with class](https://www.youtube.com/watch?v=06x8Wf2r2Mc)]

---

# Haskell's second life

.center[![haskell second life](figures/threshold.png)]
.footnote[[Simon Peyton Jones - A History of Haskell: being lazy with class](https://www.youtube.com/watch?v=06x8Wf2r2Mc)]

---

# Haskell's second life

.center[![haskell second life](figures/secondlife.png)]
.footnote[[Simon Peyton Jones - A History of Haskell: being lazy with class](https://www.youtube.com/watch?v=06x8Wf2r2Mc)]

---

# Haskell's second life

- Big Data: MapReduce

- Concurrency (Future, Promises, Observables)

- User Interfaces (Reactive functional programming)

- Neural Networks (Differentiable functional programming)

---
# A user-defined list in Haskell

```haskell
data List a = Empty | Cons a (List a)
```

A user-defined data record to model a list of `a`s
  - `Empty` represents the empty list
  - `Cons a (List a)` recursively defines a list as a pair:
       1. a element of type `a` 
       2. followed by a list.
  - Haskell's standard list is nothing special; similar definition in prelude:
    ```haskell
    data [] a = [] | a : [a]
    infixr 5 :
    ```
--

### Examples:

```haskell
Empty                            -- []
Cons 'a' Empty                   -- ['a']
Cons 1 (Cons 2 (Cons 3 Empty))   -- [1,2,3]
```

---

# Operations on our user-defined list

```haskell
filter :: (a -> Bool) -> List a -> List a
```
- takes a predicate function and a list
- returns a new list with only the elements that satisfies a predicate.

```haskell
filter f Empty = Empty
filter f (Cons x xs) = if f x then Cons x (filter f xs) else filter f xs
```

Another way to define the same thing using Haskell's `case`:

```haskell
filter f l =
      case l of 
        Empty     -> Empty
        Cons x xs -> if f x then Cons x (filter xs) else filter f xs
```

---

# Check for membership

Let's start using our `List` by defining some simple operations.

```haskell
member :: Eq a => a -> List a -> Bool
```

- takes an element (that we know how to check for equality) and a list
- returns true if a specific element is in the list, otherwise false.

```haskell
member x l = 
  case l of 
    Empty     -> False
    Cons y ls -> if (x == y) then True else member x ls
```

- Which lists we can use?
  Only lists of some type that we know how to check for equality. 
  For example, `Int`, `Char` and so on ...

- Can we use `List`s of `List`s?

---

# Checking two lists for equality

The `Eq a` in `member` is a type class that assures that the function `==` 
is defined for the specific type `a`.

```haskell
class Eq a where
  (==) :: a -> a -> Bool
```

- We can define the `==` for `List`s
- Two lists are equal if have exactly the same elements in exactly the same order.
- "Exactly the same elements" implies that we should be able to check if two elements are equal.

```haskell
instance Eq a => Eq (List a) where
  Empty       == Empty       = True
  (Cons x xs) == (Cons y ys) = (x == y) && (xs == ys)
```

Now, we can use `member` in `List`s of `List`s!

---

# Point-wise operations: mapping

```haskell 
map :: (a -> b) -> List a -> List b
```

- takes a function `f` and a list
- applies `f` for each element in the list
- returns the list with the result of the application

```haskell
map f l = 
  case l of 
    Empty     -> Empty
    Cons x xs -> Cons (f x) (map f xs)
```

### Examples:

```haskell
sq x = x * x

sqAll l = map sq l

sqAll (Cons 1 (Cons 2 (Cons 3 Empty))) -- (Cons 1 (Cons 4 (Cons 9 Empty)))
```

---
# A different map

- `map` restricts us to map each element of the input list 
  to exactly one element of the output list.

- What if we want to output multiple items for each element?

- In other words, to apply the function `sqsq :: a -> List b`
  ```haskell
  sqsq n = Cons n (Cons n*n Empty)
  ```

- If we apply directly `map` to `sqsq` we will get
  ```haskell
  map sqsq (Cons 1 (Cons 2 (Cons 3 Empty))) = (Cons (Cons 1 (Cons 1 Empty) (Cons () Cons () Empty))
    -- [[1,1], [2,4], [3,9]]
  ``` 
  but we want a single "flattened" list
  ```haskell
    -- [1, 1, 2, 4, 3, 9]
  ```

---

# A different (flattened) map

```haskell
flatMap :: (a -> List b) -> List a -> List b
```

Let's re-use `map` and then define a `flatten` function that 
remove the inner list

```haskell
flatten :: List (List a) -> List a
flatten Empty       = Empty
flatten (Cons x xs) = concat x (flatten xs)
```

- `concat` for `List` not shown here but it has the same effect like `++` for `[]`

``` haskell
flatMap f l = flatten (map f l)
```

---
# Expressions that might fail

- We want to define the function `head` that returns the first element of a `List`

``` haskell
  head :: List a -> a
  head (Cons x xs) = x
  head Empty       = ??
  ```
  What we should return when the list is empty?

- An idea is instead of returning `a` we might return `List a` 
  ```haskell
  head :: List a -> List a
  head (Cons x xs) = (Cons x Empty)
  head Empty       = Empty
  ```

- Haskell has a more elegant way to define values that sometimes fail to return something

``` haskell 
 head :: List a -> Maybe a
 ```

---
# Optional values

```haskell
data Maybe a = Nothing | Just a
```

A user-defined data record to model an optional value:
- `Nothing` represents that there is no real value
- `Just a`  represents that there is a value

- This is the Haskell equivalent of `null` but better
- So much better that Java, C++ and others ban `null`s and start using `Option`, `Optional` and the likes.

``` haskell
head :: List a -> Maybe a
head (Cons x xs) = Just x
head Empty       = Nothing
```

### Aside note

Notice the resemblance with the `List` definition:

```haskell
data List a = Empty | Cons a (List a)
```

---
# Maybe functions

```haskell 
lookup :: k -> Map k a -> Maybe a
```
searches a key-value map for a key `k` and returns the value if the key exists.

```haskell
stripPrefix :: Text -> Text -> Maybe Text
```
drops the given prefix from a text. If the list did not start with the prefix given,
then returns nothing otherwise it returns the text without the prefix.

```haskell
port :: URIAuthority -> Maybe Int
```
takes a URI as input and returns the port if specified in the URI

---
# Finding the index in a list

The function `elemIndex`

``` haskell
elemIndex :: Eq a => a -> List a -> Maybe Int
```

- takes an item and a list
- if the item is in that list returns the index

```haskell
elemIndex :: Eq a => a -> List a -> Maybe Int
elemIndex c Empty = Nothing
elemIndex c (Cons x xs) = 
  if c == x 
  then Just 1
  else case (elemIndex c xs) of
          Just n  -> Just (n+1)
          Nothing -> Nothing
```
- We recursively call `elemIndex` to check if it is in the rest of the list
- The `elemIndex` returns a `Maybe` value so we need to 
  dig into the structure of `Maybe` which is ugly.

---

# Refactoring the elemIndex

Ideally, we want an operator `phi` that will unwrap the `Maybe` value and 
rewrap it after applying a function to the actual value.

```haskell
phi :: (a -> b) -> Maybe a -> Maybe b
```

```haskell
phi f a = 
  case a of 
    Nothing -> Nothing
    Just x  -> Just (f x)
```

and the `elemIndex` becomes:

```haskell
elemIndex :: Eq a => a -> List a -> Maybe Int
elemIndex c Empty = Nothing
elemIndex c (Cons x xs) = if c == x then Just 1 else phi (+1) (elemIndex c xs)
```

---
# Maybe map

Lets compare the definition of `phi`
```haskell
phi :: (a -> b) -> Maybe a -> Maybe b
phi f a = 
  case a of 
    Nothing -> Nothing
    Just x  -> Just (f x)
```

with the `map` operations in `List`s
```haskell
map :: (a -> b) -> List a -> List b
map f l = 
  case l of
    Empty -> Empty
    Cons x xs -> Cons (f x) (map f xs)
```

The `phi` operator is a degenerate version of `map`!

---

# The Functor type class

Instead of having different names for `List` and `Maybe` we unify them
in a single concept (just like `Eq`).

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

```haskell
instance Functor List where
  fmap h Empty       = Empty
  fmap h (Cons x xs) = Cons (h x) (fmap h xs)
```

```haskell
instance Functor Maybe where
  fmap h Nothing  = Nothing
  fmap h (Just x) = Just (h x) 
```

There are many structures in Haskell that are `Functor`s

.footnote[https://hackage.haskell.org/package/base-4.14.1.0/docs/Prelude.html#t:Functor]

---

# A different perspective of Functor

Notice the type of `fmap`
```haskell
fmap :: (a -> b) -> f a -> f b
```
we can group the type:

```haskell
fmap :: (a -> b) -> (f a -> f b)
```
and perceive `fmap` as  a operation that 
  - takes a function `a -> b` and 
  - returns a *lifted* function that can now operate on the `f a -> f b`

.center[
  ![:scale 35%](figures/functormaybe.jpg)
]

---

# The equivalent of flatMap for Maybe

The `flatMap` for `List`s is

```haskell
flatMap :: (a -> List b) -> List a -> List b
```

so the equivalent for `Maybe` is

```haskell
flatMapMaybe :: (a -> Maybe b) -> Maybe a -> Maybe b
```
- if the second argument is an actual value then apply that 
  value to the function
- if the function returns an actual value `b` then return that

```haskell
flatMapMaybe f Nothing  = Nothing
flatMapMaybe f (Just x) = f x
```

---
# Chaining a sequence of Maybes

We have a sequence of operations that might fail to 
return a result.

```haskell
getHeader :: String -> MimeMessage -> Maybe String
```
takes a mail header and returns the value of a specific header (if exists)

```haskell
parseDate :: String -> Maybe Date
```
returns a date or nothing if the string is not a valid date

```haskell
mailboxForDate :: Date -> Maybe Mailbox
```
returns the mailbox for that date or nothing if the mailbox do not exist.

``` haskell
getMailbox :: MimeMessage -> Maybe Mailbox
getMailbox message =
  case getHeader "Date" message of
    Nothing -> Nothing
    Just dateString  ->
      case parseDate dateString of
        Nothing -> Nothing
        Just date -> mailboxForDate date
```

---

# Chaining Maybes

Lets assume we have the operator
```haskell
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
```

we can rewrite `getMailbox` as

```haskell
getMailbox message =
  getHeader "Date" message >>= parseDate >>= mailboxForDate
```

```haskell
Nothing  >>= f = Nothing
(Just x) >>= f = f x
```

--
### Aside note:

```haskell
flatMapMaybe :: (a -> Maybe b) -> Maybe a -> Maybe b
flatMapMaybe f Nothing  = Nothing
flatMapMaybe f (Just x) = f x
```

The `flatMap` is the `>>=` with its arguments flipped!

---
.center[![Haskell logo](figures/haskell_logo.svg)]

---
# Monads

> If we have a fancy value and a function that takes a normal value but returns
  a fancy value, how do we feed that fancy value into the function?

```haskell
class Monad m where
  return :: a -> m a
  (>>=)  :: m a -> (a -> m b) -> m b
```

``` haskell
instance Monad Maybe where
  return x = Just x
  Nothing  >>= f = Nothing
  (Just x) >>= f = f x
```

--
```haskell 
instance Monad List where
  return x = Cons x Empty
  Empty >>= f       = Empty
  (Cons x xs) >>= f = Cons (f x) (xs >>= f)
```

---
# The do notation

Monads are so popular that have a special treatment in Haskell.

Instead of writing `getMailbox` as
```haskell
getMailbox msg =
  getHeader "Date" msg >>= \dateStr ->
  parseDate dateStr    >>= \date ->
  mailboxForDate date  >>= \mbox ->
  return mbox
```

we can use the `do` notation that resembles an imperative style of programming 
but is actual functional.

```haskell
getMailbox msg = do
  dateStr <- getHeader "Date" msg
  date    <- parseDate dateStr
  mbox    <- mailboxForDate date
  return mbox
```

---
# The do notation on lists

```haskell
p = do
  x <- ['a', 'b']
  y <- [1..5]
  return (x,y)
```
will evaluate to:

```haskell
[('a',1),('a',2),('a',3),('a',4),('a',5),('b',1),('b',2),('b',3),('b',4),('b',5)]
```

--
## Aside note:

Now, try the list comprehension:

```haskell
p' = [ (x,y) | x <- ['a', 'b'], y <- [1..5] ]
```

---

# Monads

>  Once you understand monads, you immediately become incapable of explaining them to anyone else.
Lady Monadgreen’s curse ~ Gilad Bracha (used famously by Douglas Crockford)

## Cheatlist:

- Monads help to create cleaner code when dealing with computation that need contexts or have effects.

- There are many useful Monads in Haskell and other languages.
  - Computations that need to maintain `State`
  - Computations that may throw `Exception`s
  - Computations that need to perform `IO`

- The use of effects is *explicit* in types.

- Many programming languages employ monads without saying that it is a monad
  to not scare programmers! But now you know when you see a `flatMap` in your Javascript.

---

# Hello World (at last)

``` haskell
main :: IO ()
main = putStrLn "hello, world"
```
--
```bash
ghci> :t putStrLn
putStrLn :: String -> IO ()
ghci> :t putStrLn "hello, world"
putStrLn "hello, world" :: IO ()
```
--
```haskell
main = do
  putStrLn "Hello, what's your name?"
  name <- getLine
  putStrLn ("Hey " ++ name ++ ", you rock!")
```

```bash
ghci> :t getLine
getLine :: IO String
```

---
# We can read from files!

```haskell
import Data.Char

main = do
  contents <- getContents
  putStr (map toUpper contents)
```
---
# Resources

- Books
  - [Learn you a Haskell for greater good](http://learnyouahaskell.com)
  - [Real World Haskell](http://book.realworldhaskell.org/)
- Languages
  - [Scala](https;//www.scala-lang.org)
  - [F#](https://fsharp.org)
  - [Frege](http://www.frege-lang.org)
  - [PureScript](http://www.purescript.org)
  - [ReasonML](https://reasonml.github.io)

---
# Either

```haskell
data Either a b = Left a | Right b
```
```haskell
divBy :: Int -> [Int] -> Either Error [Int]
```
--
```haskell
divBy _ []    = Right []
divBy _ (0:_) = Left "divBy: division by 0"
divBy numerator (denom:xs) =
 case divBy numerator xs of
 Left x -> Left x
 Right results -> Right ((numerator `div` denom) : results)
```