6. Data Structures

Data structures deal with the problem of structuring or organizing data for efficient processing by algorithms.

To a certain extent, data structure ideas are independent of the language or notation used to express data structures. On the other hand, what data structures are expressible in a given programming notation are determined by the features of that programming language.

We are using the J programming language as a notation not only for programming in the laboratory, but as an expository notation in our lectures on computer science topics. We use J to describe data structures.

6.1 J Lists

In J we have noticed that both programs and data are expressed as lists. A list is a structure whose printed representation contains zero or more items. An item is a single indivisible J object such as a number or a character, etc. In addition, any item or list may be boxed and be an item of a list. An item of a list is sometimes called an atom. The terminology atom is used to imply that atoms are the data "building blocks". Boxing a non-atom results in an atom which may be used as a list element.

Examples of Lists:


1 2 3
''
'Hi there!'
1 4 2 , 5 6
1 4 2 ; 5 6

In the above examples, 1 4 2 , 5 6 is a 5 item list; 1 4 2append 5 6, while 1 4 2 ; 5 6 is a 2 item list; (< 1 4 2) append < 5 6. The operation of boxing inputs (if necessary) is called link and is defined as link =: ; .

Next we consider J verbs which access, construct and otherwise manipulate lists.


first ls ==> first item in ls.

Remember, first =: {. .

Examples:


first 'a b c' ==> a
first 1 2 3 4 ==> 1

rest ls ==> a list containing all items of ls but the first item.

Remember, rest =: }. .

Examples:


rest 'ab c' ==> b c
rest 1 4 2 ; 5 6 ==>

+---+
|5 6|
+---+

If tally ls is 0 then ls is empty. Remember tally =: # .

Examples:


tally rest 'a' ==> 0
tally 1 2 3 ==> 3

The test to determine whether a J object, t, is a list is to determine whether or not 1 = tally shape t .

Examples:


tally shape 1 2 3 ==> 1
tally shape i. 2 3 ==> 2

Of course, tally is the number of elements in a list.

Example:


tally 'a b (c d)' ==> 9

