depth 'nth

[newdep]

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]

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]

'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]

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



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



Eddie

[eddier]

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



Eddie

[newdep]

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]

you could walk through the tree recursevely:

Code Select Expand


(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]

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]

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]

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]

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]

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

Code Select Expand


(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 Expand


(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 Expand


(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 Expand


(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]

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]

>>>

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 Expand


(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 Expand


(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]

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.

http://www.bmc.edu/~eddier/trie.png">



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]