Essays/DataStructures

From J Wiki
Jump to navigation Jump to search

J's default data structure is array. However, you might want to use other data structures that are common to other languages.

There are a few frequently used data structures in general purpose programming. We could categorize them roughly into 4 groups; list, associative array, graph, and tree. see also wikipedia

Here you'll see how to implement those data structures in J.

<<TableOfContents>>

General Guideline

You could use J's OOP features to implement data structures. For example, you have a node class, which could contain a multiple of nodes. However, you will lose most of J's abstract power(of predefined verbs) if your data isn't in array-form. That is, you can't apply most of the verbs in J to the data types you defined.

However, you may use J's builtin operators(conjuction, adverb) with your verbs which access/modify your data structures.

List

This is the easiest and the most natural in J.

Sparse Array

Sparse arrays in the dictionary

Stack

   s=: 1 2 3 4 5
   pop=: {. ; }.
   push=: ,~
   ]s=:s push 5
5 1 2 3 4 5
   'e s'=:pop s
   e
5
   s
1 2 3 4 5

You could also define a pair of user-defined verbs which do the job with side-effects.

Queue

Priority Queue

From Rosetta Code

Set

   a=: 1 2 3 6
   b=: 1 3 4 5
   union=: ~.@,
   a union b
1 2 3 6 4 5
   intersect=: e. # [
   a intersect b
1 3
   diff=: -.
   a diff b
2 6

see also Phrases/Sets

Associative Array

AA provides O(1), i.e. constant time, lookup. You can emulate AA in J in several ways.

Using m&i. Special Code

Since J 5.04, you can use m&i. special code for faster access to the element. See help/release/midot.htm

However, with this special code, you can't emulate dynamic AA efficiently. That is, every time the hash table is changed(key added, changed or removed), the table has to be rebuilt from the ground up.

Using Sparse Array

Using names in the current locale

Here's an example of how I might implement a dictionary in J
using symbols:

coclass 'dictionary'
okchar=:~. (,toupper) '0123456789abcdefghijklmnopqrstuz'
ok=: ] [ [: assert [: *./ e.&okchar
intern=: [: ('z' , ok)&.> boxxopen
has=: _1 < nc@intern
set=: 4 :'(intern x)=: y'
get=: ".@>@intern

With this script loaded, I can do stuff like:

  table=: conew 'dictionary'
  has__table 'foo'
0
  'foo' set__table i. 3
0 1 2
  has__table 'foo'
1
  get__table 'foo'
0 1 2

If you need a larger symbol domain, replace 'ok' with
a function which converts symbols to hexadecimal strings.

--Raul Miller from J mailing list

Graph

see Dictionary/20. Directed Graphs

Tree

Tree can be seen as a special case of Graph.

see DevonMcCormick's simple example

Using Nested Boxes


Contributed by : June Kim, ( Just a start; help needed from more experienced J programmers)