Let’s start to use functional programming! — Part 2

In the first part of this blog post — you can find it here — we introduced functional programming.
Let’s start seeing fun and interesting things like pattern matching, recursion and list type!

Recursion

Perhaps the classic example that comes up when talking about recursion is the sum of the first N numbers.
Let’s see how to define a function about it in OCaml.

let rec sumFirstN n = 
  if n = 0 
    then 0
  else n + sumFirstN (n-1) 

Note the rec keyword to indicate that the function is a recursive function.
I would like to draw attention to the last line, which fully expresses the concept of recursion: n + sumFirstN(n-1)
If I have the sum of the first (n-1) numbers, the only thing I have to do is add n !

As we learned, sumFirstN is a function that takes an int as input and produces an int as output.

List type

A list is mutable homogeneous set of values — unlike tuples which have a fixed size.
A list is declared with square brackets and the elements are separated from each other with semicolon symbol.

let lst = [1;2;5;2;4;9;1]

Be careful not to use commas.

If a list of integers has type int list, what type does a list of pairs have?
Obviously ‘a*’a list.

Any list can be constructed starting from the empty list using the :: operation which represents the insert operation in front.
Let’s see an example.

[1;9;2;4]
= 1 :: [9;2;4]
= 1 :: 9 :: [2;4]
= 1 :: 9 :: 2 :: [4]
= 1 :: 9 :: 2 :: 4 :: []

To introduce the concept of pattern matching let’s see an exercise about lists.
We want to create a function that adds all the elements of a list.

let rec sum_all lst =
match lst with
  | [] -> 0
  | [x] -> x
  | x :: rest -> x + sum_all rest

let’s analyze the definition of the function line by line

• let rec sum_all lst
  sum_all is a recursive function that takes a parameter as input, lst
• match lst with
  pattern matching for lst variable
• | [] -> 0
  if the list is empty, the sum of the values inside is 0
• | [x] -> x
  if the list contains only one element, the sum is that value
• | x :: rest -> x + sum_all rest
  If the list contains multiple elements it can be expressed as x :: rest — x is the first element and rest is the remaining list.
  The sum is then x + the sum of all elements of rest.

sum_all is therefore a function that receives as input a list of integers and returns an integer.

Another way to define the function is as follows

let rec sum_all = function
  | [] -> 0
  | [x] -> x
  | x :: rest -> x + sum_all rest

Let’s see several examples.

Max value in a list

# val max_value : 'a * 'a -> 'a = <fun>
# max_value (a,b) return a if a>b
let max_value (a,b) =
  if a>b
  then a 
  else b
  
let rec max_in_list = function 
  | [x] -> x
  | x :: rest -> max_value (x,max_in_list(rest))

How does max_list work?
If the list has only one element, the maximum is the element.
If instead it has more than one element — x :: rest — the function returns the maximum between x and the maximum found in rest.

Note how the case of empty list has not been handled.

True if there is a value that is greater than 0

let rec one_greater_thanZero = function 
  | [] -> false
  | [x] -> x > 0
  | x :: rest -> x > 0 || one_greater_thanZero rest

How does one_greater_thanZero work?
If the list is empty, it returns false: there is no value greater than zero.
If the list has a single element, true if that value is greater than zero — false otherwise.
For each element x scanned, check if x>0.
NOTE
The conditions are in logical or, this means that the computation will end as soon as a value x>0 is found — or in the worst case when the whole list has been scanned.

The predicate you want to check can also be passed as a parameter to the function. Let’s see how.

# greater_thanZero : int -> bool
# greater_thanZero x = true if x>0
let greater_thanZero x = x > 0
 
# one_greater_thanZero: ('a->bool)-> ('a list) -> bool
# one_greater_thanZero p x = true if one element has p(x)==true
let rec one_greater_thanZero p = function 
  | [] -> false
  | [x] -> p x
  | x :: rest -> p x || one_greater_thanZero p rest

Filters with only the elements that satisfy a predicate

#filter_only_satify : ('a list -> bool) -> 'a list -> 'a list = <fun>
let rec filter_only_satify p = function 
  | [] -> []
  | [x] -> if p[x] then [x]
           else []
  | x :: rest -> if p[x] then x::filter_only_satify p rest
                 else filter_only_satify p rest

For now that’s all.
In the next blog post we will delve into a Sorting Algorithm — Selection Sort is the way :)

mc
mariocuomo.github.io