k from ls ==> k th element of ls (origin 0).  Remember from =: { .

Example:


2 from 1 4 2 ==> 2

a append ls ==> constructs a list whose first item is a and whose remaining items is the list ls. Here, of course, append =: ,, and we assume a is an atom or boxed.

Examples:


2 append 1 2 3 ==> 2 1 2 3
'a b ' append 'c' ==> a b c

It is a domain error for append to have one input which is character and the other which is numeric.

Example:


   2 append 'a b c'
|domain error
|   2     append'a b c'

The link verb, link =: ; , is designed for this task. link always boxes its left input, but only boxes its right input only if it is not already boxed.

Examples:


   2 3 4 link 'abc' ==>
+-----+---+
|2 3 4|abc|
+-----+---+
   2 3 4 link box 'abc' ==>
+-----+---+
|2 3 4|abc|
+-----+---+

The result of 2 3 4 link box 'abc' is the same as the result of 2 3 4 link box 'abc' because box 'abc' is boxed.

reverse ls ==> constructs a list which contains items of ls in reverse order. Reverse is defined as: reverse =: |..

Example:


reverse 'a b c d' ==> d c b a

Since the list structure is pervasive in J we will use lists to describe other data structures constructs.

6.2 Abstract Data Structures

The description of an abstract data structure involves:

(1) a set of elements

(2) a set of operations (functions) defined on the elements (1)

In most of the examples below, the set of elements we will be working with are just the regular J items, such as numbers of various kinds, characters, functions, etc., which exist on any J system. For a particular data structure, the operations which have been defined provide the functionality of the data structure.

6.3 Stack Data Structure

We wish to describe an abstract data structure called a stack. A stack is a structure which allows data elements to be added (pushed) or removed (popped) in such a manner so that the last item added will be the first item removed. Such structures are sometimes called LIFO (last in first out). When storing items (which have indefinite shelf life) in a warehouse, it is sometimes convenient to stack items out from a wall or up from the floor in such a way so that the last item stacked will be the first item removed.

We define a stack to be a collection of J items together with the following operations.


make_stack ==> constructs a stack
stackp obj ==> 1 if obj is a stack, else 0
empty_stackp stack ==> 1 if stack empty, else 0
push_stack item ; stack ==> put item on stack
pop_stack stack ==> remove last item pushed on stack
top_stack stack ==> return last item pushed on stack
                      without removing that value from stack
size_stack stack ==> return number of items on stack
print_stack stack ==> print items on stack

Following is an implementation of stacks using a J list which contains a special stack type tag as its first element.


stack_tag =: box 'stack'
the_empty_stack =: box stack_tag

The stack construction verb follows.


make_stack =: monad def 'the_empty_stack'

s =: make_stack ''

Notice that make_stack is a verb which returns a constant result. Since its definition does not refer to its input y., the value is always the same, namely, the_empty_stack. Since make_stack is a verb, it must be used with an input even though that input is ignored by make_stack. When we use make_stack we will supply an empty input.

A predicate is a verb which always return a true or false result, i.e., 1 or 0. The values 1 and 0 are sometimes called Boolean values in honor of mathematician George Boole who invented Boolean algebra. We adopt the convention to use the suffix "p" for predicate verbs to remind the reader tha the verb is a predicate. By this convention, the suffix "p" is silent in the pronunciation of names of predicate verbs. The predicates for stacks and empty stacks follow.


stackp =: monad def 'stack_tag match first open y.'

stackp s ==> 1

empty_stackp =: monad def 'the_empty_stack match y.'

empty_stackp s ==> 1

Here is what a stack looks like when printed, but we shouldn't rely on the actual representation used for a stack.


s ==>
+-------+
|+-----+|
||stack||
|+-----+|
+-------+

Next we define the push_stack verb.


push_stack =: monad define
('item' ; 'obj') =. y.
if. not stackp box obj
  do. error 'wrong type second input to push_stack' ; obj
  else. box obj append box item
end.
)

s =: push_stack 'a b' ; s
s ==>
+-----------+
|+-----+---+|
||stack|a b||
|+-----+---+|
+-----------+


s =: push_stack 3 ; s 
s ==>
+-------------+
|+-----+---+-+|
||stack|a b|3||
|+-----+---+-+|
+-------------+

Here is the top_stack verb.


top_stack =: monad define
if. not stackp y.
  do. error 'wrong type input to top_stack' ; y.
  else. open last open y.
end.
)

top_stack s ==> 3
s ==>
+-------------+
|+-----+---+-+|
||stack|a b|3||
|+-----+---+-+|
+-------------+

Here is the implementation for the pop_stack verb.


pop_stack =: monad define
if. not stackp y.
  do. error 'wrong type input to pop_stack' ; y.
  else. box drop_last open y.
end.
)

s =: pop_stack s
top_stack s ==> a b

Accessing the top element of a stack does not change the stack.


s ==>
+-----------+
|+-----+---+|
||stack|a b||
|+-----+---+|
+-----------+

Next we define the size_stack verb.


size_stack =: monad define
if. not stackp y.
  do. error 'wrong type input to size_stack' ; y.
  else. _1 + tally open y.
end.
)

size_stack s ==> 1
s =: push_stack 'Hi there' ; s
size_stack s ==> 2
top_stack s ==> Hi there

Finally, we define the print_stack verb.


print_stack =: monad define
if. not stackp y.
    do. error 'wrong type input to print_stack' ; y.
  elseif. 0 = size_stack y.
    do. 'end of stack'
  elseif. 1
    do. display top_stack y.
        print_stack pop_stack y.
end.
)

print_stack s ==>
Hi there
a b
end of stack

size_stack s ==> 2

6.4 Queue Data Structure

