list ← ##.list vect ⍝ list from vector ⍵.
rslt ← init (acc ##.ltrav) list ⍝ List traversal.
Function [list] takes a vector as right argument and returns a list.
Operator [ltrav] takes a dyadic [acc]umulating function as left operand, with
an initial accumulator value of [init] as left argument. The right argument is
the subject [list].
Background
----------
APL is pre-eminent when it comes to the processing of arrays. Occasionally, how-
ever we encounter a task where the value of the first of a number of items det-
ermines how we are to interpret any remaining ones. In this case, it might be
worth considering representing the items as a list, rather than as a vector. An
example might be in writing a parser for a sequence of expression tokens.
Definition: A List-of-⍺-s is either Null or a Pair (Head Tail), where Head is an
⍺ and Tail is a List-of-⍺-s. More succinctly:
List ⍺ ::= Null | Pair ⍺ (List ⍺)
Pair is sometimes called "Cons", short for "list constructor".
We use a nested 2-vector to implement a list with a special value '∘' for Null.
Note that the choice of '∘' for Null is arbitrary and could just as well be any
specific array value, including a 2-vector!
In general, a list has many of the properties of an APL vector, except that:
Separating the first from any remaining items in a list:
head tail←⍵
is quicker and more elegant than the vector equivalent:
head tail←(⊃⍵)(1↓⍵)
However,
A list has no prototypical item, so "overtake" must be coded explicitly.
There is an overhead of around 40 bytes per item (80 in 64-bit APL), comp-
ared with a simple vector but this overhead is diluted when compared with a
nested vector.
size←{⎕size'⍵'} ⍝ size in bytes.
size 1e3⍴⎕a ⍝ size of 1000-vector of bytes.
1016
size list 1e3⍴⎕a ⍝ size of 1000-list of bytes.
39980
size ,¨1e3⍴⎕a ⍝ size of 1000-vector of 1-vectors.
24016
size list ,¨1e3⍴⎕a ⍝ size of 1000-list of 1-vectors.
44016
To access the ⍺'th item of a list takes ⍺ iterations, as opposed to the
vector's 1. In other words, list-item-access is O(n), whereas vector-item-
access is O(1). However, in both cases, access-each-item is O(n).
To process all of the items in a list, a common operation, there is no equi-
valent of the array's primitive operator ¨ (each). Instead, an explicit loop
must be coded.
(
However, in defence of the list: splitting a problem into what-to-do-
with-the-head together with what-to-do-with-the-tail is a powerful de-
composition technique. Proponents of the list argue that, in situations
where a vector cannot be treated as a whole, recurring on a list as op-
posed to iterating on the vector leads to many fewer "plus-or-minus-one"
errors.
)
The following function counts the number of items in a list.
litems←{ ⍝ No. of list items.
⍺←0 ⍝ initial count is 0.
⍵≡'∘':⍺ ⍝ null list: accumulated count.
head tail←⍵ ⍝ head item and tail.
(⍺+1)∇ tail ⍝ accumulate with tail.
}
and this function converts a list to its equivalent vector:
vect←{ ⍝ Vector from list.
⍺←⍬ ⍝ initial vector is ⍬.
⍵≡'∘':⍺ ⍝ null list: accumulated vector.
head tail←⍵ ⍝ head item and tail.
(⍺,⊂head)∇ tail ⍝ accumulate with tail.
}
leading to operator [ltrav], which abstracts the essence of traversing a list:
ltrav←{ ⍝ List traversal.
⍵≡'∘':⍺ ⍝ null list : accumulator.
head tail←⍵ ⍝ head item and tail.
(⍺ ⍺⍺ head)∇ tail ⍝ accumulated with tail.
}
Note that in this general case, the initial accumulator ⍺ must be supplied ex-
plicitly as the operator can not know its type.
Using such techniques we can show that, in some circumstances, the processing of
a list can outpace the equivalent (naïvely coded) vector version:
vsum←{ ⍝ vector summation.
⍺←0 ⍝ initial accumulator.
0=⍴⍵:⍺ ⍝ null vector: finished.
head tail←(⊃⍵)(1↓⍵) ⍝ first and remaining items.
(⍺+head)∇ tail ⍝ accumulated sum.
}
lsum←{ ⍝ list summation.
⍺←0 ⍝ initial accumulator.
⍵≡'∘':⍺ ⍝ null list: finished.
head tail←⍵ ⍝ first and remaining items.
(⍺+head)∇ tail ⍝ accumulated sum.
}
cmpx'vsum⍳1e4' 'lsum list⍳1e4'
vsum⍳1e4 2.2E¯1 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
lsum list⍳1e4 6.5E¯2 -72% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
The reason why vsum is so much slower is that (1↓⍵), which is executed ⍴⍵ times,
makes a copy of all but the first item of the vector ⍵.
NB: Of course, there are better ways to sum a numeric vector!
Technical note:
The coding for list is simply:
list←{ ⍝ list from vector ⍵.
↑{⍺ ⍵}/⍵,'∘' ⍝ with '∘' as null.
}
As {⍺ ⍵} is an idiom, the list function is relatively fast.
Naming leading items
--------------------
We can name more than one item at the head of the list by using "structure as-
signment"
(head tail) ← ⍵ ⍝ name first item and remainder.
(head (next tail)) ← ⍵ ⍝ name first two items and remainder.
(a (b (c (d (e ... ))))) ← ⍵ ⍝ name first umpteen items and remainder.
A rather contrived example of the use of this technique might be to remove adj-
acent duplicate values from a list:
rmdups←{ ⍝ remove adjacent duplicates.
⍺←'∘' ⍝ null accumulator.
(a(b tail))←⍵ ⍝ a and b are first two items.
b≡'∘':'∘'{⍺ ⍵}⍨ltrav a ⍺ ⍝ b null: list-reversed accumulator.
a≡b:⍺ ∇ b tail ⍝ two items match: drop first one.
a ⍺ ∇ b tail ⍝ accumulate first, continue.
}
vect rmdups list 'Mississippi' ⍝ removal of adjacent duplicates.
Misisipi
Handy functions on lists
------------------------
Here are some list utility functions:
rev←{⍺←'∘' ⋄ ⍵≡'∘':⍺ ⋄ hd r←⍵ ⋄ hd ⍺ ∇ tl} ⍝ reversed list: (⌽⍵),⍺
cat←{⍺≡'∘':⍵ ⋄ hd tl←⍺ ⋄ hd(tl ∇ ⍵)} ⍝ list catenation: ⍺,⍵
pop←{⍺=0:⊂⍵ ⋄ hd tl←⍵ ⋄ ((⍺-1)∇ tl),⊂hd} ⍝ ⍺ items and tail from list ⍵
Examples:
ltrav←{ ⍝ List traversal.
⍵≡'∘':⍺ ⍝ null list : accumulator.
head tail←⍵ ⍝ head item and tail.
(⍺ ⍺⍺ head)∇ tail ⍝ accumulated with tail.
}
0 {⍺+1} ltrav list'hello' ⍝ length of list.
5
length←0∘( {⍺+1} ltrav ) ⍝ named list-length function.
length list ⎕a
26
vect←⍬∘( {⍺,⊂⍵} ltrav ) ⍝ vector from list.
vect list 'hello' ⍝ round-trip vector.
hello
revl←'∘'∘( {⍺ ⍵}⍨ ltrav ) ⍝ reverse of list.
vect revl list 'hello' ⍝ vector reverse.
olleh
⍝ A more substantial example is this little "lambda expression" parser:
parse←{ ⍝ Right-to-left lambda expr parser.
↑{ ⍝ ⎕←⍺'│'⍵ ⍝ (uncomment to see trace).
(toks a)(b(c accs))←⍺ ⍵ ⍝ a│b c : a│b c 3-item window.
'⊣'≡a:b ⍝ ⊣│* : * finished
'()'≡a c:toks ∇ b accs ⍝ (│* ) : │* ·
'(→'≡a b:⍺ ∇ c accs ⍝ (│→ * : (│*· ·
'→→'≡a b:toks ∇ ⍵ ⍝ →│→ * : │→ *
'→'≡b:toks ∇ b(('→'a c)accs) ⍝ v│→ b : │→ v→b lambda node.
'→)'≡a c:toks ∇ a ⍵ ⍝ →│* ) : │→ * )
a∊'→(':⍺ ∇('@'b c)accs ⍝ (│f a : (│fa apply node.
toks ∇ a ⍵ ⍝ *│* · : │* *
}/↑{⍺ ⍵}⍨/⌽'⊣(',⍵,')' ⍝ parse of token list ⍵.
}
⍝ Notice that, apart from the last line, there are very few APL primitive funct-
⍝ ions in the code; most of the action takes place using structure construction
⍝ and deconstruction by assembling and naming parts of the ⍺ and ⍵ lists.
)copy min trees ⍝ borrow Min's expression tree display.
··· saved ···
trees parse '(t→ttt)(fx→f(fx))+0' ⍝ parse tree for lambda expression.
┌─@┐
┌──@┐ 0
┌────@─┐ +
┌→──┐ ┌→─┐
t ┌─@┐ f ┌→─┐
┌@┐ t x ┌@─┐
t t f ┌@┐
f x
See also: alists parse lisp joy
Back to: contents
Back to: Workspaces