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>
, wherex
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 witha
and either counts up or down by ones (depending on whetherb
is greater than or less thana
, 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 isa
, second element isb
, and the difference between each element and the next is the differenceb - a
. The list continues as long as the elements do not “exceed”c
, where “exceed” means either “greater than” or “less than”, depending on whetherb - 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]
.