Next, we consider a data structure, called a queue. A queue structure is similar to a waiting line. Additions to a queue are made at one end of the waiting line, called the rear, while removals are made at the other end of the queue, called the front.

Queue structures are called FIFO (first in first out) structures and are often used when modeling inventories of perishable or age-dated goods.

A queue is a collection of items together with the following operations.


make_queue ==> constructs a queue
queuep obj ==> 1 if obj is a queue, else 0
empty_queuep queue ==> 1 if queue empty, else 0
enter_queue item ; queue ==> put item in queue
remove_queue queue ==> remove item at front of queue
front_queue queue ==> return item at front of queue
                      without removing that value from queue
size_queue queue ==> return number of items in queue
print_queue queue ==> print items in queue

Following is an implementation of queues using lists which contain a tag identifying a list as a queue.

The queue_tag and the the_empty_queue constants may be defined as:


queue_tag =: box 'queue'
the_empty_queue =: box queue_tag

The make_queue verb.


make_queue =: monad def 'the_empty_queue'

q =: make_queue ''
q ==> 
+-------+
|+-----+|
||queue||
|+-----+|
+-------+

The predicate for a queue may be defined as:


queuep =: monad def 'queue_tag match first open y.'

queuep q ==> 1

The predicate for an empty queue may be defined as:


empty_queuep =: monad def 'the_empty_queue match y.'
empty_queuep q ==> 1

Next we define the enter_queue verb.


enter_queue =: monad define
('item' ; 'queue') =. y.
if. not queuep box queue
  do. error 'wrong type second input to enter_queue' ; queue
  else. box queue_tag append (box item) append rest queue
end.
)

q =: enter_queue 'Hi there' ; q
q ==>
+----------------+
|+-----+--------+|
||queue|Hi there||
|+-----+--------+|
+----------------+

q =: enter_queue (4 % 5) ; q
q ==>
+--------------------+
|+-----+---+--------+|
||queue|0.8|Hi there||
|+-----+---+--------+|
+--------------------+

The front_queue verb may be define as:


front_queue =: monad define
if. not queuep y.
  do. error 'wrong type input to front_queue' ; y.
  else. open last open y.
end.
)

front_queue q ==> Hi there

The remove_queue verb may be defined as:


remove_queue =: monad define
if. not queuep y.
  do. error 'wrong type input to remove_queue' ; y.
  else. box drop_last open y.
end.
)

q =: remove_queue q
q ==>
+-----------+
|+-----+---+|
||queue|0.8||
|+-----+---+|
+-----------+
front_queue q ==> 0.8

Next we define the size_queue verb.


size_queue =: monad define
if. not queuep y.
  do. error 'wrong type input to size_queue' ; y.
  else. _1 + tally open y.
end.
)

size_queue q ==> 1

Finally, we define the print_queue verb.


print_queue =: monad define
if. not queuep y.
    do. error 'wrong type input to print_queue' ; y.
  elseif. 0 = size_queue y.
    do. 'end of queue'
  elseif. 1
    do. display front_queue y.
        print_queue remove_queue y.
end.
)

print_queue q ==>
0.8
end of queue

6.5 Object Programming

Next we give an "object oriented" implementation of stacks and queues. Object oriented programming is currently a very active area of computer science research and development.

Recall that we defined an abstract data structure to consist of:

(1) a set of elements

(2) a set of operations which are defined on the elements in (1)

The main idea of object oriented programming is the packaging together, in what is called an "object", both data structure (nouns) and the operations (verbs) which are defined on that data structure.

The main benefits of object oriented programming are:

* better abstraction of data structures

* objects may be defined so that they inherit some of their behavior from other objects

* better encapsulation of data structures which helps isolate those structures from the programs which use those structures

6.5.1 Preliminary Ideas and Definitions

