JavaScript data structures - a Lisp-like list
Written by Mike James   
Tuesday, 03 May 2011
Article Index
JavaScript data structures - a Lisp-like list
Towards a general structure

 

A general structure

How do you create a general structure using this form of linked list?

The answer is you just do it. For example consider a binary tree with a root and two leaves A and B. You can create this in one instruction:

var tree=CONS(CONS("A",null),CONS("B",null));

This creates a structure something like:

[|---->[B|---->[null|
V
[A|---->[null|

How do you access the elements in this structure?

You simply use the CAR and CDR properties. For example, to display the stored "A" you would use:

console.log(tree.CAR.CAR);

and to display the stored B you would use:

console.log(tree.CDR.CAR);

Now you can think of CAR as say "left branch" and CDR as "right branch".

To extend the example to a four-item binary tree is just as easy although the brackets are tricky:

var tree=CONS(CONS(CONS("A",null),CONS("B",null)),
CONS(CONS("C",null),CONS("D",null)));

This builds a tree that is the equivalent of:

      /\
  /\ /\
A B C D

Again you can use the CAR and CDR properties to walk the tree and access elements.

For example to display the A and B items you would use:

console.log(tree.CAR.CAR.CAR);
console.log(tree.CAR.CDR.CAR);

and to display the other half of the tree:

console.log(tree.CDR.CAR.CAR);
console.log(tree.CDR.CDR.CAR);

You should have the idea well enough now to create and use a tree of any size.

In practice you wouldn't do it manually in this way but instead create some functions that allow you to build the tree without quite so many brackets getting in the way.

Tree walk

Of course if you try the display function on the tree it doesn't work because it assumes that a CAR is always going to be a data item to display rather than perhaps another list. That is the function assumes that CAR will always be a data item and CDR another list.

To convert it to work with any sort of list we have to deal with the possibility that CAR and CDR might be a list.

The function starts in the same way:

function displayList(L)
{
if(L===null) return;

If the list isn't null then we need to display its CAR but only if it isn't a list that needs further processing.

So how can you tell if L.CAR is a list?

Simple, if it is a list then it too has a CAR and CDR property.

So we can test using:

if (L.CAR.CAR === undefined) {

and if it is undefined then we can assume that L.CAR is a data item and we display it:

console.log(L.CAR);

If it isn't a data item then it is a list and we need to process it further so the else part of the if statement is:

 }else{
displayList(L.CAR);
}

Finally when the if statement is complete all of the tree that is accessible following the CAR side of the first node has been displayed i.e. the left part of the tree.

All we need to do now is process the right side as before:

 displayList(L.CDR);
}

The complete function is:

function displayList(L)
{
if(L===null) return;
if (L.CAR.CAR === undefined) {
console.log(L.CAR);
}else{
displayList(L.CAR);
}
displayList(L.CDR);
}

If you try it out using:

 

tree=CONS(CONS(CONS("A"ll),CONS("B",null)),
CONS(CONS("C",null),CONS("D",null)));
displayList(tree);

Then you will see A,B,C,D printed as the terminal nodes of the tree are encountered left-to-right.

Notice that now that the display function treats both the CAR and CDR parts of a node as possible list the function can deal with lists of any complexity.

Where next

So where to from here?

You can work your way though the Lisp set of functions if you really want, to implementing each one as you go, but you still won't have a Lisp implementation. Lisp is more than just list handling but not much more. What is amazing is that so much can be achieved using so little. Back in the early days when Lisp was first invented it really didn't amount to much more than CONS, CAR and CDR functions and it captured the minds of its users because it was so simple and yet so powerful.

JavaScript has many of the facilities of Lisp and if you want to you can write Lisp-style functional programs using it, but is is just one aspect of this chameleon of a language.

In most cases it is better to try to understand JavaScript on its own terms and try not to make it look like another language.

Related articles:

 

Banner


Just JavaScript - The Prototype Mechanism

The prototype is about the most mysterious part of JavaScript. Once you have mastered the call context and the constructor, it is the prototype that you have to turn to. How does it work? How do you u [ ... ]



Getting Started With jQuery - Advanced Filters

When you first encounter filters they seem easy enough - just extract the results you want from the results you have. The trouble is that filters are fun and jQuery pushes the idea beyond the obvious. [ ... ]


Other Articles

<ASIN:0137054890>

<ASIN:0596517742>

<ASIN:1590597273>

<ASIN:0596805527>

 

<ASIN:1470525932>

<ASIN:0596517742>

<ASIN:1590597273>



Last Updated ( Tuesday, 15 January 2013 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.