Text only | Text with Images

newLISP Fan Club

Forum => newLISP in the real world => Topic started by: newdep on March 10, 2005, 02:28:03 PM

Title: depth 'nth
Post by: newdep on March 10, 2005, 02:28:03 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.
Title:
Post by: newdep on March 10, 2005, 04:35:00 PM
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.
Title:
Post by: Lutz on March 11, 2005, 04:07:38 AM
'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
Title:
Post by: eddier on March 11, 2005, 06:00:01 AM
What about an associative list with a number representing the depth? Say



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



Eddie
Title:
Post by: eddier on March 11, 2005, 06:03:57 AM
Then again maybe you are building a tree? If so, you can use a general purpose tree searching algorithm?



Eddie
Title:
Post by: newdep on March 11, 2005, 02:25:29 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.
Title:
Post by: Lutz on March 11, 2005, 02:49:11 PM
you could walk through the tree recursevely:




Code Select

(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
Title:
Post by: newdep on March 11, 2005, 02:55:43 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.
Title:
Post by: eddier on March 11, 2005, 03:10:30 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
Title:
Post by: newdep on March 11, 2005, 03:21:05 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.
Title:
Post by: eddier on March 14, 2005, 06:20:51 AM
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
Title:
Post by: eddier on March 14, 2005, 02:42:53 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

(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

(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

(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

(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
Title:
Post by: eddier on March 17, 2005, 09:18:00 AM
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
Title:
Post by: Lutz on March 17, 2005, 01:16:02 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

(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

(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
Title:
Post by: eddier on March 17, 2005, 02:21:06 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.

(//%3C/s%3E%3CURL%20url=%22http://www.bmc.edu/~eddier/trie.png%22%3Ehttp://www.bmc.edu/~eddier/trie.png%3C/URL%3E%3Ce%3E)



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]
Title:
Post by: Lutz on March 17, 2005, 04:16:45 PM
This one would work:


Code Select

;; 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
Title:
Post by: eddier on March 18, 2005, 06:21:29 AM
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

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
Title:
Post by: Lutz on March 18, 2005, 07:34:10 AM
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
Title:
Post by: eddier on March 18, 2005, 07:41:44 AM
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
Text only | Text with Images