Objects may be modeled in J using locales. A J locale is a separate namespace (area of memory) where definitions may be located without name conflicts. For example, the name t_abc_ refers to the name t in the locale abc. The t in locale abc is distinct from the name t. All locales including the base (default) locale are children of a special parent locale z. This means that the definition of a name is first sought in the indicated locale. If the definition is not found in that locale, then the definition for the same name in the z locale (if it is defined in the z locale) is used, however, even when the name is found in the z locale, the definition is evaluated in the indicated locale. A few examples will help you understand locales.


t =: 1 2 3

This establishes a binding of the name t (in the base locale) to the list 1 2 3. We could have also written this as t__ =: 1 2 3(t__ is is a reference to t in the base locale and is the same as t).


t_abc_ =: 'Hi there'

Establishes the name t in the abc locale. The binding of t in the abc locale does not interfere with the value bound to t in the base locale.


t ==>
1 2 3

Our file of standard definitions, stddefs.ijs, contains a definition

make_z_ ==>
0!:0@<

which is located in the z locale.

At this point, we do not have all of the background to fully understand all of the verbs used in this definition, however, we can still put this definition to good use. make_z_ is used to read definitions contained in a file and establish them in any locale (If the locale doesn't already exist, it will be created.). This occurs because, even though make exists in the special parent locale z, it may be evaluated in any other locale, causing definitions to be read into that locale. We will use the make verb to read object data structures and object operations into locales whose names are the names of the objects we wish to establish. We call the definitions of such objects which are stored in files object templates.

Next we define an invalid_method_name_indicator constant and the verb for_effect_only.


invalid_method_name_indicator =: 'unknown'

for_effect_only =: monad def '''unspecified'''

Recall that the J evaluation rule requires that the entire expression to the right of a monad be evaluated before the verb may be applied to the resulting noun. for_effect_only is the constant verb which always returns the list of characters 'unspecified'. If the evaluation of the input expression to for_effect_only has a side effect (such as binding a name to some value, that side effect remains after for_effect_only has been evaluated. For example, suppose that a is not bound to any object:


   a ==>
|value error
   for_effect_only a =: 1 2 3 ==>
unspecified
   a ==>
1 2 3

The side effect here is that a is bound, at the top level, to the noun 1 2 3.

6.5.2 A Trivial Object

We are going to use J functions and nouns which are located in special locales to represent objects. An object template will be defined in a file. This file will be used to establish instances of objects of any type by reading the object template into a locale. The following simple example illustrates how simple objects may be constructed in J. Suppose the file simple.object.ijs contains:


NB. A simple object having a data value
NB. and methods to access and set the data value.

data =. 0

simple =. monad define
('method' ; 'value') =. 2 take y.
if. method match 'type'
    do. 'simple object'
  elseif. method match 'get'
    do. data
  elseif. method match 'set'
    do. for_effect_only data =: value
  elseif. 1
    do. root_object method ; value
end.
)

This object template contains a single datum called data together with three operations; type, get and set. We call the object's operations methods. An instance of simple object is established by using the verb make (which is defined in the stddefs locale) to read the simple object template into a locale which becomes the name of the object. In the following example we establish two instances of simple object called s1 and s2.


   make_s1_ 'simple.object.ijs'
   make_s2_ 'simple.object.ijs'
   simple_s1_ <'type' ==>
simple object
   simple_s2_ <'type' ==>
simple object

Notice that even though both object's method definition functions are named simple, they coexist without conflict since they are stored in different locales. Similarily, the object's data structure, both named data, do not conflict. The initial value for the datum is defined to be zero in the object's template file. We can see this value by:


   simple_s1_ <'get' ==>
0
   simple_s2_ <'get' ==>
0

Next we set s1's datum.

   simple_s1_ 'set' ; 1 2 3 4 ==>
unspecified
   simple_s1_ <'get' ==>
1 2 3 4
   simple_s2_ <'get' ==>
0

6.5.3 More Definitions

Notice that the simple object template contains a reference to another object named root_object. This object is used to define any operations not contained in simple object's template. We call an object which contains definitions of operations not in the object's template a parent object. This mechanism is used to allow an object to inherit operations from a parent and avoid the reprogramming of similar operations for different objects. The root_object is defined to have only a type method and is considered the parent of all objects. Here is the root_object template from the file root.object.ijs :


NB. The root object
NB. This object has no data structure and
NB. implements only the type method.

root_object =. monad define
('method' ; 'value') =. 2 take y.
if. method -: 'type'
  do. 'root object'
  else. 'In root object: ',method,': Invalid method name.'
end.
)

