depth 'nth

newdep · Post by **newdep** » Thu Mar 10, 2005 10:28 pm

Hello Lutz,

Im working on a nested lists problem currently and im stuck!

I just tried ->

> (setq mylist '( (a(b(c(d(e(f(g(h(i(j(k(l(m(n(o(p(q(r(s(t(u(v(w(x(y(z))))))))))))))))))))))))))) )
((a (b (c (d (e (f (g (h (i (j (k (l (m (n (o (p (q (r (s (t (u (v (w (x (y (z)))))))))))))))))))))))))))
> (nth 0 0 0 0 0 0 0 0 mylist)
a
> (nth 0 0 0 0 0 0 0 0 0 mylist)

array, list or string expected in function nth : mylist

>

The manual speaks of 16 indices, so that probably wont fit my problem
at all but also the example above starts complaining already at 9 depths??
(do i do something wrong?)

Actualy my initial problem is that i need to nest lists upto a level of
probably 512 or bigger.. Is that possible?
(so a nested list in a nested list in a nested list ....etc...)

Regards, Norman.

newdep · Post by **newdep** » Fri Mar 11, 2005 12:35 am

I made a mistake here i guess...

Its (nth list list list...list) where I go in depth from 1..512.. and that works..
but the range of 16 is too small ;-( in need to go at least upto 512.. like

(nth 0 200 100 512 100 200 ........Xth... list) where Xth is too small..(16)

How can I fix this?

Regards, Norman.

Lutz · Post by **Lutz** » Fri Mar 11, 2005 12:07 pm

'nth' missed the upgrade from 8 to 16 indices when version 8.0.1 came out, this will be corrected in 8.4.5. 'set-nth' and 'nth-set' work fine with 16.

Perhaps 'push' or 'pop' can solve you problem, both work with an unlimited number of indices. We could go to unlimited on 'nth' etc. when moving the indices to the last poistion in the parameter list, like in 'push' and 'pop', but that would break old code.

But what are you trying to do? perhaps there is an other way to represent your data structure? Or try to work with 'push' and 'pop' or try to nest several 'nth' expressions.

Lutz

eddier · Post by **eddier** » Fri Mar 11, 2005 2:00 pm

What about an associative list with a number representing the depth? Say

((a 0) (b 1) (c 2) ...)

Eddie

eddier · Post by **eddier** » Fri Mar 11, 2005 2:03 pm

Then again maybe you are building a tree? If so, you can use a general purpose tree searching algorithm?

Eddie

newdep · Post by **newdep** » Fri Mar 11, 2005 10:25 pm

Welll yes actualy is someting of a tree..
The data that needs to go into the list has an unknow size and every data-part
itself had an unknown amount of subdata parts..and so on.. And my goal is
to visualize those inside a list in a nested way..

So i was on my way of using ( nth x x x ..) but that turned out to be not very
dynamic because the function itself that needs to create the list has to be
adjusted on the fly in list-size..ie. (nth x x list) goes to (nth x x x list ).....etc..

So then i tried to use (push 'x 'y x x x) which also has some dynamic issue
on it (and is unlimited).. I need to figure out the depth in Lisp-language to create a dynamic function (which is a function that adjusts itself during runtime..ieeks..)

The problem is keeping me up for 5 days now because i try to solve the problem in my head instead of try and error it in newlisp ;-) well im working on it ;-)

Any hint is welcome.. eddie was quiet near with his "tree searching algorithm" but i havnt been able to create one yet that suits my needs ;-)

Regards, Norman.

Lutz · Post by **Lutz** » Fri Mar 11, 2005 10:49 pm

you could walk through the tree recursevely:

Code: Select all

(define (walk-tree tree-list)
    (dolist (elmnt tree-list)
        (if (list? elmnt) 
            (walk-tree elmnt)
            (do-something-to elmnt))))

(walk-tree '(a b (c d (e f) g) h i))

;; would process a,b,c,d,e,f,g,h,i in succession

Lutz

newdep · Post by **newdep** » Fri Mar 11, 2005 10:55 pm

Hi Lutz,

Its not quite what im searching for in my first step but you certainly
handed out a nice function which helps me...

I must be stupid , but i did not think of the fact that my define
could call itself from within itself.. I realy dont know why im using
a loop for that ;-) Thanks !

Its time for a topic on "99 great ways to create a loop" ;-)

Norman.

eddier · Post by **eddier** » Fri Mar 11, 2005 11:10 pm

As a matter of taste I try never to use regular old iteration unless it SCREAMS at me. I like recursion in almost every circumstance. A recursive tree search is not very difficult actually even for n-arry trees. Do you want an inorder, preorder, or postorder and how many elements per node?

Eddie

newdep · Post by **newdep** » Fri Mar 11, 2005 11:21 pm

Well actualy im still struggling with the convertion from data to lists then ill focus on the display of the listdata for output..for now its somehow a strange "block' in my head that is saying to me that it must be possible to fix this problem within a few lines of code..but sofar i did not succeed ;-) If i do ill post
the solution in the forum as a [ 3 $ tip of the month ] (it wont be a quick one)..

Norman.

eddier · Post by **eddier** » Mon Mar 14, 2005 2:20 pm

We will be waiting. I've noticed in the past that when someone solved a problem like the one you are facing, it provided a solution for many other types of problems as well.

Eddie

eddier · Post by **eddier** » Mon Mar 14, 2005 10:42 pm

Maybe your looking for a "trie" instead of a "tree." Which brings up the following topic. I created an example trie as:

