# Lists

```
1 :: 2 :: 3 :: 4 :: []
[1, 2, 3, 4]
cons(1, cons(2, cons(3, cons(4, nil()))))
[1, 2] ++ [3, 4]
```

## Syntax

The list type constructor is `[a]`

where ‘`a`

’ is a type.

The empty list is can be written two ways:
```
[]
nil()
```

The cons operator as well:
```
<Expr :: a> :: <Expr :: [a]>
cons(<Expr :: a>, <Expr :: [a]>)
```

The append operator (`++`

) is usable on lists, as is ‘`length`

’:
```
<Expr :: [a]> ++ <Expr :: [a]>
length(<Expr :: [a]>)
```

Finally, there are three more function that operate on lists:
```
null( <Expr :: [a]> )
head( <Expr :: [a]> )
tail( <Expr :: [a]> )
```

* null* returns true if and only if the list is empty (i.e. nil).

*returns the first element of the list, while*

`head`

*returns the remainder of the list, after the first element.*

`tail`

IfNote:or`head`

are called on an empty list, an uncatchable error is raised.`tail`

In nearly every case, pattern matching should be used instead of these functions.

## The Colon Confusion Concern

Yes, * ::* is both the type operator and the cons operator in Silver. Here’s a helpful guide:

Language | Scope resolution operator | Has type operator | list cons operator | Access operator |
---|---|---|---|---|

Silver | : |
:: |
:: |
. |

Haskell | . |
:: |
: |
n/a |

Ocaml, Scala, F# | . |
: |
:: |
. |

It wasn’t confusing enough that Haskell uses * ::* as the type operator and

*as the cons operator, while ML uses the exact oppose. We hope that our strategy of using one operator for both will sweep the world, though another language will inevitably use only*

`:`

*, just to annoy everyone in classic Bieber-like fashion. The parser is lonely, please give it some syntax errors to play with.*

`:`

Alright, seriously now. It’d be nice if we could eliminate this overlap, but we really wanted to keep the access operator and the scope resolution operator syntactically distinct.

Consider

`Foo.Bar.Baz`

in Java, and that each of those names could be a package, a class, a field, or…. the only option to make sense of it is to go left-right looking up each name in turn.`Foo:Bar.Baz`

is the grammar`Foo`

, a value`Bar`

, and the attribute`Baz`

, no question.

This becomes dramatically more important when you realize that attributes can be scoped, too. Consider

`foo:bar.foo:baz`

.

Unfortunately, no other operator really seems appropriate for any of these cases. Fortunately, there is no ambiguity in Silver, because arbitrary expressions don’t need to be given explicit type annotations. For now.

## map

Applies the function

to each element of the list`f`

, and returns the resulting list.`l`

`function map [b] ::= f::Function(b ::= a) l::[a]`

Example:`map(null, [[],[1],[]])`

will produce the list.`[true, false, true]`

## foldr

Starting with the initial value

, the function`i`

is applied to the current intermediate value and the next element of the list, and the last intermediate value is returned as the result. If the list is empty, the initial value is also the result.`f`

`function foldr b ::= f::Function(b ::= a b) i::b l::[a]`

Example:`foldr(stringConcat, "He", ["llo", ", ", "World!"])`

will produce the string.`"Hello, World!"`

## filter

The function

is applied to each element list`f`

, and the element is included in the final list only if the function returns true. The order of elements is preserved.`lst`

`function filter [a] ::= f::Function(Boolean ::= a) lst::[a]`

``` function isSilverFile Boolean ::= s::String { return endsWith(“.sv”, s); }Example:

silverFiles = filter(isSilverFile, directoryContents);
```
> will assign to * silverFiles* only those files that end in

*.*

`.sv`

## containsBy

Returns true if an only if the element

is in the list`elem`

, as determined by the equality function`lst`

.`eq`

`function containsBy Boolean ::= eq::Function(Boolean ::= a a) elem::a lst::[a]`

Example:`containsBy(stringEq, "ABC", ["A", "B", "C"])`

will return.`false`

## last

Returns the last element of the list. Ensure that the list is not empty, or it will raise an error (as

does on an empty list.)`head`

`function last a ::= lst::[a]`

Example:`last(["A", "B", "C"])`

will return.`"C"`

## drop / dropWhile

Returns the list remaining after

elements have been removed from the beginning. If the list does not have that many elements, the empty list is returned. Or, returns the list remaining after the function`number`

returns false for the first time (including the element it returned false on.) ``` function drop [a] ::= number::Integer lst::[a]`f`

function dropWhile [a] ::= f::Function(Boolean::=a) lst::[a] ```

Example:`drop(2, ["A", "B", "C"])`

will return.`["C"]`

## take / takeWhile

Returns the first

elements of the list. Or the whole list if there aren’t that many elements in the list. Or, returns the list up to the first element that`number`

returns false on (excluding the element that returns false.) ``` function take [a] ::= number::Integer lst::[a]`f`

function takeWhile [a] ::= f::Function(Boolean::=a) lst::[a] ```

Example:`take(2, ["A", "B", "C"])`

will return.`["A","B"]`

## reverse

Returns the reverse of the list.

`function reverse [a] ::= lst::[a]`

Example:`head(reverse(lst)) == last(lst)`

will always return true, or raise an error on an empty list.

## sortBy

Sorts the list according to the comparison function

.`lte`

`function sortBy [a] ::= lte::Function(Boolean ::= a a) lst::[a]`

IfNote:is a <= comparison, the sort will be stable and in ascending order. If it is a >= comparison, the sort will be stable and descending.`lte`

Example:`sortBy(stringLte, ["b","c","a"])`

will return.`["a","b","c"]`