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.
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.
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
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.
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
λ> :t otherwise otherwise :: Bool λ> otherwise True
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 (
(.) :: (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 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
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 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.
⊥ 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.
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
λ> x = x in x *** Exception: <<loop>>
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 🎉