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].

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↓⍵)


    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.
            size list   1e3⍴⎕a              ⍝ size of 1000-list of bytes.

            size      ,¨1e3⍴⎕a              ⍝ size of 1000-vector of 1-vectors.
            size list ,¨1e3⍴⎕a              ⍝ size of 1000-list of 1-vectors.

    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 can not 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"

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-

    (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.

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 ⍵


    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.
    length←0∘( {⍺+1} ltrav )        ⍝ named list-length function.

    length list ⎕a
    vect←⍬∘( {⍺,⊂⍵} ltrav )         ⍝ vector from list.

    vect list 'hello'               ⍝ round-trip vector.

    revl←'∘'∘( {⍺ ⍵}⍨ ltrav )       ⍝ reverse of list.

    vect revl list 'hello'          ⍝ vector reverse.

⍝ 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.

    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