# Lists¶

Disco defines a type of inductive, singly-linked lists, very similar to lists in Haskell.

## Basic lists¶

All the elements of a list must be the same type, and the type of a
list with elements of type `T`

is written `List(T)`

.

The basic syntax for constructing and pattern-matching on lists is almost exactly the same as in Haskell, with the one difference that the single colon (type of) and double colon (cons) have been switched from Haskell.

```
emptyList : List(Bool)
emptyList = []
nums : List(N)
nums = [1, 3, 4, 6]
nums2 : List(N)
nums2 = 1 :: 3 :: 4 :: 6 :: []
-- nums and nums2 are equal
nested : List(List(Q))
nested = [1, 5/2, -8] :: [[2, 4], [], [1/2]]
sum : List(N) -> N
sum [] = 0
sum (n :: ns) = n + sum ns
```

## List comprehensions¶

Disco has list comprehensions which are also similar to Haskell’s. A
list comprehension is enclosed in square brackets, and consists of an
expression, followed by a vertical bar, followed by zero or more
*qualifiers*, `[ <expr> | <qual>* ]`

.

A *qualifier* is one of:

- A
*binding*qualifier of the form`x in <expr>`

, where`x`

is a variable and`<expr>`

is any expression with a list type.`x`

will take on each of the items of the list in turn. - A
*guard*qualifier, which is an expression with a boolean type. It acts to filter out any bindings which cause the expression to evaluate to`false`

.

For example, `comp1`

below is a (rather contrived) function on two
lists which results in all possible sums of two *even* numbers taken
from the lists which add to at least 50. `pythagTriples`

is a list
of all Pythagoren triples with all three components at
most 100. (There are much more efficient ways to compute Pythagorean
triples, but never mind.)

```
comp1 : List(N) -> List(N) -> List(N)
comp1 xs ys = [ x + y | x in xs, 2 divides x, y in ys, 2 divides y, x + y >= 50 ]
pythagTriples : List (N*N*N)
pythagTriples = [ (a,b,c)
| a in [1 .. 20]
, b in [1 .. 20]
, c in [1 .. 20]
, a^2 + b^2 == c^2
]
```

Note

The biggest difference between list comprehensions in disco and
Haskell is that Haskell allows *pattern* bindings, *e.g.* ```
Just x <-
xs
```

, which keep only elements from the list which match the
pattern. At the moment, disco only allows variables on the
left-hand side of a binding qualifier. There is no reason in
principle disco can’t support binding qualifiers with patterns, it
just isn’t a big priority and hasn’t been implemented yet.

## Polynomial sequences¶

Like Haskell, disco supports ellipsis notation in literal lists to
denote omitted elements, although there are a few notable
differences. One minor syntactic difference is that (just for fun)
disco accepts two *or more* dots as an ellipsis; the number of dots
makes no difference.

```
-- Counting numbers from 1 to 100
counting : List(N)
counting = [1 .. 100]
-- Even numbers from 2 to 100
evens : List(N)
evens = [2, 4 ..... 100]
-- [5, 4, 3, ... -3, -4, -5]
down : List(Z)
down = [5 .. -5]
-- 1 + 3 + 5 + 7 = 16
s : N
s = {? a+b+c+d when [1, 3 .. 100] is (a::b::c::d::_) ?}
-- It doesn't always have to be integers
qs : List(Q)
qs = [2/3, 7/5 .. 10]
```

`[a .. b]`

denotes the list that starts with`a`

and either counts up or down by ones (depending on whether`b`

is greater than or less than`a`

, respectively), continuing as long as the elements do not “exceed”`b`

(the meaning of “exceed” depends on whether the counting is going up or down).`[a, b .. c]`

denotes the list whose first element is`a`

, second element is`b`

, and the difference between each element and the next is the difference`b - a`

. The list continues as long as the elements do not “exceed”`c`

, where “exceed” means either “greater than” or “less than”, depending on whether`b - a`

is positive or negative, respectively.

All the above is similar to Haskell, except that `[10 .. 1]`

is the
empty list in Haskell, and disco’s rules about determining when the
list stops are much less strange (the strangeness of Haskell’s rules
is occasioned by floating-point error, which of course disco does not
have to deal with). Also, since disco is strict, it does not support
infinite lists.

However, disco also generalizes things further by allowing notation of
the form `[a, b, c .. d]`

or `[a, b, c, d .. e]`

, and so on. We
have already seen that `[a, b .. c]`

generates a linear progression
of values; by analogy, `[a, b, c .. d]`

generates a quadratic
progression, `[a, b, c, d .. e]`

a cubic, and so on. In general, when
\(n\) values \(a_0, a_1, \dots, a_n\) are given before the
ellipsis, disco finds the unique polynomial \(p\) of degree
\(n-1\) such that \(p(i) = a_i\), and uses it to generate
additional terms of the list. (In practice, the disco interpreter does
not actually find a polynomial, but uses the *method of finite
differences*, just like Charles Babbage’s Difference Engine.)

```
-- Some triangular numbers
triangular : List(N)
triangular = [1, 3, 6 .. 100]
-- Some squares
squares : List(N)
squares = [1, 4, 9 .. 100]
-- Some cubes
cubes : List(N)
cubes = [1, 8, 27, 64 .. 1000]
```

The list continues until the first one which “exceeds” the ending value. The precise definition of “exceeds” is a bit trickier to state in general, but corresponds to the eventual behavior of the polynomial: the list stops as soon as elements become either larger than or smaller than the ending value, as the polynomial diverges to \(+\infty\) or \(-\infty\), respectively.

## Multinomial coefficients¶

We already saw that the `choose`

operator can be used to compute
binomial coefficients. In fact, if the second operand to `choose`

is a list instead of a natural number, it can be used to compute
general multinomial coefficients as well. `n choose xs`

is the
number of ways to choose a sequence of sets whose sizes are given by
the elements of `xs`

from among a set of `n`

items. If the sum of
`xs`

is equal to `n`

, then this is given by `n!`

divided by the
product of the factorials of `xs`

; if the sum of `xs`

is greater
than `n`

, then `n choose xs`

is zero; if the sum is less than
`n`

, it is as if another element were added to `xs`

to make up the
sum (representing the set of elements which are “not chosen”). In
general, `n choose k = n choose [k,n-k] = n choose [k]`

.