Lists in F#

Dea Saddler
May 13, 2012
28.5k
0
0
Article

Introduction to Lists

A list is an ordered collection of related values and is equivalent to a Linked List data structure used in many other Languages. F# lists are a simple collection type that is built into F#. F# provides the module Microsoft.Fsharp.Collections.List for common operations on Lists. This module is imported automatically by F#, so the List module is already accessible from every F# application.

F# lists are used in functional programming. Lists play an important role in Functional Programming. In functional programming (F#) lists are actually a linked list of the singly linked list variety. Lists can only contain members of the same type; you have the ability to create a list of an object type. Lists are a built-in data structure that is basically a concatenation of the Head and Tail. The head is the First element and the Tail is the remainder of the List.

An F# list can be an Empty List, a List with a value concatenated to it. A value can be concatenated to the front of a F# list using a built-in operator that consists of two colons (::), pronounced "cons". The following table showing a List being defined starting with an empty List on the First Row.

List related Language Constructs and Operators

Expressions/Operator	Description	Example
[]	Showing an Empty List	[]
expr ::expr	" cons" an element with a List	2 :: [3;4]
[expr;...;expr]	A List value	[3 ; 4 ; 5]
[expr .. expr]	A range of Integers	[1 .. 99]
[for Y in List -> expr]	A generated List	[for Y in 1 .. 99 -> Y * Y]
expr @ expr	Concatenates two Lists	[3 ; 4] @ 2

Empty List

The very simplest List you can create or use is an Empty List, represented by empty square brackets.

let emptyList = []
    // the empty list, head = tail = []
    // By Default, the empty list is of type 'T
    // If it contains an element, the list is of a fixed type

" cons"

If you want to add an Element to the head or start of a list, you use the right associative cons operator(::). The List in which you want to add an element to can be empty or non empty.

//example "cons"
let list0 = []
let list1 = "colors" :: []
let list2 = "red" :: list1
let list3 = "blue" :: list2
let list4 = "black" :: "olive" :: "pink" :: []

Fixed value List

If you want to create a List that contains elements, then individual elements can be enumerated by a separate semicolon like below.

let names = ["angle"; "jhon"; "denni"]
// list with 3 string elements (head = angle, tail = denni)

concatenated List

A new List can be built by two existing Lists by using @ operator to concatenate them together. You can concatenate like below.

let evenNumbers=[2;4;6;8;10] //separate List 1
let otherNumbers=[11;13] // Separate List 2
let numbers=3::(evenNumbers @ otherNumbers);; //concatenated List From 1 and 2

Ranges

Ranges can be defined in a list as in the following form:

[start_element..step..end_element]

Where start_element is the first element in the List step (it is optioanl) and it is a "Count By" parameter and the end element is the last value. Both Start and End elements will always display in the List that F# constructs, because both are inclusive elements.

// Ranges In List
let digits = [2..20]
let alphabet = ['D'..'S']
let mul3 = [4..4..132]
let evens = [0..2..28]

Generators

Another form of List comprehension used extensively in functional programming is Generators. Generators can be defined in the following form.

[for <identifier> in collection -> expr] or
[for <identifier> in collection do ... yield expr]

Both forms are used in Generators. The first form uses a lambda expression to generate the List elements like below.

let squares = [for i in 1..10 -> i * i] // squares of 1 to 10

Second form for Generators.

let evenumsqr = [for i in 1..10 do if i % 2 = 0 then yield i * i] //squares of even numbers

Syntax for List creation-

let emptyList=[]

let oneElement= "ram" :: []

let twoElement= "ram" :: "shyam" :: []

Some List Examples

let evenNumbers=[2;4;6;8;10]

let otherNumbers=[11;13]

let numbers=3::(evenNumbers @ otherNumbers);;

Results

val evenNumbers : int list = [2; 4; 6; 8; 10]

val otherNumbers : int list = [11; 13]

val numbers : int list = [3; 2; 4; 6; 8; 10; 11; 13]

Lists Type Example

It's important to note that lists are immutable; the "cons" :: and "append" @ operations do not modify the original lists; instead they create new Lists. You can see this in the following example.

Examples-

let names=["eddie";"jenni";"jolly"];;

Result

val names : string list = ["eddie"; "jenni"; "jolly"]

Example

"kathelyn" :: names;;

Result

val it : string list = ["kathelyn"; "eddie"; "jenni"; "jolly"]

Example

names;;

Result

val it : string list = ["eddie"; "jenni"; "jolly"]

List with

The things which make F# list different from .NET Array and Generic List in the System.collections.Generic namespace.

Features	Generic List	Arrays	F# List
Add new Element	Yes	No	No
Element Lookup	O(1) fast	O(1) fast	O(n) slow
Modify Elements	Yes	Yes	No

List module Functions

There are a number of built-in functions for manipulating a List.

list.hd- Returns the first element or head of a list.
list.tl- Returns the tail of the first element. The list of items after the first element.
list.length- Returns the length of the List.
list.rev- Reverses a list and makes a copy of the entire list.
list.find- This takes a Boolean function and returns the first element where that function returns true. If it doesn't find an element it will throw an exception.
list.filter- Takes a function and produces a new list with only the items on which the function returns true. This function filters out the list as you request.

A complete Example for List-

Showing all types of List.

List Types
// the empty list
let emptyList = []
// list of one item
let newItem = "red " :: []
// list of two items
let oldItem = "black " :: "blue " :: []
// list of two items
let shortHand = ["orange "; "pairs "]
// concatenation of two lists
let twoLists = ["one, "; "two, "] @ ["buckle "; "my "; "shoe "
// list of objects
let objList = [box 1; box 2.0; box "three"]
// print the lists
let main() =
    printfn "%A" emptyList
    printfn "%A" newItem
    printfn "%A" oldItem
    printfn "%A" shortHand
    printfn "%A" twoLists
    printfn "%A" objList
// call the main function
main()