## 11.4. list: Operations on lists.

Operations on lists.

Many of these functions are similar to those in the Haskell prelude, but operate on the elements of a list in parallel.

### 11.4.1. `each`

`def each[A](List[A]) :: A`

Publish every value in a list, simultaneously.

Implementation.

```
def each[A](List[A]) :: A
def each([]) = stop
def each(h:t) = h | each(t)

```

### 11.4.2. `map`

`def map[A,B](lambda (A) :: B, List[A]) :: List[B]`

Apply a function to every element of a list (in parallel), publishing a list of the results.

Implementation.

```
def map[A,B](lambda (A) :: B, List[A]) :: List[B]
def map(f,[]) = []
def map(f,h:t) = f(h):map(f,t)

```

### 11.4.3. `reverse`

`def reverse[A](List[A]) :: List[A]`

Publish the reverse of the given list.

Implementation.

```
def reverse[A](List[A]) :: List[A]
def reverse(l) =
def tailrev(List[A], List[A]) :: List[A]
def tailrev([],x) = x
def tailrev(h:t,x) = tailrev(t,h:x)
tailrev(l,[])

```

### 11.4.4. `filter`

`def filter[A](lambda (A) :: Boolean, List[A]) :: List[A]`

Publish a list containing only those elements which satisfy the predicate. The filter is applied to all list elements in parallel.

Implementation.

```
def filter[A](lambda (A) :: Boolean, List[A]) :: List[A]
def filter(p,[]) = []
def filter(p,x:xs) =
val fxs = filter(p, xs)
if p(x) then x:fxs else fxs

```

### 11.4.5. `head`

`def head[A](List[A]) :: A`

Publish the first element of a list.

Implementation.

```

```

### 11.4.6. `tail`

`def tail[A](List[A]) :: List[A]`

Publish all but the first element of a list.

Implementation.

```
def tail[A](List[A]) :: List[A]
def tail(x:xs) = xs

```

### 11.4.7. `init`

`def init[A](List[A]) :: List[A]`

Publish all but the last element of a list.

Implementation.

```
def init[A](List[A]) :: List[A]
def init([x]) = []
def init(x:xs) = x:init(xs)

```

### 11.4.8. `last`

`def last[A](List[A]) :: A`

Publish the last element of a list.

Implementation.

```
def last[A](List[A]) :: A
def last([x]) = x
def last(x:xs) = last(xs)

```

### 11.4.9. `empty`

`def empty[A](List[A]) :: Boolean`

Is the list empty?

Implementation.

```
def empty[A](List[A]) :: Boolean
def empty([]) = true
def empty(_) = false

```

### 11.4.10. `index`

`def index[A](List[A], Integer) :: A`

Publish the nth element of a list, counting from 0.

Implementation.

```
def index[A](List[A], Integer) :: A
def index(h:t, 0) = h
def index(h:t, n) = index(t, n-1)

```

### 11.4.11. `append`

`def append[A](List[A], List[A]) :: List[A]`

Publish the first list concatenated with the second.

Implementation.

```
def append[A](List[A], List[A]) :: List[A]
def append([],l) = l
def append(h:t,l) = h:append(t,l)

```

### 11.4.12. `foldl`

`def foldl[A,B](lambda (B, A) :: B, B, List[A]) :: B`

Reduce a list using the given left-associative binary operation and initial value. Given the list `[x1, x2, x3, ...]` and initial value `x0`, returns `f(... f(f(f(x0, x1), x2), x3) ...)`

Example using `foldl` to reverse a list:

```-- Publishes: [3, 2, 1]
foldl(flip((:)), [], [1,2,3])```

Implementation.

```
def foldl[A,B](lambda (B, A) :: B, B, List[A]) :: B
def foldl(f,z,[]) = z
def foldl(f,z,x:xs) = foldl(f,f(z,x),xs)

```

### 11.4.13. `foldl1`

`def foldl1[A](lambda (A, A) :: A, List[A]) :: A`