We put the root_object in the z locale since all objects will defer operations they do not implement to the root_object.

   make_z_ 'root.object.ijs'
   simple_s1_ <'run' ==>
In root object: run: Invalid method name.

Notice that when the simple_s1 is asked to perform the run method, s1 delegates that task to its parent object (root object), but the root object does not know how to perform the run method either. Finally, notice that we did not specify a locale for the root_object when we made it because the object template file specifies that the root_object is to always be made in the stddefs locale. This object is automatically read into the stddefs locale when the J system is started from the j.code.301 directory.

6.5.4 Stack Objects

Following is a stack object template which is stored in the file stack.object.ijs.

NB. The stack object template


data =: ''

stack =: monad define
('method' ; 'value') =. 2 take y.
if. method match 'type'
    do. 'stack'
  elseif. method match 'emptyp'
    do. 0 = tally data
  elseif. method match 'push'
    do. for_effect_only data =: (box value) , data
  elseif. method match 'top'
    do. if. 0 = tally data
          do. 'top:  stack is empty'
          else. open first data
        end.
  elseif. method match 'pop'
    do. if. 0 = tally data
          do. 'pop:  stack is empty'
          else. for_effect_only data =: rest data
        end.
  elseif. method match 'size'
    do. tally data
  elseif. method match 'print'
    do. if. 0 = tally data
          do. 'print: stack is empty'
          else. for_effect_only display 'top of stack'
            s =. data
            while. 0 < tally s
              do. for_effect_only display open first s
                  s =. rest s
            end.
        end.
  elseif. 1
    do. root_object method ; value
end.
)

The stack object template defines the stack data structure (named data, starting with an empty initial value) and object methods (operations) of:


type
emptyp
push
top
pop
size
print

and inherits any other operations which the base object can perform. The base object given above does nothing but process error messages, however other operations might be defined.

Conceivably, stack objects could delegate operations to other objects which in turn delegate some operations to still other objects, etc.

The following examples examine the operation of stacks as implemented with the stack object template.


   make_s_ 'stack.object.ijs'
   stack_s_ box 'type' ==>
stack

Note that the input to the s stack object must be boxed.


   stack_s_ box 'emptyp' ==>
1
   stack_s_ box 'print' ==>
print: stack is empty
   stack_s_ 'push' ; 'ab c' ==>
unspecified
   stack_s_ box 'top' ==>
ab c
   stack_s_ box 'print' ==>
top of stack
ab c

   stack_s_ 'push' ; 3 * 4 ==>
unspecified
   stack_s_ box 'print' ==>
top of stack
12
ab c

   stack_s_ box 'top' ==>
12
   stack_s_ box 'pop' ==>
unspecified
   stack_s_ box 'print' ==>
top of stack
ab c

   stack_s_ box 'emptyp' ==>
0

6.5.5 Queue Objects

We can make an object oriented version of queues with the following object template stored in the file queue.object.ijs.

NB. The queue object template


data =: ''

