More Functional Patterns and Recursion
Tags: functional, haskell
Published: 2019-04-09 06:27:58

---title: More Functional Patterns and Recursion
description: #100DaysOfFP Day 15: Review of Haskell book's 7th and 8th chapters
cover_image: https://images.pexels.com/photos/691710/pexels-photo-691710.jpeg?auto=compress&cs=tinysrgb&dpr=2&h=750&w=1260
series: 100 Days Of FP
tags: fp,haskell
published: true 
---

> I would like to be able to always...divide the things up into as many pieces as I can, each of which I understand separately. I would like to understand the way of adding things up, independently of what it is I’m adding up.
> _Gerald Sussman_

I'm playing a bit of catching up since this corresponds to previous week's session [Delft Haskell Study Group #5](https://www.meetup.com/Delft-Haskell-Study-Group/events/259979758/).

As always, I quote [the book](http://haskellbook.com/) as a way of recap.

## Functional Patterns

### Arguments and parameters

All Haskell values can be arguments to functions, even other functions. This is key in functional programming (FP). A value that can be used as an argument to a function is a _first-class_ value.

**Parameters** are the variables declared in the function definition.

```haskell
add :: Num a => a -> a -> a
add a b = a + b
    ^ ^
    | |
   a & b are parameters
```

**Arguments** are the values applied to a function when calling it. The value of the argument is bound to the named parameter in our function definition.

```haskell
x :: Int
x = 1

y :: Int
y = 2

add x y
    ^ ^
    | |
   x & y ar arguments, bound to add's a & b respectively
```

Applying a function binds its parameters to values. Type parameters become bound to a type, and function variables are bound to a value.

### Pattern matching

One of Haskell's killers features :heart: Whenever I do something in a language that supports it somehow and then go back to JS/TS I suffer a lot :sob:

... is a way of matching values against patterns and, where appropriate, binding variables to successful matches. It is worth noting here that patterns can include things as diverse as undefined variables, numeric literals, and list syntax.

Pattern matching allows you to expose data and dispatch different behaviors based on that data in your function definitions by deconstructing values to expose their inner workings.

**Pattern matching values**

```haskell
isItA :: Char -> Bool
isItA 'a' = True
isItA _   = False


isIt123 :: Int -> Bool
isIt123 1 = True
isIt123 2 = True
isIt123 3 = True
isIt123 _ = False
```

The underscore acts as a wild card, it matches anything. Since it matches anything it has to be the last case, otherwise we'd never get pass it.

**Pattern matching against data constructors**

We can deconstruct data in pattern matching and match against that:

```haskell
withDefault :: a -> Maybe a -> a
withDefault _ Just a  = a
withDefault b Nothing = b

head' :: [a] -> Maybe a
head' []     = Nothing
head' (x:xs) = Just x

first :: (a, b) -> a
first    (a, b) =  a -- notice how much it looks like the signature
```

**Case expressions**

We can also pattern match in case expressions, which are similar to `switch`es from imperative languages. But, as the name suggests, they are expressions.

```haskell
withDefault :: a -> Maybe a -> a
withDefault def maybeA =
  case maybeA of
    Nothing -> b
    Just a  -> a
```

### Higher order functions (HOFs)

Functions that accept functions as arguments. As I said, this is key in FP and allows to combine functions efficiently.

```haskell
flip :: (a -> b -> c) -> b -> a -> c
flip f b a = f a b
```

`f` is a function, making `flip` a HOF.

The book gives many more examples. But really it is a simple concept that is seen all over the place in FP that it can be understood without giving much thought to it.

### Guards

Just a syntax pattern that relies on truth values to decide between two or more possible returns

```haskell
abs' :: Int -> Int
abs' x
  | x < 0 = (-x)
  | otherwise = x
```

`otherwise` is the guard's wildcard and is nothing more than `True`.

```
λ> :t otherwise
otherwise :: Bool
λ> otherwise
True
```

### Function composition

Another of the pillars of FP. Allows us to combine functions such that the result of applying one function gets passed to the next function as an argument.

Compose is defined defined as the dot (`.`) operator:

```haskell
(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)
```

```
λ> :t negate
negate :: Num a => a -> a
λ> :t sum
sum :: (Foldable t, Num a) => t a -> a
λ> :t negate . sum
negate . sum :: (Num c, Foldable t) => t c -> c
λ> negate . sum $ [1, 2, 3, 4, 5]
-15
```

#### Pointfree style

Pointfree refers to a style of composing functions without specifying their arguments. The “point” in “pointfree” refers to the arguments, not (as it may seem) to the function composition operator. In some sense, we add “points” (the operator) to be able to drop points (arguments).

```
λ> f = negate . sum
λ> :t f
f :: (Num c, Foldable t) => t c -> c
λ> f [1, 2, 3, 4, 5]
-15
```

Although `f` has an argument we don't specify it.

```haskell
f :: Int -> [Int] -> Int

f z xs = foldr (+) z xs -- pointfull, all arguments specified

f = foldr (+) -- pointfree, arguments not specified
```

```
λ> f 0 [1..5]
15
```

Another example of composition:

```haskell
putStrLn :: String -> IO ()
show :: Show a => a -> String

print :: Show a => a -> IO ()
print = putStrLn . show
```

## [Recursion](https://dev.to/gillchristian/day-15-more-functional-patterns-and-recursion-4mic#recursion)

Recursion is defining a function in terms of itself via self-referential expressions. It means that the function will continue to call itself and repeat its behavior until some condition is met to return a result.

Comes from the [fixed point combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator) (or Y combinator) of lambda calculus.

The classic recursion example is the factorial (`!`).

```
4! = 4 * 3 * 2 * 1
        12 * 2 * 1
            24 * 1
                24
4! = 24
```

And we can define it as a recursive function.

```haskell
brokenFactorial :: Integer -> Integer
brokenFactorial n = n * brokenFactorial (n - 1)
```

That has a problem though, it keep calling itself infinitely, or in fact until we run out of stack.

We have to define a base case.

```haskell
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)
```

Making our base case an identity value for the function (multiplication in this case) means that applying the function to that case doesn’t change the result of previous applications.

### Bottom

`⊥` or bottom is a term used in Haskell to refer to computations that do not successfully result in a value. The two main varieties of bottom are computations that failed with an error or those that failed to terminate (loop).

Not much more to say about bottom.

**Error**

```haskell
f :: Bool -> Int
f True = error "sarasa"
f False = 0
```

```
λ> f False
0
λ> f True
*** Exception: sarasa
CallStack (from HasCallStack):
  error, called at <interactive>:1:10 in interactive:Ghci1
```

**Loop**

```
λ> x = x in x
*** Exception: <<loop>>
```

## Conclusions

Haskell is not only a functional language but it also offers a few nice things that really make writing code very nice an expressive. I, personally, am a fan of pattern matching, functions defined as infix operators and the [polymorphism model](https://dev.to/gillchristian/day-13-types-59m6#polymorphism). I really miss those features whenever I write code in other languages that don't support them.

Also, this is when the book starts to get interesting. We'll be seeing more code from now on :tada: