this is the 3rd part of our tutorials which aim to make people more familiar with functional programming and the functional thinking in general, if you are new to functional programming, be sure you take a look at the first two parts here :
- http://dev.martani.net/2009/07/understand-functional-programming-with.html
- http://dev.martani.net/2009/07/understand-functionnal-programming-with.html
Today I’ll explain the most important point about functional programming, which is obviously functions. as you can guess it’s called functional programming because functions are first class citizens here, they are so special and powerful, we will take a look at how to define functions, understand their types, some pattern matching tricks and a little examples to make you think functionally and get out of the imperative box.
How to define a function in OCAML (as I always say, it’s also F# compatible):
this is the general syntax for defining functions
let [function_name] [param_1] [param_2] … [param_n] =
[the function code goes here] ;;
As you ca see, you provide the function name after the let keyword, the same allowed variable name rules in other languages apply here, for example you can’t have a function named “4342” or “ZER zer” that’s obvious.
then comes the input values or the parameter names, parameters are delimited by spaces (not commas like in the other languages), as I explained the reason of this in the second part of this series.
let’s see that example :
let fun1 x y = do_things_here;;
let fun2 (x, y) = do-other-things-here ;;
those two functions are totally different, fun1 accept two generic parameters x and y (ah, you wonder what are generics?? don’t worry we will talk about that), and fun2 accept one parameters which is the tuple (x, y). Part 2 is so important since understanding functional programming is about understanding types!
there are also other ways to define functions:
- the fun keyword : this type of declaration is used when working with iterators to define functions on the fly (like anonymous functions for the .NET framework or lambdas)
let [function_name] = fun [param_1] … [param_n] –>
[function boddy here];;
this is an example of a function that returns the sum of two values :
let add = fun x y –> x + y;;
the first type of syntax is just a shortcut for this one, we can define it as follows
let add x y = x + y;;
- the Function keyword : this is the same as the above case, I didn’t encounter a case where I can use Function and not fun. So the same rules applied for fun are also valid for Function.
- with partial definition : this is quite an advanced topic that we will talk about in the future parts, but for now keep in mind that you can obtain functions as a return type of other functions or expression:
For example, taking the List.for_all iterator we can define a function that tests is a list have just positive values like follows
let is_all_positive = List.for_all (fun x –> if x >= 0 then true else false);;
or :
let predicate x = if x >= 0 then true else false;;
let is_all_positive = List.for_all predicate;;
well that is, now we can pass a list and the function will return a bool indicating if all the elements are positive or not, for example :
is_all_positive [3,56,23,0];; (* returns true*)
well, if you are new to functional programming, you may have not noticed anything at all going here, if your head is starting to think functionally then it should be blocking now, and if you are an advanced functional programmer then you might be having a big smile now for the beauty of what you are looking to :)
the first question is, how the is_all_positive function knows about it will be having a list as a parameter? simple, the inference engine knows everything :), you will see why once we discuss generics.
second : we don’t see anywhere in the code that we told is_all_positive that it will take a parameter at all, how is that possible? this is a little advanced topic, called partial application, but this is how it works in general : if we don’t mention the last parameter when we apply a function partially, it returns a function which will have that parameter for example :
let add x y = x + y;;
let add_x_to_10 = add 10;;
it might seems a little complicated for now, but once you get used to functions types, you will see more clearer.
Function types, the secret behind understanding functional programming
This is the most important part to understand function programming, function types. Let’s start with the simplest function that take one parameter and return a simple data type (yes a function can return a function too :D )
let fun1 x = x + 1;;
this is the simplest function ever, it takes one parameter which is an int (an int not float, not string, see part 2 for that, “+” applies only to int, in F# that’s another story, let’s keep OCAML for now), and simply returns an int which represents the successor of x.
To express the type of that function, we use an advanced (weird for imperative people) representation, if you type this in OCAML you get the following type :
# let fun1 x = x + 1;;
val fun1 : int -> int = <fun>
the type is what’s behind “val fun”, as you see functions are values like everything else, they can be returned in any expression in your code.
more specifically the type is int –> int which means the function take an int and returns an int, not that complicated after all !
now let’s see a function with 2 parameters :
# let fun2 var1 var2 = var1 + var2;;
val fun2 : int -> int -> int = <fun>
now if you see the type it is int –> int –> int, so is translates to the function take an int and an int and returns an int? not really, this is an imperative thinking! in fact putting parentheses will clarify things a little bit:
this type int –> int –> int could be read like follows int –> (int –> int), in function type, parentheses are right associated! so for now we can read it as follows : the fun2 takes an int and returns a (int –> int) which is like in the first example a function which in it’s turn take an int and returns an int.
In other words, fun2 takes an int and returns a function of type (int –> int)
this is how the compiler see the function :
let fun2 var1 = (fun var2 –> var1 + var1);;
be sure you understand what is happening here? if you can’t see all the picture then you can’t go anymore in your way understanding functional programming, here is a simple concrete example :
# let add x y = x + y;;
val add : int -> int -> int = <fun>
now :
# add 4 7;;
- : int = 11
# add (-2) 4;;
- : int = 2
notice that when passing negative values you have to embrace them with parentheses, let’s consider now passing one argument to this function, that sound not valid in the imperative style but it’s the key of success in functional programming:
# add 6;;
- : int -> int = <fun>
so what just happened? passing one argument to the add function doesn’t cause an error but returns another function which has the type (int –> int), you can define another function from this one like follows :
# let add_to_6 x = add x 6;;
val add_to_6 : int -> int = <fun>
or simply as we stated before :
# let add_to_6 = add 6;;
val add_to_6 : int -> int = <fun>
here we just defined a function that adds 6 to any other number, using the function that add two numbers.
you might not realize the use of that now, but be sure that will save you someday :)
Types, types and type:
as I stated before (in the previous parts), every expression in the OCAML code has a type, and by every I mean ALL of them, for example consider this piece of imperative code :
int a = 23;
int s = “a cool string”;
bool b = true;
if (b = true)
a = 123;
else
s = “b is not true”;
that’s a totally valid code in C# or other languages, if you are used to this type of code (chances are your 99% are used to), you will have to change a little of the way you deal with your code, in fact in OCAML even the if statement must return (must have in other words) a type, and a unique type.
means that the type of the if part must be the same as the type in the else part, for example
let x = if 1 = 1 then
3
else
"this is impossible";;
in this piece of code, we wanted x to be the int 3 if 1 is equal to 1, otherwise take the value of the string “this is impossible”.
this is what we get after typing this in OCAML:
Characters 39-59:
"this is impossible";;
^^^^^^^^^^^^^^^^^^^^
Error: This expression has type string but is here used with type int
as you see, the compiler is stating that we used a string in a place where it expects an int, why that? because the if block must return one type, whether the condition is valid or not, as you see in that case that it will never reach the else, but the OCAML compiler is so strict, that will bother you a little but you will love it once you get your hands coding.
did I mention that you can return functions from if blocks?? yes, you can, let see this :
# let give_me_a_function b =
if b then
fun x -> x + 10
else
fun x -> x * 10;;
val give_me_a_function : bool -> int -> int = <fun>
as you see here, we have a function “give_me_a_function” that takes a boolean and returns a function according to the value of that boolean, if true, a function that adds 10 to it’s parameter, of multiply it by 10 otherwise.
so let’s apply some of what we learned so far, we can define a partially function from this one like follows :
# let add_to_10 = give_me_a_function true;;
val add_to_10 : int -> int = <fun>
# add_to_10 13;;
- : int = 23
# let by_10 = give_me_a_function false;;
val by_10 : int -> int = <fun>
# by_10 23;;
- : int = 230
cool isn’t it? a function that returns functions? not just that but an if…then…else block that returns two different functions.But… that doesn’t mean t return any function it wants, remember that is has to return one and only one type, so all the functions that can be returned must have the same type (signature in other words).
we can apply the “give_me_a_function” directly like this
# (give_me_a_function false) 27;;
- : int = 270
we can apply directly the if statement returning a function to parameters :
# (if true then fun x -> x + 4 else fun x -> x - 4) 27;;
- : int = 31
Recursive functions :
recursive functions are a key feature in functional programming, you may use recursive functions so frequently in your code, like you use for loops in the imperative world.
to define a recursive function you add the rec keyword before the function name like in the following example :
# let rec fact n =
if n = 0 then
1
else
n * fact ( n - 1);;
val fact : int -> int = <fun>
this is a simple example of a recursive function that calculates the factorial of a positive number, if you don’t provide the rec keyword in a recursive function you will get an error.
this was a sneak peak on recursive functions which are so important, we will discuss them with details in the next tutorial along with, pattern matching, tail recursion and we will dig more vast and real functions using more daily used examples.
Did you understand function types?
try to figure out the types of the following function and if they are valid or not (most of them has not a valid type), the answers are in the end of the post. Be sure you understand the Part 2 and this part before you try to solve those little questions, if you solve 40% of these then consider yourself eligible to pass to the next part, otherwise you may need to read it again.
# let add x y z = x + y / z;;
# let add2 x y z = x + y /. z;;
# let add3 x y = add1 x y;;
# let f1 = fun x -> x^"sssssss";;
# let f2 = fun x -> fun y -> x@y;;
# let f3 x = fun y -> x::y;;
# let f4 =
if true then
fun x y -> x + y
else
fun x y -> x +. y;;
let f5 x y z =
if y then
x
else
z +. 2.;;
let f5 m =
if fst m then
if snd m then
(fst m) && (snd m)
else
not (fst m)
else
m + 7;;
Answers will be posted soon.