A special case of `foldl` which uses the first element of the list as the initial value. If called on an empty list, halt.

Implementation.

```
def foldl1[A](lambda (A, A) :: A, List[A]) :: A
def foldl1(f,x:xs) = foldl(f,x,xs)

```

### 11.4.14. `foldr`

`def foldr[A,B](lambda (A, B) :: B, B, List[A]) :: B`

Reduce a list using the given right-associative binary operation and initial value. Given the list `[..., x3, x2, x1]` and initial value `x0`, returns `f(... f(x3, f(x2, f(x1, x0))) ...)`

Example summing the numbers in a list:

```-- Publishes: 6
foldr((+), 0, [1,2,3])```

Implementation.

```
def foldr[A,B](lambda (A, B) :: B, B, List[A]) :: B
def foldr(f,z,xs) = foldl(flip(f),z,reverse(xs))

```

### 11.4.15. `foldr1`

`def foldr1[A](lambda (A, A) :: A, List[A]) :: A`

A special case of `foldr` which uses the last element of the list as the initial value. If called on an empty list, halt.

Implementation.

```
def foldr1[A](lambda (A, A) :: A, List[A]) :: A
def foldr1(f,xs) = foldl1(flip(f),reverse(xs))

```

### 11.4.16. `afold`

`def afold[A](lambda (A, A) :: A, List[A]) :: A`

Reduce a non-empty list using the given associative binary operation. This function reduces independent subexpressions in parallel; the calls exhibit a balanced tree structure, so the number of sequential reductions performed is O(log n). For expensive reductions, this is much more efficient than `foldl` or `foldr`.

Implementation.

```
def afold[A](lambda (A, A) :: A, List[A]) :: A
def afold(f, [x]) = x
{- Here's the interesting part -}
def afold(f, xs) =
def afold'(List[A]) :: List[A]
def afold'([]) = []
def afold'([x]) = [x]
def afold'(x:y:xs) = f(x,y):afold'(xs)
afold(f, afold'(xs))

```

### 11.4.17. `cfold`

`def cfold[A](lambda (A, A) :: A, List[A]) :: A`

Reduce a non-empty list using the given associative and commutative binary operation. This function opportunistically reduces independent subexpressions in parallel, so the number of sequential reductions performed is as small as possible. For expensive reductions, this is much more efficient than `foldl` or `foldr`. In cases where the reduction does not always take the same amount of time to complete, it is also more efficient than `afold`.

Implementation.

```
def cfold[A](lambda (A, A) :: A, List[A]) :: A
def cfold(f, []) = stop
def cfold(f, [x]) = x
def cfold(f, [x,y]) = f(x,y)
def cfold(f, L) =
val c = Channel[A]()
def work(Number, List[A]) :: A
def work(i, x:y:rest) =
c.put(f(x,y)) >> stop | work(i+1, rest)
def work(i, [x]) = c.put(x) >> stop | work(i+1, [])
def work(i, []) =
if (i <: 2) then c.get()
else c.get() >x> c.get() >y>
( c.put(f(x,y)) >> stop | work(i-1,[]) )
work(0, L)

```

### 11.4.18. `zipWith`

`def zipWith[A, B, C](lambda (A, B) :: C, List[A], List[B]) :: List[C]`

Combine two lists into a list of elements, each produced by calling the given function with corresponding elements of each list. The length of the shortest list determines the length of the result.

Implementation.

```
def zipWith[A, B, C](lambda (A, B) :: C, List[A], List[B]) :: List[C]
def zipWith(_, [], _) = []
def zipWith(_, _, []) = []
def zipWith(f, x:xs, y:ys) = f(x, y) : zipWith(f, xs, ys)

```

### 11.4.19. `zip`

`def zip[A,B](List[A], List[B]) :: List[(A,B)]`

Combine two lists into a list of pairs. The length of the shortest list determines the length of the result.

Implementation.

```
def zip[A,B](List[A], List[B]) :: List[(A,B)]
def zip(xs, ys) = zipWith(lambda(x :: A, y :: B) = (x, y), xs, ys)

```

