depth 'nth

[Lutz]

This one would work:

Code Select Expand


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

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 Expand


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]

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">http://www.newlisp.org/index.cgi?page=News



Lutz

[eddier]

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