Code: Select all

(setq trie '((("h" nil) 
	      (("a" nil)
	       (("s" "has"))
	       (("v" nil) 
		(("e" "have")))))
	     (("t" 0)
	      (("o" "to")))))

where the trie contains the words "has," "have," and "to." The second part of each node has a nil or some data. I chose to put the word in there. A search can be written as

Code: Select all

(define (trie-search T key)
  (cond ((= T '())
	 nil)
	((= key (nth 0 0 0 T))
	 (last (nth 0 0 T)))
	((= (first key) (nth 0 0 0 T))
	 (trie-search (rest (first T)) (rest key)))
	((> (first key) (nth 0 0 0 T))
	 (trie-search (rest T) key))
	(true 
	 nil)))

and returns the data part. For example,

Code: Select all

(trie-search trie "have") => "have"
(trie-search trie "hav") => "nil"

Constructing the tree however is difficult since you can't do something like

Code: Select all

(setq L '((1 0) (2 (3 4) 5)))
(push '(2 3) (first L) 1)
~~~~> L = '((2 3 1 0) (2 (3 4) 5)

Without a reference to where you want to put the new list, this is tough. Tommorrow I'll work on a function that returns the position in the list to insert the new data object and see how that works.

Eddie

eddier · Post by **eddier** » Thu Mar 17, 2005 5:18 pm

I'm going to give up on this for a while. With Ryan out of school and a bunch of other tasks at hand, I'll wait to another time.

Ed

Lutz · Post by **Lutz** » Thu Mar 17, 2005 9:16 pm

>>>
Without a reference to where you want to put the new list, this is tough. ... a function that returns the position in the list to insert the new data object ....
>>>

There is the function 'ref' which returns the index vector of of the first object found in a nested list or tree:

Code: Select all

(set 'L '(a b (c d (e f) (g (h (x (y z)))))))

(ref 'x L) => (2 3 1 1 0)

(ref '(e f) L) => (2 2)

The same ref vector returned can be used to extract and then insert a (updated) term:

Code: Select all

(set 'vec (ref 'x L)) => (2 3 1 1 0)

(pop L vec) => x

(push 'XXX L vec) => XXX

L => (a b (c d (e f) (g (h (XXX (y z))))))

Lutz

eddier · Post by **eddier** » Thu Mar 17, 2005 10:21 pm

Yes, but what if we are looking into a trie that has the words
"the",
"there",
"these",
"to."

Notice the structure of the trie with out any data attached. You would have to have data to actually see that "the" was an entry into the trie.

I'm not sure how I can use ref to find the correct possition? What I need is a function that returns the pointer to the "s" node in "these" and then change the link from nil to a new node with "m" in it.

Eddie[/quote]

Lutz · Post by **Lutz** » Fri Mar 18, 2005 12:16 am

This one would work:

Code: Select all

;; trie for: an, ant, all, allot, alloy, aloe, are, ate, be

(set 'aTrie '(
  (a (n () (t)) (l (l () (o (t) (y))) (o (e))) (r (e)) (t (e))) 
  (b (e))))

(define (search-trie trie word)
  (cond
      ( (and (empty? trie) (not (empty? word))) nil)
      ( (and (empty? trie) (empty? word)) true)
      ( (and (empty? (first trie)) (empty? word)) true)
      ( (and 
          (set 'tail (assoc (first word) trie)) 
          (search-trie (rest tail) (rest word))) true)))

(search-trie aTrie '(a n t)) => true
(search-trie aTrie '(a n t s)) => nil
(search-trie aTrie '(a l l o)) => nil
(search-trie aTrie '(a l l o y)) => true

Lutz

eddier · Post by **eddier** » Fri Mar 18, 2005 2:21 pm

Yep that is a trie.
This is the same structure as the trie I have a search working for above except I have data attached to the entries. Therefore "a" becomes "(a data)." I've got the search working what is hard is the insertion. This would actually be quite easy if there was some way to get a pointer from a position and push a value into that position. I started on a function that returns a list of positions to navigate to the item and it worked for the most part except for a few instances which I'm not ready to go and trackdown. With a list of positions following down to the item, we could push a subtrie with the rest of a data item in at that point (the search I have above returning a pointer where items could be pushed on whould be MUCH easier. This is one of the few instances that I've actually seen that it is easier to construct a trie using C, Pascal, Ada, ... than Lisp. Note that in Python I can do stuff like

Code: Select all

T = [[["a", 1], [["b", 4], ["c", 5]]]]
X = T[0][1]
X.append(['d',7])
print T
=> [[['a', 1], [['b', 4], ['c', 5], ['d', 7]]]]

We've all heard the horror stories of aliasing but in this case, aliasing is very usefull. There is nothing like this in newLISP. So we will have to construct an entire list of indicies to push the element into the trie.

Eddie

Lutz · Post by **Lutz** » Fri Mar 18, 2005 3:34 pm

perhaps inserting the index-path as part of the data and returning it ... nice problem to think about.

Meanwhile ... a new development release 8.4.5 with a better installer, 'sort', 'pack/unpack' and implicit indexing http://www.newlisp.org/index.cgi?page=News

Lutz

eddier · Post by **eddier** » Fri Mar 18, 2005 3:41 pm

Haven't thought about putting the index path into the trie, maybe as part of the data. Thanks for the sort. I find myself using the sort function quite often and being able to sort by a comparison function will simplify many other scripts.

Thanks!

Eddie