## Concept:

# Immutable list

## 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).

- Determine whether the list is
- 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).

- Construct a

- Adding an element in ways other than by using
*cons*. - Removing an element in ways other than by using
*tail*.

## 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.

### There are no revisions for this page.

## User contributions

## 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.
**