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).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// naive implementation | |
let rec length list = | |
match list with | |
| [] -> 0 | |
| _::tail -> 1 + computeLength tail |
A tail recursive implementation
is outlined next.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
Following is a more succinct implementation using List.Fold
.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let length list = | |
List.fold | |
(fun acc _ -> acc+1) | |
0 | |
list |
Output:
> length [];; val it : int = 0 > length [1;2;3;4];; val it : int = 4 > length ['a';'b'];; val it : int = 2