101companies

Headline

A form of list without basic operations for mutation

Description

An immutable list is a data structure for lists (ordered sequences) of elements of a common type. An immutable list can be manipulated in a basic sense like this:

  • Observations
    • Determine whether the list is null (i.e., empty).
    • Retrieve the head of the list, if it exists (i.e., the first element of the list)
    • Retrieve the tail of the list, if it exists (i.e., the rest or all but the head of the list).
  • Construction
    • Construct a nil list (i.e., the empty list).
    • Construct a cons list (i.e., a non-empty list from given head and tail).
Notably, there are no operations like these:
  • Adding an element in ways other than by using cons.
  • Removing an element in ways other than by using tail.
Such operations are not available because of immutability (lack of support of changes, i.e., mutations). Such operations may be still encoded, but only by means of copying elements from a given list to a new list.

Illustration

Immutable lists in Haskell

Here are some lists with an increasing number of elements: 

[]
[1]
[1,2]
[1,2,3]

We showed convenience notation for list construction. Fundamentally, lists are constructed from two constructor functions: nil (square brackets) and cons (colon). Let us construct the same lists with the fundamental constructors: 

[]
1:[]
1:(2:[])
1:(2:(3:[]))

These are the functions to retrieve the head and the tail of a list: 

head :: [a] -> a
tail :: [a] -> [a]

(In reality, these functions have more general types, but let's simplify things here.)

Here are some applications of head and tail: 

> head [1,2]
1
> tail [1,2]
[2]

Here is how we test a list to be empty: 

null :: [a] -> Bool

For instance: 

> null []
True
> null [1,2]
False

Further operations on lists can be expressed in terms of the operations described so far. Let us define an operation snoc for adding an element at the end of a list. (snoc is inverse of cons in that cons adds an element at the start of a list.) Here is the function definition: 

snoc :: [a] -> a -> [a]
snoc [] x = [x]
snoc (x:xs) y = x : snoc xs y

Here is an illustrative function application: 

> snoc [1,2] 3
[1,2,3]

The function definition for snoc is representative for functions on lists in that we leverage pattern matching with two cases: one for the empty list, another one for nonempty lists. Further, we leverage recursion: the function snoc is defined in terms of itself; the first equation is the base case for recursion.

(C) 2012-2024 softlang.org and contributors

There are no revisions for this page.

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.