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


Javascript data structures - the binary tree

Binary trees in JavaScript? Easy with the right storage mapping function. Find out how to code a binary tree right up to a depth first traversal.



Just JavaScript - Object Construction

Object creation is fundamental to all object-oriented languages, but in JavaScript is is left to the programmer to work out how best to do it and often the practice that you encounter isn't the best b [ ... ]


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.