### 11.4.20. `unzip`

`def unzip[A,B](List[(A,B)]) :: (List[A], List[B])`

Split a list of pairs into a pair of lists.

Implementation.

```
def unzip[A,B](List[(A,B)]) :: (List[A], List[B])
def unzip([]) = ([],[])
def unzip((x,y):z) = (x:xs,y:ys) <(xs,ys)< unzip(z)

```

### 11.4.21. `concat`

`def concat[A](List[List[A]]) :: List[A]`

Concatenate a list of lists into a single list.

Implementation.

```
def concat[A](List[List[A]]) :: List[A]
def concat([]) = []
def concat(h:t) = append(h,concat(t))

```

### 11.4.22. `length`

`def length[A](List[A]) :: Integer`

Publish the number of elements in a list.

Implementation.

```
def length[A](List[A]) :: Integer
def length([]) = 0
def length(h:t) = 1 + length(t)

```

### 11.4.23. `take`

`def take[A](Integer, List[A]) :: List[A]`

Given a number `n` and a list `l`, publish a list of the first `n` elements of `l`. If `n` exceeds the length of `l`, or `n < 0`, take halts with an error.

Implementation.

```
def take[A](Integer, List[A]) :: List[A]
def take(0, _) = []
def take(n, x:xs) =
if n :> 0 then x:take(n-1, xs)
else Error("Cannot take(" + n + ", _)")

```

### 11.4.24. `drop`

`def drop[A](Integer, List[A]) :: List[A]`

Given a number `n` and a list `l`, publish a list of the elements of `l` after the first `n`. If `n` exceeds the length of `l`, or `n < 0`, drop halts with an error.

Implementation.

```
def drop[A](Integer, List[A]) :: List[A]
def drop(0, xs) = xs
def drop(n, x:xs) =
if n :> 0 then drop(n-1, xs)
else Error("Cannot drop(" + n + ", _)")

```

### 11.4.25. `member`

`def member[A](A, List[A]) :: Boolean`

Publish true if the given item is a member of the given list, and false otherwise.

Implementation.

```
def member[A](A, List[A]) :: Boolean
def member(item, []) = false
def member(item, h:t) =
if item = h then true
else member(item, t)

```

### 11.4.26. `merge`

`def merge[A](List[A], List[A]) :: List[A]`

Merge two sorted lists.

Example:

```-- Publishes: [1, 2, 2, 3, 4, 5]
merge([1,2,3], [2,4,5])```

Implementation.

```
def merge[A](List[A], List[A]) :: List[A]
def merge(xs,ys) = mergeBy((<:), xs, ys)

```

### 11.4.27. `mergeBy`

`def mergeBy[A](lambda (A,A) :: Boolean, List[A], List[A]) :: List[A]`

Merge two lists using the given less-than relation.

Implementation.

```
def mergeBy[A](lambda (A,A) :: Boolean,
List[A], List[A]) :: List[A]
def mergeBy(lt, xs, []) = xs
def mergeBy(lt, [], ys) = ys
def mergeBy(lt, x:xs, y:ys) =
if lt(y,x) then y:mergeBy(lt,x:xs,ys)
else x:mergeBy(lt,xs,y:ys)

```

### 11.4.28. `sort`

`def sort[A](List[A]) :: List[A]`

Sort a list.

Example:

```-- Publishes: [1, 2, 3]
sort([1,3,2])```

Implementation.

```
def sort[A](List[A]) :: List[A]
def sort(xs) = sortBy((<:), xs)

```

### 11.4.29. `sortBy`

`def sortBy[A](lambda (A,A) :: Boolean, List[A]) :: List[A]`

Sort a list using the given less-than relation.

Implementation.

