[2008.07.08] Functions, Monoids and Monads [Part I/IV]

Introduction

Since most of us are probably imperative programmers, we understand how to deal with functions in the imperative world. Imperative programming, however, treats functions a little differently and I hope to illustrate how to translate functions from the imperative to functional environment.

The results of this post and others in the series come from my own reading on FP but is primarily derived from talks by Brian Beckman and Erik Meijer, both from Microsoft Research.

[1] FUNCTIONS

• the idea behind functional programming is to program with mathematical functions where both code and functions are treated like data
• we understand that int x means the variable x is of type int or mathematically this is equivalent to saying x is an member of the set of integers
• we want to do a change of notation and replace int x with x:int and they both mean the exact same thing, that is, x is of type int
• now extend this change of notation to functions so instead of writing something like int f(int x) we can write f:int -> x which is saying that this is a function that takes and int and returns an int (recall that x was defined as an int (x:int) )
• instead of picking a particular type, let us make the type generic and call it type a
• therefore we can have a few assertions:
  • x:a , assert that x is of type a
  • f:a -> a assert that the function f takes a type a and returns a type a where a is any type

• function composition is just another term for calling a function in FP
• given the following definitions:
  • x:a means that x is of type a
  • f:a -> a means f is a function that takes a type a and returns a type a
  • g:a -> a means g is a function that takes a type a and returns a type a
• we can combine f and g and make them into one function using two methods:
  • [1] method1: call g(a) and then call f on the result to get f(g(a)) or
  • [2] method2: call f(a) and call g on the result to get g(f(a))
• either method produces a new function and these methods are how we normally call functions, that is, it is the notation we use the most and are more familiar with especially in imperative programming

• now move the idea of calling functions in the imperative world to the functional world by first removing the parenthesis around g(a) in method1 to get g a
• g a means that we are calling the function g with an argument of type a
• note that this looks like multiplication and it is done deliberately even though g may not be a linear function because it allows us to treat functions as data in a more natural way

• remove the parenthesis around the final expression in method1 and you will get f g a
• this means that we have a composition of two functions and both functions are called on the argument a
• the order of this calling is this: since f is the first function defined, it will be the first to be called passing in a as an argument ( basically saying f(a) ), then the result of this is passed as an argument to the function g ( basically saying g(f(a)) )
• notice that our change of notation changes the order of how the functions are being called
• if you want to call g first, you can use parenthesis like f(g a) or do g f a