More Functional Patterns and Recursion

Originally posted on dev.to/gillchristian.

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.

As always, I quote the book 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.

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.

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 ♥️ Whenever I do something in a language that supports it somehow and then go back to JS/TS I suffer a lot 😭

... 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

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:

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 switches from imperative languages. But, as the name suggests, they are expressions.

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.

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

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:

(.) :: (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.

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:

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

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

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 (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.

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.

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

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. 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 🎉