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 =
(fun acc _ -> acc+1)
view raw length.fs hosted with ❤ by GitHub


> length [];;
val it : int = 0
> length [1;2;3;4];;
val it : int = 4
> length ['a';'b'];;
val it : int = 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: