From J Wiki
Jump to: navigation, 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.


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.


This is the easiest and the most natural in J.

Sparse Array



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

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


Priority Queue


   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'
  'foo' set__table i. 3
0 1 2
  has__table 'foo'
  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


see Dictionary/20. Directed Graphs


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)