namekuseijin <············@gmail.com> writes:
> On 29 out, 04:12, llothar <·······@web.de> wrote:
> > Wow, thats impressive close to the perl line noise. Isn't it?
>
> no. Perl line noise would be a lot more concise. It looks like
> normal, everyday applicative Scheme. Perhaps your were confused by
> all the lambdas? I agree, the author could have dropped the outer
> lambda and used the simpler function definition syntax...
The author has written the code to make the comparision test
for the elements a parameter. That hurts readability. It
also worries me, for don't you have to use the same test for
access as for construction. So shouldn't the test be stored
away at construction time, for future use?
Hmm, I think you are ok if construction-equals is stricter
that access-equals. So you cannot do case-sensitive reads on
a case-insenstive trie, but case-insensitve reads on a
case-sensitive tree, ought to work.
No, that cannot be right, there is no backtracking, if you go
down the lower-case leg and don't find it, it might have
been down the upper-case leg. You need the key matches as
you descent the trie to be unique.
Something fishy here.
Anyway I found the code hard to get into so I tried writing
my own trie-builder in CL
Once I'd done it I realised that my builder is a recursive
builder that is called on the entire data set, while Darius
has written an item-by-item builder.
>
> other than that, it's a complicated algorithm...
>
> tries in CL are not any better.
My recursive version looks a lot better tonight, while it is
still fresh in my head. No doubt I will find it
incomprehensible if I return to it in a month or two :-)
#| How do I represent a trie?
If I have a set ((a b)(a b c)(a d)(e)(f g h))
I am trying to factor out the common prefixs
ie start with a or e or f
The route (a b) leads to either empty or c so
I cannot just have an association list, I need to
flag empty.
In CL an association list can contain NIL, so I should exploit
that
So I want
(defparameter *example1*
'((a (b nil
(c nil))
(d nil))
(e nil)
(f (g (h nil)))))
|#
;;; membership test
;;; is the item (a list of characters) in the trie?
(defun in (list trie)
(or (and (endp list)
(position nil trie))
(let ((subtrie (assoc (first list) trie)))
(and subtrie
(in (rest list)
(cdr subtrie))))))
;;; Build a Trie
;;; The helper, build2, does the heavy lifting
;;; BUILD handles the special case when we have arrived
;;; at the end of a prefix
(defun build (list-of-lists)
(let ((pure-alist (build2 (remove nil list-of-lists))))
(if (member nil list-of-lists)
(cons nil pure-alist)
pure-alist)))
(defun build2 (list-of-cons)
(let ((heads (remove-duplicates (mapcar #'car list-of-cons))))
(loop for head in heads
collect (cons head
(build (loop for cons in list-of-cons
when (eql (car cons) head)
collect (cdr cons)))))))
#| Time marches on, so I'm out of time to test this way of
writing it
(defun build2 (list-of-cons)
(mapcar (extract-from list-of-cons)
(remove-duplicates (mapcar #'car list-of-cons))))
(defcurry extract-from (list-of-cons)(head)
(cons head
(build (loop for cons in list-of-cons
when (eql (car cons) head)
collect (cdr cons))))
|#
(defun list-of-lines (file-spec)
(with-open-file (stream file-spec)
(loop for line = (read-line stream nil nil)
while line
collect line)))
;;; I've stress tested the code on a two hundred and thirty
;;; thousand word dictionary
(defvar *words*
(list-of-lines "/usr/share/dict/web2"))
(defvar *letter-lists*
(mapcar (lambda(string)
(coerce string 'list))
*words*))
(defun random-word (length)
(loop repeat length
collect (code-char (+ (char-code #\a)
(random 26)))))
Alan Crowe
Edinburgh
Scotland