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.

example/list.disco
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.)

example/comprehension.disco
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.

example/basic-ellipsis.disco
-- 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.)

example/general-ellipsis.disco
-- 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].