Category: Functional Programming

Computing bound of a List with F#

Following code snippet shows how to compute bound (i.e the min and max elements) of a List using F#.

let rec bound (lst:int list) : (int*int) option =
match lst with
| [] -> None // Empty List
| xhd::xtl ->
match bound xtl with
| None -> Some (xhd,xhd) // List with only 1 element
| Some (x,y) ->
Some ((if x>xhd then xhd else x), (if y<xhd then xhd else y))
view raw bound.fs hosted with ❤ by GitHub

Solution outlined here is quite trivial and use the pattern matching facilities of F#.  In case of an empty list (line 3), it returns None; otherwise, it returns the bound as Some (int*int)  (line 8).

Therefore, the signature of bound is given by-

val bound : lst:int list -> (int * int) option
view raw gistfile1.fs hosted with ❤ by GitHub

Output of bound –

> bound [1;2;3;4];;
val it : (int * int) option = Some (1, 4)
> bound [1];;
val it : (int * int) option = Some (1, 1)
> bound [];;
val it : (int * int) option = None
view raw gistfile1.fs hosted with ❤ by GitHub

Euler Problem 002 with F#

Problem Statement

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solutions

Recursive Solution:

// Recursive solution
let eulerProblem2Answer'' =
let maxF = 4000000
let rec computeSum f1 f2 sum =
match f1 + f2 with
| n -> computeSum f2 n sum
| n when n%2 = 0 -> if (n<maxF) then (computeSum f2 n (sum+n)) else sum
computeSum 0 1 0
view raw euler02.fsx hosted with ❤ by GitHub

Using infinite Fibonacci sequence:

let eulerProblem2Answer =
(0,1)
|> Seq.unfold (fun (f1,f2) -> Some(f2, (f2, f1+f2))) // Fibonacci Sequence
|> Seq.takeWhile(fun x -> x < 4000000) // Taking upto Max Fibbonacci
|> Seq.filter (fun x -> x%2=0) // Filtering only even numbers
|> Seq.sum // computing sum
view raw euler02.fsx hosted with ❤ by GitHub

A bit shorter version can be derived using Seq.SumBy:

let eulerProblem2Answer' =
(0,1)
|> Seq.unfold (fun (f1,f2) -> Some(f2, (f2, f1+f2)))
|> Seq.takeWhile(fun x -> x < 4000000)
|> Seq.sumBy (fun x -> if (x%2)=0 then x else 0) // using SumBy with a projection
view raw euler02.fsx hosted with ❤ by GitHub

Result

> 
val eulerProblem2Answer : int = 4613732
val eulerProblem2Answer' : int = 4613732
val eulerProblem2Answer'' : int = 4613732

Define symbolic operators with F#

This post describes how we can define a custom operator with F#. Defining a new operator in F# is very straightforward. For instance, by using the following code, we can define “!” as an operator to compute factorial of an integer.

let rec (!) n =
match n with
| 1 -> (1)
| n -> n*(n-1)
view raw sym_op.fs hosted with ❤ by GitHub

Running the following command in the interactive F# console computes the factorial for 10.

> !10;; 
val it : int = 3628800 
>

A symbolic operator can use any sequence of the following characters: ! % & * + - . / ? @ ^ |~. Note that, “:” can also be used in the character sequence of symbolic operation if and only if, it is not the first character in the operator.

Following is an example of modulo operator defined using F#:

let rec (|%|) a n =
match a, n with
|_ when a < n -> a
|_ when a>=n -> (|%|) (a-n) n
//Resulting signature: val ( |%| ) : int -> int -> int
view raw modulo.fs hosted with ❤ by GitHub

Following outputs shows how to use it from F# interactive shell.

> 23 |%| 3;;
val it : int = 2
> 3 |%| 3;;
val it : int = 0
>

F# | Length of a List

The code snippets listed below defines a function to compute the length of a give list using F#. Note that these functions are also called polymorphic function, as they work with any type of list (as shown in the output).

// naive implementation
let rec length list =
match list with
| [] -> 0
| _::tail -> 1 + computeLength tail
view raw gistfile1.fs hosted with ❤ by GitHub

A tail recursive implementation is outlined next.

// Tail recursive computation of List's length
let length list =
// Auxiliary function to compute length
// It store intermediate result in acc.
let rec lengthAux acc list =
match list with
| [] -> acc
| _::tail -> lengthAux (acc+1) tail
lengthAux 0 list // invoking lengthAux with acc = 0
view raw gistfile1.fs hosted with ❤ by GitHub

Following is a more succinct implementation using List.Fold.

let length list =
List.fold
(fun acc _ -> acc+1)
0
list
view raw length.fs hosted with ❤ by GitHub

Output:

> length [];;
val it : int = 0
> length [1;2;3;4];;
val it : int = 4
> length ['a';'b'];;
val it : int = 2
Design a site like this with WordPress.com
Get started