```
def sortBy[A](lambda (A,A) :: Boolean, List[A]) :: List[A]
def sortBy(lt, []) = []
def sortBy(lt, [x]) = [x]
def sortBy(lt, xs) = xs >> (
val half = Floor(length(xs)/2)
val front = take(half, xs)
val back = drop(half, xs)
mergeBy(lt, sortBy(lt, front), sortBy(lt, back)))

```

### 11.4.30. `mergeUnique`

`def mergeUnique[A](List[A], List[A]) :: List[A]`

Merge two sorted lists, discarding duplicates.

Example:

```-- Publishes: [1, 2, 3, 4, 5]
mergeUnique([1,2,3], [2,4,5])```

Implementation.

```
def mergeUnique[A](List[A], List[A]) :: List[A]
def mergeUnique(xs,ys) = mergeUniqueBy((=), (<:), xs, ys)

```

### 11.4.31. `mergeUniqueBy`

`def mergeUniqueBy[A](lambda (A,A) :: Boolean, lambda (A,A) :: Boolean, List[A], List[A]) :: List[A]`

Merge two lists, discarding duplicates, using the given equality and less-than relations.

Implementation.

```
def mergeUniqueBy[A](lambda (A,A) :: Boolean,
lambda (A,A) :: Boolean,
List[A], List[A])
:: List[A]
def mergeUniqueBy(eq, lt, xs, []) = xs
def mergeUniqueBy(eq, lt, [], ys) = ys
def mergeUniqueBy(eq, lt, x:xs, y:ys) =
if eq(y,x) then mergeUniqueBy(eq, lt, xs, y:ys)
else if lt(y,x) then y:mergeUniqueBy(eq,lt,x:xs,ys)
else x:mergeUniqueBy(eq,lt,xs,y:ys)

```

### 11.4.32. `sortUnique`

`def sortUnique[A](List[A]) :: List[A]`

Example:

```-- Publishes: [1, 2, 3]
sortUnique([1,3,2,3])```

Implementation.

```
def sortUnique[A](List[A]) :: List[A]
def sortUnique(xs) = sortUniqueBy((=), (<:), xs)

```

### 11.4.33. `sortUniqueBy`

`def sortUniqueBy[A](lambda (A,A) :: Boolean, lambda (A,A) :: Boolean, List[A]) :: List[A]`

Sort a list, discarding duplicates, using the given equality and less-than relations.

Implementation.

```
def sortUniqueBy[A](lambda (A,A) :: Boolean,
lambda (A,A) :: Boolean,
List[A])
:: List[A]
def sortUniqueBy(eq, lt, []) = []
def sortUniqueBy(eq, lt, [x]) = [x]
def sortUniqueBy(eq, lt, xs) = xs >> (
val half = Floor(length(xs)/2)
val front = take(half, xs)
val back = drop(half, xs)
mergeUniqueBy(eq, lt,
sortUniqueBy(eq, lt, front),
sortUniqueBy(eq, lt, back)))

```

### 11.4.34. `group`

`def group[A,B](List[(A,B)]) :: List[(A,List[B])]`

Given a list of pairs, group together the second elements of consecutive pairs with equal first elements.

Example:

```-- Publishes: [(1, [1, 2]), (2, [3]), (3, [4]), (1, [3])]
group([(1,1), (1,2), (2,3), (3,4), (1,3)])```

Implementation.

```
def group[A,B](List[(A,B)]) :: List[(A,List[B])]
def group(xs) = groupBy((=), xs)

```

### 11.4.35. `groupBy`

`def groupBy[A,B](lambda (A,A) :: Boolean, List[(A,B)]) :: List[(A,List[B])]`

Given a list of pairs, group together the second elements of consecutive pairs with equal first elements, using the given equality relation.

Implementation.

```
def groupBy[A,B](lambda (A,A) :: Boolean,
List[(A,B)])
:: List[(A,List[B])]
def groupBy(eq, []) = []
def groupBy(eq, (k,v):kvs) =
def helper(A, List[B], List[(A,B)]) :: List[(A,List[B])]
def helper(k,vs, []) = [(k,vs)]
def helper(k,vs, (k2,v):kvs) =
if eq(k2,k) then helper(k, v:vs, kvs)
else (k,vs):helper(k2, [v], kvs)
helper(k,[v], kvs)

```