queue =: monad define
('method' ; 'value') =. 2 take y.
if. method match 'type'
    do. 'queue'
  elseif. method match 'emptyp'
    do. 0 = tally data
  elseif. method match 'enter'
    do. for_effect_only data =: data , box value
  elseif. method match 'front'
    do. if. 0 = tally data
          do. 'front:  queue is empty'
          else. open first data
        end.
  elseif. method match 'remove'
    do. if. 0 = tally data
          do. 'remove:  queue is empty'
          else. for_effect_only data =: rest data
        end.
  elseif. method match 'size'
    do. tally data
  elseif. method match 'print'
    do. if. 0 = tally data
          do. 'print: queue is empty'
          else. for_effect_only display 'front of queue'
            s =. data
            while. 0 < tally s
              do. for_effect_only display open first s
                  s =. rest s
            end.
        end.
  elseif. 1
    do. root_object method ; value
end.
)

We examine the behavior of queue objects.


   make_q_ 'queue.object.ijs'
   queue_q_ box 'type' ==>
queue
   queue_q_ box 'emptyp' ==>
1
   queue_q_ box 'print' ==>
print: queue is empty
   queue_q_ 'enter' ; 4 % 5 ==>
unspecified
   queue_q_ box 'print' ==>
front of queue
0.8

   queue_q_ box 'front' ==>
0.8
   queue_q_ 'enter' ; 'Hi there' ==>
unspecified
   queue_q_ box 'print' ==>
front of queue
0.8
Hi there

   queue_q_ box 'remove' ==>
unspecified
   queue_q_ box 'print'
front of queue
Hi there

6.5.6 Object Inheritance

When you closely examine the print methods of the queue and stack objects, you will notice that the programs for printing are identical after display of the message 'front of queue' or 'top of stack'. This means that one could write a printing object which would handle the actual printing operation for both the queue and stack objects.

The following object template files, stack1.object.ijs, queue1.object.ijs and print.object.ijs illustrate this.

6.5.7 stack1.object.ijs


NB. The stack object template which inherits a print method

data =: ''

stack_z_ =: monad define
('method' ; 'value') =. 2 take y.
if. method match 'type'
    do. 'stack'
  elseif. method match 'emptyp'
    do. 0 = tally data
  elseif. method match 'push'
    do. for_effect_only data =: (box value) , data
  elseif. method match 'top'
    do. if. 0 = tally data
          do. 'top:  stack is empty'
          else. open first data
        end.
  elseif. method match 'pop'
    do. if. 0 = tally data
          do. 'pop:  stack is empty'
          else. for_effect_only data =: rest data
        end.
  elseif. method match 'size'
    do. tally data
  elseif. method match 'print'
    do. if. 0 = tally data
          do. 'print: stack is empty'
          else. for_effect_only display 'top of stack'
                print 'print' ; box data
        end.
  elseif. 1
    do. root_object method ; value
end.
)

6.5.8 queue1.object.ijs


NB. The queue object template which inherits the print method

data =: ''

queue_z_ =: monad define
('method' ; 'value') =. 2 take y.
if. method match 'type'
    do. 'queue'
  elseif. method match 'emptyp'
    do. 0 = tally data
  elseif. method match 'enter'
    do. for_effect_only data =: data , box value
  elseif. method match 'front'
    do. if. 0 = tally data
          do. 'front:  queue is empty'
          else. open first data
        end.
  elseif. method match 'remove'
    do. if. 0 = tally data
          do. 'remove:  queue is empty'
          else. for_effect_only data =: rest data
        end.
  elseif. method match 'size'
    do. tally data
  elseif. method match 'print'
    do. if. 0 = tally data
          do. 'print: queue is empty'
          else. for_effect_only display 'front of queue'
                print 'print' ; box data
        end.
  elseif. 1
    do. root_object method ; value
end.
)

6.5.9 print.object.ijs


NB. The stack and queue print object

print =: monad define
('method' ; 'value') =. 2 take y.
if. method match 'type'
    do. 'print'
  elseif. method match 'print'
    do.
    while. 0 < tally value
      do. for_effect_only display open first value
          value =. rest value
    end.
  elseif. 1
    do. base method ; value
end.
)

6.5.10 Exercise

