Re: data structure equivalent ops

*To*: mathgroup at yoda.ncsa.uiuc.edu*Subject*: Re: data structure equivalent ops*From*: CAMERON at midd.cc.middlebury.edu*Date*: Fri, 22 Feb 91 17:13 EST

David Doll says: > Hello, quick question: I was wondering about how you would do data > structure operations like insert-sorted, delete, find, etc., > double(single) link list, a priority queue, binary tree ops - > insert, delete, traversal, etc., stack ops - pushd, pop, etc. I'm > about to give a quick talk to a few people in my research lab about > the thought of using Mathematica and one of them mentioned it > would helpfull to explain the difference between doing some of the > above mentioned in "C" and in Mathematica. Well, it's not a "quick question" once I've gotten my hands on it! :-) This is a long posting, but it answers the question fairly thoroughly. I was one of the presenters at the 2nd annual Mma Users' Conference in San Francisco last January. One of my presentations was a 90-minute talk called "Introduction to Mma for Users of FORTRAN and C", but I didn't actually rely on any knowledge of those languages, and the title "Introduction to Mma for Users Traditional Procedural Languages" would have been equally apt. The use of pointers in Mma to build up classical data structures like the ones you mention is one of the topics I covered. The example I used in the notes for that talk is insertion sort with a binary tree. Here it is, in revised form. ----- The one-line answer: store pointers in functions. First of all, you must shed (if you've acquired it) the notion that Mma "functions" are "programs". In classical procedural languages there is a sharp distinction between executable entities in a program (functions and procedures and subroutines) and data objects (variables, arrays, pointers). There is no such division in Mma -- programs are data. If you insist on thinking of a statement like f[x_] := x^2 + x only as a "program" that accepts "input" x and computes the "output" x^2 + x then you may miss the insight that you can store data in functions. This statement actually stores a rewriting rule (which is a data object) in the global rule base, namely the rule "f[x_] :> x^2 + 2". You can think of this as specifying the "value" of the "pointer named f" at any "node named x". Similarly, the statements left[a] = b; right[a] = c; can be thought of as specifying that the value of the "left" pointer at "node a" is "b", and the value of the "right" pointer is "c"; they store the rules "left[a] -> b" and "right[a] -> c" in the global rule base. If you have many other rewriting rules on "left" and "right", such as "left[x] -> y" and "right[u] -> v", this amounts to a data structure built out of the nodes "{a,b,c,...,u,v,...,x,y,...}" and the pointers "left" and "right". This could be a binary tree (for example). There is only one difference between this and the usual way of constructing a data structure from pointers in languages like C and Pascal, and it's this: in C you'd declare a "struct" type (in Pascal it'd be a "record") that contained two "fields" named "left" and "right", which were pointers to this same type of "struct". There would be an instance of this "struct" for each node. Thus the information about "left" and "right" subtrees of a node would be physically stored in the data structure that represents the node. In Mma, the information about ALL "left" subtrees is physically stored in memory under the "pointer name" "left", instead of being distributed among the nodes. Similarly the information about all "right" subtrees is stored with the name "right". But who cares whether the value of "right[a]" is stored with "right" or with "a"? For most purposes, it doesn't matter. You can tell whether a pointer is defined or not by whether it rewrites. For example, suppose your "nodes" are Mma lists that store several items of information. Suppose you have a binary tree of these nodes, and the pointers are "left" and "right". Suppose the variable "x" in a procedure represents one of the nodes in the tree, and you want to know whether "x" has a left subtree or not. In C or Pascal, you would ask whether "x.left" is a null pointer. In Mma, you would simply ask whether "left[x]" has head "left"! After all, if "x" has a left subtree, then "left[x]" will evaluate to the node that is the root of that subtree, and (since we are storing nodes as lists) the expression "Head[left[x]]" will be "List". But if "x" has no left subtree, then "left[x]" won't have a rewriting rule associated with it, so it won't rewrite, so "Head[left[x]]" will be "left". This also shows how to clear a pointer: just say "left[x] = ." (or, equivalently, "Unset[left[x]]", which is what that is an abbreviation for). With all that in mind, here's an insertion sort in Mma. In this case we're building a binary tree whose nodes are strings. ClearAll[ root, left, right ] (* these are our "pointers" *) insert[s_String] := insert[root,s] insert[ x_String, y_ ] := Which[ x === y, x, OrderedQ[{x,y}], insert[ right[x], y ], True, insert[ left[x], y ] ] insert[ x_, y_ ] := x = y That's it! The rules, in order, say this: First, initialize the tree (defined by the pointers "root", "left", and "right") to be empty. Next, if you're being asked to insert a string into the tree, that means to start by trying to insert it at the root. Next, if you're being asked to insert a string "y" at or below the node "x", and "x" is a string, then there are three subcases: a) Maybe they are the same string ("x === y"), in which case "y" is already in the tree. In this case just return the node that stores "y" (which happens to be the string itself). (What we choose to return here is actually completely arbitrary, because the insertion is done at this point.) b) If the strings aren't equal, then maybe string "x" is less than string "y" ("OrderedQ[{x,y}]"). We have to use "OrderedQ" to compare the strings because Mma's less-than operator "<" only wants to compare numeric entities. If "x" is less than "y", then "y" should be inserted in the "right" subtree of "x". We recurse. c) If the strings aren't equal, and "x" isn't less than "y", then "x" must be greater than "y", so "y" belongs in the "left" subtree of "x". Now, there are two ways to break out of the recursion in the second rule for "insert". If a string being inserted ("y") is already in the tree, then eventually we will break out in subcase (a) above. But if the string is not in the tree, then eventually we will reach a leaf node in the recursions through cases (b) and (c). What is a leaf node? It's a node that lacks a subtree -- in other words, its "left" and/or "right" pointers are undefined. Say for concreteness that "x" is the string "foo" and "y" is the string "bar", so we are trying to evaluate insert["foo","bar"] and say that left["foo"] is undefined. The second rule on "insert" will rewrite insert["foo","bar"] into insert[left["foo"],"bar"], but since left["foo"] is undefined it won't rewrite. This keeps the second rule on "insert" from firing again, because it is restricted to fire only when its first argument has head "String", and the expression left["foo"] has head "left". So we drop through to the third rule, which says that if you have "insert[x,y]" and "x" is not a string, rewrite it to "x = y". In this case, that becomes left["foo"] = "bar" which does exactly the right thing -- it installs "bar" as the root node of the left subtree of "foo". As a test, try this: insert /@ {"this", "is", "a", "test", "of", "this", "insertion", "sort"} Mma returns the same list (because we return the value of the inserted string in subcase (a) of the second rule and in the third rule, which are the two places where we break out of the recursion on "insert"). But if we look at the "left" and "right" and "root" pointers we see this: In[6]:= ?left left left/: left["this"] = "is" left/: left["is"] = "a" left/: left["test"] = "of" In[6]:= ?right right right/: right["is"] = "test" right/: right["a"] = "insertion" right/: right["of"] = "sort" In[6]:= ?root root root = this (NOTE: a bug in Mma V1.2 causes the string quotes around "this" in the output from "?root" to be omitted. This is fixed in V2.0.) To print out the list in sorted order, we want to traverse this tree in left-center-right order, printing nodes as we come to them. Here's a function that does this: LCR[s_String] := { LCR[left[s]], s, LCR[right[s]] } LCR[_] := {} sortedlist := Flatten[LCR[root]] If a node has a value (i.e., if it is a string) then return that string, preceded by its left subtree and followed by its right subtree. If it has no value (i.e., if it is an expression like left["foo"] that doesn't rewrite, so its head is not "String"), return nothing. To print the list in sorted order, we do this: In[9]:= sortedlist Out[9]= {a, insertion, is, of, sort, test, this} It works! Note that "this" was stored only once. Exercise: modify the above so that the elements of the list returned by "sortedlist" are not just the strings, but lists of the form {String,Integer} where the integer counts the number of occurrences of the string. The output of your modified program on the same input should be In[39]:= sortedlist Out[39]= {{a, 1}, {insertion, 1}, {is, 1}, {of, 1}, {sort, 1}, > {test, 1}, {this, 2}} (Hint: the first thing I thought of was to make the "nodes" be lists. This is the hard way. There's a much simpler, more elegant solution.) A historical comment: I doubt that many people today know much about the programming language SNOBOL4, which is about twenty-five years old now and yet is still in many ways one of the most advanced languages ever developed. But if you do have some knowledge of SNOBOL4, then you have a big advantage in working with Mma, because much of the conceptual framework that you need is the same. Both languages rely heavily on pattern-matching to drive the flow of control, for example. And both languages build up data structures via pointers in the same way: by defining "pointer functions". BTW, this was only an incidental point in the "Intro to Mma..." talk I referred to above. The main idea of the presentation was to assume that my listeners knew what programming was about and had done some procedural programming, and to explain the two new programming paradigms (functional programming, and programming by pattern-matching/term-rewriting) that Mma offers, and how they can lead to programs that are easier to write and maintain and that run more efficiently than procedural programs. The notes from this talk are available in the collection "1991 Mma Conference -- Elementary Tutorial Notes", which you can order from WRI. I feel free to say this because I don't get a penny if you do order the notes; I mention it only as a public service for those who might be interested. I'd be happy to put the full notes from my talk on an FTP server somewhere if I didn't think that would upset WRI (since they are trying to sell them). If you order the collection, you do get all the notes from all the elementary tutorials, and there were many of them and they were very good. Hope this helps. --Cameron Smith Mathematica maven and free-lance consultant cameron at midd.cc.middlebury.edu

**Re: data structure equivalent ops**

**psfix for Mathematica 2.0**

**Re: data structure equivalent ops**

**New Message and Files**