### 11.4.36. `rangeBy`

`def rangeBy(Number, Number, Number) :: List[Number]`

`rangeBy(low, high, skip)` returns a sorted list of numbers `n` which satisfy `n = low + skip*i` (for some integer `i`), `n >= low`, and `n < high`.

Implementation.

```
def rangeBy(Number, Number, Number) :: List[Number]
def rangeBy(low, high, skip) =
if low <: high
then low:rangeBy(low+skip, high, skip)
else []

```

### 11.4.37. `range`

`def range(Number, Number) :: List[Number]`

Generate a list of numbers in the given half-open range.

Implementation.

```
def range(Number, Number) :: List[Number]
def range(low, high) = rangeBy(low, high, 1)

```

### 11.4.38. `any`

`def any[A](lambda (A) :: Boolean, List[A]) :: Boolean`

Publish true if any of the elements of the list match the predicate, and false otherwise. The predicate is applied to all elements of the list in parallel; the result is returned as soon as it is known and any unnecessary execution of the predicate killed.

Implementation.

```
def any[A](lambda (A) :: Boolean, List[A]) :: Boolean
def any(p, []) = false
def any(p, x:xs) =
Let(
val b1 = p(x)
val b2 = any(p, xs)
Ift(b1) >> true | Ift(b2) >> true | (b1 || b2)
)

```

### 11.4.39. `all`

`def all[A](lambda (A) :: Boolean, List[A]) :: Boolean`

Publish true if all of the elements of the list match the predicate, and false otherwise. The predicate is applied to all elements of the list in parallel; the result is returned as soon as it is known and any unnecessary execution of the predicate killed.

Implementation.

```
def all[A](lambda (A) :: Boolean, List[A]) :: Boolean
def all(p, []) = true
def all(p, x:xs) =
Let(
val b1 = p(x)
val b2 = all(p, xs)
Iff(b1) >> false | Iff(b2) >> false | (b1 && b2)
)

```

### 11.4.40. `sum`

`def sum(List[Number]) :: Number`

Publish the sum of all numbers in a list. The sum of an empty list is 0.

Implementation.

```
def sum(List[Number]) :: Number
def sum(xs) = foldl(
(+) :: lambda (Number, Number) :: Number,
0, xs)

```

### 11.4.41. `product`

`def product(List[Number]) :: Number`

Publish the product of all numbers in a list. The product of an empty list is 1.

Implementation.

```
def product(List[Number]) :: Number
def product(xs) = foldl(
(*) :: lambda (Number, Number) :: Number,
1, xs)

```

### 11.4.42. `and`

`def and(List[Boolean]) :: Boolean`

Publish the boolean conjunction of all boolean values in the list. The conjunction of an empty list is `true`.

Implementation.

```
def and(List[Boolean]) :: Boolean
def and([]) = true
def and(false:xs) = false
def and(true:xs) = and(xs)

```

### 11.4.43. `or`

`def or(List[Boolean]) :: Boolean`

Publish the boolean disjunction of all boolean values in the list. The disjunction of an empty list is `false`.

Implementation.

```
def or(List[Boolean]) :: Boolean
def or([]) = false
def or(true:xs) = true
def or(false:xs) = or(xs)

```

### 11.4.44. `minimum`

`def minimum[A](List[A]) :: A`

Publish the minimum element of a non-empty list.

Implementation.

```
def minimum[A](List[A]) :: A
def minimum(xs) =
def minA(x :: A, y :: A) = min(x,y)
foldl1(minA, xs)

```

### 11.4.45. `maximum`

`def maximum[A](List[A]) :: A`

Publish the maximum element of a non-empty list.

Implementation.

```
def maximum[A](List[A]) :: A
def maximum(xs) =
def maxA(x :: A, y :: A) = max(x,y)
foldl1(maxA, xs)

```