Posted in f#, functional, math

How functional programming helped me recognise patterns and concepts in mathematics

I've never been strong at mathematics, and to this day I don't believe you need to be a skilled mathematician to be a good developer, but as time has gone on I've found more and more value in being able to understand and implement algorithms and expressions, which are fundamentally described in mathematics.

The more natural functional concepts become to me, the more I've become to recognise patterns in expressions - being able to break them down and remove the complications which used to baffle me.

I can now understand why maths and FP fit so naturally, and it's because of the ease of which it is to apply patterns; how easy it is to represent them in code.

This is a strange way to go about picking up mathematics and it wasn't at all intentional. Many problems with functional complexity such as; keeping functions pure but requiring side effects; passing state; error handling etc. Have found elegant solutions fundamentally adapted from abstract mathematics - The monad (from category theory) is a great example.

Breakdown

To help explain what I mean when I say identifying patterns, and how they map onto FP, lets take this statement, which defines the product of logarithm.

logarithm product

Looking at this equation, to solve it would be quite simple; add log(x) to log(y) and that gives us our answer.

log(20 * 30) = log(20) + log(30) = 2.778

This is interesting from a code perspective, it's the same log function (logb(x)) if we replace logb() with something we essentially have F(xy) = F(x) + F(y). The logb() is irrelevant, we could put any function in there. In fact it doesn't even need to be a function! It's just a type that wraps some value, therefore; we can go a step further and make it generic. Let's look at some code to see how we can work with this.
We will first need to declare a type, which can hold a value.

// directly represents F(x)
type F<'a> = F of 'a  

We can wrap our values in this new F type; any value we want, it can even be a function we wrap!
In order to replicate getting the product of our new type and actually be able to do any work, we are going to need to define some functions, which are capable of working on our new elevated values. Reason being, we can't use basic functions such as addition, subtraction etc... But more on that later...

We need to be able to add, subtract, multiple, divide these wrapped values, so in comes pure, apply and fmap to help us build up these functions.

// pure (aka return) - takes a value and wraps it
let pure' x = F x

// apply - unwraps an elevated function and applies an unwrapped value,
// wrapping up the result.
let apply (F fn) (F v) = F (fn v)

// a common infix for apply, makes it nicer to chain.
let (<*>) x fn = apply fn x

// takes a regular function and applies it to a wrapped value,
// returning a wrapped result.
// we can make fmap from both our pure' and apply functions
let fmap fn x = pure' fn <*> x

// infix for fmap
let (<!>) x fn = fmap fn x  

These functions are fundamental when working with our wrapped type. They are all well known patterns and are very handy when composing new functions.

fmap is the function we will find most useful here, without going into too much detail you can think of fmap similar to C#'s IEnumerable<> extension Select - which unwraps an IEnumerable and applies a normal function to each item in the collection, wrapping up the result. Similar deal with fmap, only our fmap works on the type F rather than an IEnumerable.

Back to the reason why we need these - We have to have a way to compose functions in this higher, elevated world. For example, if we have a wrapped value:

let val = F 10  

And we want to add 5, we can't simply do:

let valPlus5 = val + 5  
-- compile error

Because (+) takes 2 number arguments and returns a number (+) : int -> int -> int. Our val is not a number; it's an F<int>
That's where fmap (or it's infix ) comes in!
We need a way to squeeze our F value through an ordinary (+) 5 function.

let valPlus5 = val <!> ((+) 5)  
-- F 15

fmap Lets us chain these operations together, just like we can do with (+).

let val = 5 + 10 + 34 + 62

let val' = F 5 <!> ((+) 10) <!> ((+) 34) <!> ((+) 62)  

By this point it should be a little clearer how we are going to solve our equation: F(xy) = F(x) + F(y). But before we are ready, there is one more helper function we can make to get us on our way.

:: lift2 : fn:('a -> 'b -> 'c) -> F<'a> -> F<'b> -> F<'c>
let lift2 fn (F v1) (F v2) = F (fn v1 v2)  

lift2 is essentially fmap2. It applies a regular function which takes 2 arguments to 2 unwrapped values, it's going to help when we come to solving quotent and power too.

Firstly though, let's go back to that addition stuff we just did and see if lift2 can help tidy it up.

let (++) = lift2 (+)  
let val' = F 5 ++ F 10 ++ F 34 ++ F 62  

Better, using lift2 we can compose a function which takes 2 elevated values and applies an ordinary function to it; finally wrapping up the result, which enables chaining.

Product

Now we have the functions defined to work with our type, we can do what we came here to do, find the product of log. Using the same idea we just used for addition, we can also apply to product:

// gets the product of two elevated values
// replicates combine - F(xy) = F(x) + F(y)
// add is associative (order doesn't matter)
let product = lift2 (*)  
let (>*) = product

let inline log10 v = v |> (float >> System.Math.Log10)  
let productResult = F 20 >* F 30 <!> log10  
-- 2.77815125

And there's our result. You will notice that it's only at the last stage of composure do we actually apply log (log10 in this case for ease).

Quotent, power and root

We can implement and use the other three laws of logarithms in the same way.

// opposite of product
let quotent = lift2 (/)  
let (>/) = quotent

// to power
let power = lift2 <| fun x y -> System.Math.Pow(float x, float y)  
let (>^) = power

// square root
// we don't need lift2, Sqrt takes only a single argument.
let root = fmap System.Math.Sqrt


let quotentResult = F 10 >/ F 2  
-- F 5
let powerResult = F 10 >^ F 2  
-- F 100.0
let rootResult = F 10.0 |> root  
-- F 3.16227766

We don't really need to write all of this for these simple calculations, it's a big abstraction for a little problem, we aren't gaining much just calculating the product of log. In real terms though there is a lot of benefit from working with monadic types like this, and to recognise these patterns and implement them has helped join a few dots for me.

Real value

In practical terms, analysing data; running predictive algorithms (and much more) are all described in the language of maths. Being able to translate these algorithms into practical applications is a good thing, and it starts with recognising patterns and being able to apply them. I'm not really interested in being able understand complicated theory if I can't apply it.

In terms of why we would want to work on an abstraction (like our F type) in a real program, there are a few reasons; which I will very briefly mention:

  • Error handling
  • Side effects
  • Logging/Diagnostics
  • Chaining

For example, we can add a side effect to our apply function, which logs to the output stream the result of the function. Useful for debugging or logging maybe?

let apply (F fn) (F v) =  
    let fnResult = fn v
    printfn "applied value: %A, result is: %A" v fnResult
    F fnResult

Round up

Tackling these concepts from a computer science first view has helped me identify similar patterns where they exist in mathematics. It has allowed me to find a connection between FP and the more abstract concepts in maths.

I've dived into a lot of FP here and it's not really the important part, but it's a good example of how we can work with maths in FP in a flexible and usable way.