Notice that the print object has no data structure and just two methods; type and print. The print should be put in the z locale so that both the stack and queue objects refer to the print object using the name print. Notice also that the stack and queue objects are designed so that their operations are read into the z locale. This means that only one copy of the methods for stack and queue objects will exist in memory. This copy (residing in the z locale) will be shared by all of the stack and queue objects. Verify that these new stack and queue objects function properly.

6.6 J Lists as a Primitive Data Structure

Next, we consider a method of diagramming J boxed lists which are formed with the link ( ; ) verb. Consider the list:


   'abc' ; 1 2 3 ; 4 ==>
+---+-----+-+
|abc|1 2 3|4|
+---+-----+-+

We define a new verb


head =: open atop first
   head 'abc' ; 1 2 3 ; 4
abc

Recall the verb rest:


   rest 'abc' ; 1 2 3 ; 4 ==>
+-----+-+
|1 2 3|4|
+-----+-+

So, if we link these two parts of the list together, we have the original list.


   (head 'abc' ; 1 2 3 ; 4 ) ; rest 'abc' ; 1 2 3 ; 4 ==>
+---+-----+-+
|abc|1 2 3|4|
+---+-----+-+

If we separate this list into its head and rest components we have:


abc and +-----+-+
        |1 2 3|4|
        +-----+-+

We can use a tree like (upside down) notation and write


+---+-----+-+
|abc|1 2 3|4|
+---+-----+-+
  /     \
abc   +-----+-+
      |1 2 3|4|
      +-----+-+

Doing the same for


+-----+-+
|1 2 3|4|
+-----+-+

and


+-+
|4|
+-+

we have the following diagram:


+---+-----+-+
|abc|1 2 3|4|
+---+-----+-+
  /     \
abc   +-----+-+
      |1 2 3|4|
      +-----+-+
        /     \
     1 2 3    +-+
              |4|
              +-+
              / \
             4

A diagram for any boxed list may be drawn in a similar fashion.

We call such a diagram a binary tree because each location in the tree has at most 2 branches. The data of the tree, that is, abc, 1 2 3, 4, and empty value are referred to as the leaves of the tree. These are leaves because there are no branches eminating from these locations. Another name for a leaf of a tree is terminal-node. The non-terminal nodes of the tree for a given list represent the links or link cells of that list. For example,


'abc' ; 1 2 3 ; 4 <==> 'abc' link 1 2 3 ; 4
1 2 3 ; 4 <==> 1 2 3 link 4

We could use what is often called a "box and pointer" notation for a J list. Each box represents a link cell in memory and the lines are locators or pointers to the memory cells which hold the tree leaves.

Each box is a representation of a link cell in memory. The left part of the box locates the head portion of that link cell while the right part of each box locates the rest portion of that link cell.

6.6.1 A Simple List Application

Suppose we wish to use lists to represent a database of information on people. J scripts may be used to define nouns and other parts of speech in a mannor similar to that of defining verbs. For example, we might have a simple database like the following:


people =: ('howland' ; 'jack' ; 'computer science professor') ; ('clinton' ; 'bill' ; 'president usa') ; ('clinton' ; 'hillary' ; 'president usa') ; ('perot' ; 'ross' ; 'wanted to be president') ; < ('bush' ; 'george' ; 'used to be president')

The definition of people, above, is wrapped over several lines. It cannot be entered as shown above, but is available in the file of definitions for the Data Structures chapter, data.struct.ijs.

The people database is simply a list of lists, each of which is of the form:


name ; info_list

As with all boxed lists, we may see the structure of the contained lists by opening the boxed list. For example,


open people ==>
+-------+-------+--------------------------+
|howland|jack   |computer science professor|
+-------+-------+--------------------------+
|clinton|bill   |president usa             |
+-------+-------+--------------------------+
|clinton|hillary|president usa             |
+-------+-------+--------------------------+
|perot  |ross   |wanted to be president    |
+-------+-------+--------------------------+
|bush   |george |used to be president      |
+-------+-------+--------------------------+

