The initial loop statement must refer to the variable before it is declared.

Question

Sorry for the collapsed name, I tried my best to make it conscious. Well, if you have an idea, change it!

Not to be confused, this is Emacs Lisp loop , not Common Lisp:

 (defun hxswfml-build-trie (alist) "Builds a trie (a list, containing number of hash-maps, each hash-map uses single character for a key, except for `t' symbol, which, if present as a key is the key for the value one has to substitute with." (loop for (key . value) in alist with trie = (make-hash-table) do (loop for c across key with branch = (or (gethash c trie) (puthash c (make-hash-table) trie)) with first-time = t do (if first-time (setq first-time nil) (setq branch (or (gethash c branch) (puthash c (make-hash-table) branch)))) finally (puthash t value branch)) finally (return trie))) 

This converts alist to a tree of hash tables, where each table contains keys, which are the characters of the rows that I later searched and replaced. This is necessary to optimize the search for several keys with, possibly, a similar prefix in most of the text, and then replace each of them with the corresponding key.

The problem is that in the inner loop, I would like to initialize branch to trie , and then in all subsequent iterations set it to a new hash table (created for a character that is not part of the known prefix) or a hash table that has already been created for the character from the prefix.

Ideally, it looks something like this:

 for branch = (or (and branch (gethash c branch)) (puthash c (make-hash-table) trie)) ;; ^-----------------^------- cannot reference it here 

And that is why I have a stupid first-time flag that I could avoid. Can I somehow use the form initially or perhaps rebuild function in any other way to avoid this flag and further if it? It’s not very important that this function is fast (the search should be fast, but you don’t need to build a tree), but it looks just ugly :)

Answer 1

Unverified:

 (defun hxswfml-build-trie (alist) "Builds a trie (a list, containing number of hash-maps, each hash-map uses single character for a key, except for `t' symbol, which, if present as a key is the key for the value one has to substitute with." (loop for (key . value) in alist with trie = (make-hash-table) for leaf = (reduce (lambda (branch c) (or (gethash c branch) (puthash c (make-hash-table) branch))) key :initial-value trie) do (puthash t value leaf) finally (return trie))) 

Answer 2

Since you explicitly mention refactoring as a potential option, I would suggest separating the two operations that your function combines: creating a trie and inserting an element into a trie.

If you consider the definition of attempts as a more modular data structure, you can, for example, start with the following two functions:

 (defun trie-create () (make-hash-table :test 'equal)) (defun trie-put (key value trie) (if (equal key "") (puthash t value trie) (let* ((c (substring key 0 1)) (child-trie (gethash c trie))) (unless child-trie (setq child-trie (trie-create)) (puthash c child-trie trie)) (trie-put (substring key 1) value child-trie)))) 

(As you can see, I suggest recursing here instead of a nested loop - this may be a matter of taste, but it seems to me that this makes the code somewhat simpler and cleaner.)

Then you can add features like trie-get or trie-remove , etc.

Using this code, converting alist to trie becomes a combination of creating a new trie and then inserting all the elements into it using the above functions:

 (let ((trie (trie-create))) (mapc '(lambda (x) (trie-put (car x) (cdr x) trie)) alist)) 

Answer 3

Note that there is already a trie.el package that implements common attempts in Elisp (disclaimer: I am the author of the package). It has been around for several years and is available from GNU ELPA in a recent amount of Emacsen. Or you can download it from the package web page .

It uses AVL trees as the base data structure for default attempts instead of hash tables. But when creating a trie, you can specify a different underlying data structure. All standard search queries (plus a few add-ons) are implemented and agnostic for the underlying data structure.

This does not directly answer your question, but it may save you some work.

Answer 4

I'm not sure I understand, but in Common Lisp I would do:

 (loop for i = (foo) then (1+ i) ...)