We can write a simple J function which will look up names in such a database and return the corresponding info_list.


lookup =: monad define
('name' ; 'database') =. y.
if. 0 = tally database
  do. ''
  else. if. name match head head database
          do. head database
          else. lookup name ; box rest database
        end.
end.
)

Then


lookup 'perot';box people ==>
+-----+----+----------------------+
|perot|ross|wanted to be president|
+-----+----+----------------------+

In the definition of lookup, the phrase 0 = tally database, tests to see whether or not the database has any elements. We will see this phrase occurring many times in different contexts in future chapters. Because of this it seems appropriate to develop a new verb which is true ( 1 ) if its input is an empty list and false ( 0 ) otherwise. We call this verb nullp. The suffix p reminds us that the definition is a predicate (returns a true or false answer) for null (empty) lists. We can write nullp as:


nullp =: monad def '0 = tally y.'


nullp =: (0 bond =) atop tally

We now can rewrite lookup as:


lookup =: monad define
('name' ; 'database') =. y.
if. nullp database
  do. ''
  else. if. name match head head database
          do. head database
          else. lookup name ; box rest database
        end.
end.
)

If we analyze this lookup function so as to estimate the amount of work done while searching the database, we find that the lookup function searches sequentially through the items in the database. Hence, in the worst case, when the item we are looking for is the last item of an n item database, the lookup process requires n uses of the lookup function. If we measure the work done as the number of times lookup is used, then the work done is of order n. We write this as O(n) which is "read order n" or "big O of n". We will give a precise definition of order in the Chapter Program Execution Time. For now, the intuitive concept of the work done being order n, O(n) is that the work is proportional to n. This means that if a program is order n and it takes 1 hour to complete a problem of size 1000, then it will take 2 hours to complete a problem of size 2000.

Suppose that we could devise a method to store our data at the leaf positions of a tree which is symmetrical (unlike the tree diagrams for lists). If we had 16 items and some kind procedure to tell us which half of the tree (left or right), then the number of uses of lookup would be 4.

It is not hard to see that using a similar method to store 17 through 32 items would require 5 uses of lookup, etc. The work done here for a database of n items is ceiling of log₂ n, where ceiling of j is the smallest integer which is greater than or equal to j. Hence the work done is O(log₂ n) which is much smaller than n for large n. This could result in very fast searches of large databases.

6.7 Arrays

Arrays are the principle datatype of the J notation.

6.7.1 Lists

Lists are actually stored internally as arrays in most J systems. Lists have just one axis, namely, length. For example,


t =: 100 2 99 4 6 23

defines a list (array having 1 axis) of length 6. We may access items in this array using the from verb. For example,


2 0 3 from t ==>
99 100 4

We may append items to a list using the append (, ) verb. For example,


t append 1 2 3 ==>
100 2 99 4 6 23 1 2 3

The verb shape ( $ ) is used to produce a list containing the lengths of each of the axes of an array. For example,


shape t append 1 2 3 ==>
9

The verb tally ( # ) is used to give the number of items in a list. If ls is a list, tally and shape give the same results. The number of axes in an array is determined by the phrase tally shape. For example,


tally shape t ==>
1

6.7.2 Lists, Tables and Other Arrays

Arrays may have any number of axes. The dyad reshape ( $ ) may be used to create arrays of any number of axes by choosing items from another array. For example,


2 3 5 reshape t ==>
100   2  99   4   6
 23 100   2  99   4
  6  23 100   2  99

  4   6  23 100   2
 99   4   6  23 100
  2  99   4   6  23

produces an array having 3 axes of lengths 2 3 5. This array prints as a collection of 2 3 by 5 tables. Suppose,


u =: 2 3 5 reshape t

Then,


shape u ==>
2 3 5
tally shape t ==>
3

u may also be thought of as a list of length 2. Indeed,


tally u ==>
2
1 from u ==>
 4  6 23 100   2
99  4  6  23 100
 2 99  4   6  23