Multiple assoc in Lisp?
Morten Warankov
Does anyone have a neat way to search for multiple hits in a association
list?
Ex.
Having the list a:
(setq a '((2 1 3)(2 2 3)(2 3 4)(1 2 3)))
I now want to extract the entity(ies) which matches (2 1 ?).
A function like (my_assoc '(2 1) a)?
There's not a solution to (while...) or (repeat...) due to the time
consumption in large lists.
One solution is of course to remove the assoc hit and continue until the
second (or third) is hit, but this seems a bit time consuming also, and
most of the speed benefits of assoc is lost.
Any better solutions ?
Mortenw
Morten Warankov
Since I've found one myself, I turn this into an lisp puzzle.
Any takers??
Mortenw
Reini Urban
Morten Warankov <mor...@abacus.no> wrote:
>> Having the list a:
>> (setq a '((2 1 3)(2 2 3)(2 3 4)(1 2 3)))
>> I now want to extract the entity(ies) which matches (2 1 ?).
>>
>> A function like (my_assoc '(2 1) a)?
This is called (match) and is a standard function in every lisp/scheme
system. a sample implementation for a simple match (which works in
AutoLISP too) is in Winston/Horn: Lisp (the source is available
on-line), even on my site somewhere.
I'll hold it back to see what the others have.
Which wildcards do you want to have?
? or * also
the standard match knows also variables (like $0 in perl)
(match (1 2 ?a ?b) '(1 2 3 4))
=>
>a
3
>b
4
there are more free regex packages for lisp available which could be
ported to alisp.
-- Reini Urban
AutoCAD stuff at http://xarch.tu-graz.ac.at/autocad/
Reini Urban
<rur...@sbox.tu-graz.ac.at> (Reini Urban) wrote:
>This is called (match) ...
BTW: last week somebody posted a combinatoric package to comp.lang.lisp
which would retrieve hits of permutated lists too i.e.
But I haven't ported it to alisp yet. this is not that easy as the
winston/horn matcher. xlisp has a cute mactch.lsp too.
Morten Warankov
Hi Reini,
You're one step ahead of me :). You see, my intention was to create a
new puzzle to extend this into a general assoc function (like your
match), where you can supply any 'legal' list into another list to
retrieve any elements matching the submitted list.
Ex.
Having ((1 2 3 4 5)(2 3 4 5 6)(3 4 5 6 7)(1 2 5 7 7))
by issuing (1 2 nil nil nil) (or as you're suggesting, (1 2 * * *)), the
multiple assoc should return any element matching the issued list, in
this case ((1 2 3 4 5)(1 2 5 7 7)).
But since it's a standard function in Lisp, transferable to Autolisp,
you might as well just post the standard code.
However, I got some solutions for a 'double assoc', and in addition with
my own, I post them in cca in a day or two, so there's some time if
there's still someone that are trying to break the puzzle.
Mortenw
PS.
BTW, after having written this I see why the function is called match :)
Reini Urban
On Wed, 09 Apr 1997 18:46:48 GMT, Reini Urban wrote:
>This is called (match) and is a standard function in every lisp/scheme
>system. a sample implementation for a simple match (which works in
>AutoLISP too) is in Winston/Horn: Lisp (the source is available
>on-line), even on my site somewhere.
One version is at:
http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/lang/lisp/code/match/matcher/0.html
Examples of use include:
(match-p '((:star :wild) b :wild d) '(a b c d)) ==> t
(match-p '(b (:star :wild) d (:star :wild)) '(a b c d)) ==> nil
(match-p '(:wild b :wild d) '(a b c d)) ==> t
;;; Pattern elements:
;;; :wild Matches any single element.
;;; (:star :wild) Matches any number of elements, including
zero.
;;; (:and <pattern>*) Each of the specified patterns must match.
;;; :every Synonym for :and.
;;; (:or <pattern>*) At least one of the patterns must match.
;;; :some Synonym for :or.
;;; (:not <pattern>) The specified pattern must not match.
;;; (:notevery <pattern>*) True if not every pattern matches. Equivalent
;;; to (:not (:and <pattern>*)).
;;; (:notany <pattern>*) True if no pattern matches. Equivalent to
;;; (:not (:or <pattern>*)).
;;; (:typep <type>) True if the expression is of type <type>.
;;; (:test <test> <pattern>) Changes the test for the specified pattern
;;; to <test>. Allows local changes in the test
;;; specified in match-p. For example,
;;; (:test #'eq <pattern>).
;;; (:key <key> <pattern>) Changes the key for the specified pattern to
;;; <key>. Allows local changes in the key
;;; specified in match-p. For example,
;;; (:key #'symbol-name <pattern>).
;;; (:star <pattern>) Allows the specified pattern to match
;;; any number of times, including zero.
;;; (:plus <pattern>) May match any number of times, but must
;;; match at least once.
;;; (:optional <pattern>) May optionally skip over the pattern.
;;; <pattern-variable> Substitutes the value of the pattern
;;; variable in the pattern and matches it
;;; against the expression.
;;;
;;; One may define pattern variables using define-pattern-variable.
;;; For example, (define-pattern-variable :wild-inferiors (:star :wild))
;;; defines :wild-inferiors as a synonym for (:star :wild):
;;; (match-p '(:wild-inferiors b :wild d) '(a b c d)) ==> t
----
The Winston/Horn matcher is i.e. at
http://xarch.tu-graz.ac.at/autocad/lisp/FAQ-link/Winston/24matchi.lsp
=> (match) and (unify)
This implementation would be harder to convert to alisp, esp.
if you haven't got the book. I've got no time now unfortunately
but i will definitely implement a full matcher sooner or later
in alisp or vill (lpp)
Samples:
(print (match '(color (? x) red)
'(color apple red)))
=> ((X APPLE))
(print (match '(((? p) is-a person) with (hair (? h)))
'((patrick is-a person) with (hair blond))))
=> ((H BLOND) (P PATRICK))
(print (unify '(color (? x) (? y))
'(color apple red)))
=> ((Y RED) (X APPLE))
----
According your sample:
(1 2 * * *)) is a wrong pattern. it should say (1 2 *)
and would match to every list which begins with (1 2)
You meant (1 2 ? ? ?) or as in the first style
(1 2 :wild :wild :wild)
(match (1 2 ? ? ?) '(1 2 3 4 5))
-> (1 2 3 4 5)
(match (1 2 *) '(1 2 3 4 5))
-> (1 2 3 4 5)
(match (1 2 *) '((1 2 3)(1 2 3 4 5)))
-> (1 2 3 4 5)
the good thing with match the automatic binding to pattern variables:
(match (1 2 (? a) (? b) (? c)) '(1 2 3 4 5))
-> (1 2 3 4 5) and a, b and c are set to the matched values.
for your "multiple assoc" the appropriate pattern would look like
("every list starting with (1 2) and length 5")
we want:
(match (1 2 ? ? ?) '(1 2 3 4 5))
=> (1 2 3 4 5)
instead of
=> (? (3 4 5))
;as the standard match would return it.
;and for recursive patterns and lists:
(setq l '((1 2 3 4 5)(2 3 4 5 6)(3 4 5 6 7)(1 2 5 7 7)))
(match '((1 2 ? ? ?)) l)
=> ((1 2 3 4 5)(1 2 5 7 7))
in xlisp this works: (winston/horn match.lsp)
(mapcar '(lambda (lst) (match '(1 2 ? ? ?) lst)) l)
=> (((? (3 4 5))) FAIL FAIL ((? (5 7 7))))
>-- Reini Urban
>AutoCAD stuff at http://xarch.tu-graz.ac.at/autocad/
- Reini
AutoCAD stuff: http://xarch.tu-graz.ac.at/autocad/
Christoph Candido
Morten Warankov <mor...@abacus.no> wrote:
>> Does anyone have a neat way to search for multiple hits in a association
>> list?
>> Ex.
>> (setq a '((2 1 3)(2 2 3)(2 3 4)(1 2 3)))
>> I now want to extract the entity(ies) which matches (2 1 ?).
>>
>> A function like (my_assoc '(2 1) a)?
Here is a solution, not very tricky, unfortunately slow, but it works.
My routine MATCH looks for every occurrence of (2 1) in the
association list, e.g. (match '(2 3) a) => '((2 2 3)(2 3 4)).
;; match.lsp
;; 10.04.97 Christoph Candido
;; University of Agricultural Sciences, Vienna, Austria
;; E-Mail: h854...@edv1.boku.ac.at
;;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(defun match (key lst / len)
(setq len (length key))
(apply 'append
(mapcar
'(lambda (l / cont ol i sl)
(setq cont T ol l)
(while cont
(if (>= (length (setq l (member (car key) l))) len)
(progn
(setq i 0 sl '())
(while (< i len)
(setq sl (cons (nth i l) sl)
i (1+ i)
)
)
(if (equal (reverse sl) key)
(setq cont nil)
(setq l (cdr l))
)
)
(setq l nil cont nil)
)
)
(if l (list ol))
)
lst
)
)
)
Regards,
Chris
--
*********************************************
Christoph Candido
E-Mail: h854...@edv1.boku.ac.at
University of Agricultural Sciences
Vienna, Austria
*********************************************
Morten Warankov
I've got some solutions now, so I suppose both Serge Volkov (who was
first), Loh Nam Ngiap and Christoph Candido feel quite confident, having
succeded the puzzle. Keep up the good work guys :)
I post the easiest and quickest here:
----------------------------------------
;; By Morten Warankov
;; Returns first double assoc element
;; Double-assoc
(defun d_assoc (item l)
(cond ((null l) nil)
((equal item (list (caar l)(cadar l))) (car l))
(t (d_assoc item (cdr l)))))
------------------------------------------
;;;
;;; using Vital LISP extensions
;;; By Serge Volkov
(defun vl-mw-assocs (ltag lst)
(vlx-remove-if-not
(function
(lambda (a)
(vlx-every 'equal ltag a) ) )
lst
)
)
--------------------------------------------
I also post Serge's routine using Autolisp, since this routine returns
_all_ elements matching the issued list, as opposed to my own, which
only returns the first element found ( as the normal assoc function.)
-----------------------------------------
;;;By Serge Volkov
;;; pure AutoLISP
;;; returns all assoc elements in a list
(defun equal+ (lbeg lst)
(or (null lbeg)
(and (equal (car lbeg) (car lst))
(equal+ (cdr lbeg) (cdr lst))
)
)
)
(defun mw-assocs (ltag lst)
(apply
'append
(mapcar
'(lambda (a)
(if (equal+ ltag a) (list a)))
lst)
)
)
-------------------------------------------
Mortenw
Morten Warankov
Hi Reini,
and thanks a lot for the hints on where to find these routines. However
I'm still struggling with them :), none works in my Autocad.
Either I'm missing something quite obvious, or you're a better lisp'er
than Autolisper :)
However, I'll keep on learning, and one day I might even manage to write
a general lisp matcher myself. :)
The idea begin to make shape now, and all I wonder is whether I'm
missing something obvious or not. In my head now, a general matcher
should be max 10 lines long, but I might be wrong (Again, there could be
something obvious I've missed :) )
Thanks for the hints,
Mortenw
...still struggling after all these years....
(originally written by Paul Simon, re-written and used without any legal
right. )
Morten Warankov
Hi Reini,
Here is a general match routine which include wildcards as ? or any
string pattern.
As I said, about 10 lines long :)
Regards,
Mortenw
;; Match function which searches through list for matching elements
;; by Morten Warankov 11.04.97
;; (c) ABACUS 1997
;; The function may freely be distributed and used if the header is
;; included and unchanged, with it's copyright notice.
;; usage: (mw_match list1 list2)
;; where list1 is a pattern of elements in list2 to search for matching
elements
;; The function returns all matching elements.
;; The function accepts '?' as wildcard pattern. Further the function
performs a wcmatch
;; and thereby any wildcard accepted by wcmatch (see autolisp manual) if
the wildcard pattern
;; is included in quotes
;; Ex. (mw_match '(1 2 3 ? "5") '((2 3 4 5 6)(3 4 5 6 7)(1 2 3 4 5)(1 2
3 5 5)(1 2 3 5 "5")))
;;returns ((1 2 3 5 "5"))
;; (mw_match '(1 2 3 ? "?") '((2 3 4 5 6)(3 4 5 6 7)(1 2 3 4 5)(1 2 3 5
5)(1 2 3 5 "5")))
;;returns ((1 2 3 5 "5"))
(defun mw_match (item l)
(cond ((null l) nil)
((not (member 'nil (mapcar '(lambda (x y)
(cond ((= '? x) T)
((= 'STR (type x)(type y))
(wcmatch y x))
(t (equal x
y))))
item (car l)))) (append (list(car l))(mw_match
item (cdr l))))
(t (mw_match item (cdr l)))))
Christoph Candido
Morten Warankov <mor...@abacus.no> wrote:
>Hi Reini,
>
>Here is a general match routine which include wildcards as ? or any
>string pattern.
>
>As I said, about 10 lines long :)
This is a good example for what can be done using recursions in real
LISP. But i ever thought, AutoLISP has a little problem with
recursions, because the size of Stack is limited.
Now my question: can you use your routine with big association lists?
I guess, you can't ... am i wrong?
Vladimir Nesterovsky
Sorry for late respond, I've got to read this thread only now.
Like you said, just multiple assoc, not fancy match- functions
(and it's plain ol' AutoLISP):
(defun massoc( group lst )
(apply 'append
(mapcar
'(lambda(el)
(if
(apply 'and
(mapcar 'equal group el))
(list el)))
lst)))
So (massoc '(1 2) '( (1 2 3)(2 1 3) (1 2)))
will return '((1 2 3)(1 2)).
If you want it to respond properly to atom group-codes too,
then make it
(defun massoc( group lst )
(apply 'append (mapcar
(if (atom group)
'(lambda(el)
(if(equal group(car el))(list el)))
'(lambda(el)
(if(apply'and(mapcar'equal group el))(list el))))
lst)))
So that (massoc 1 '( (1 2 3)(2 1 3) (1 2)))
will be valid call and return '((1 2 3)(1 2))
Pretty simple, isn't it ;)
I'm using here an undocumented (?) feature of MAPCAR
that it acts only on number of arguments present in
all argument-lists, so it stops automatically when
shortest list ends - hence no need here to define recursive
solutions for this var-length equality test. MAPCAR
does this automatically. And it consumes *far less*
stack space then it's recursive counterpart. For example,
recursive deep copy of object (like in Winston & Horn,
LISP, pg. 82, problem 5-7) causes AutoLISP stack overflow
for pretty short lists, while mapcar solution never does
for much bigger lists.
I guess, MAPCAR solution must be faster then recursion, too.
Secondly note that (if (atom...)) is before LAMBDAs, so it
maust be evaluated only once here.
Another solution for you problem would be to just change
you data structure to ( ((1 2) 3 4...)((a b) c d ...) ... )
and use standard assoc with (assoc '(1 2) your-data),
although this will return you only one group found.
But you can do this only if you know the key-length
in advance.
Cheers.
------- Original message: -------
On Tue, 08 Apr 1997 14:56:37 +0200, - Morten Warankov <mor...@abacus.no>
wrote in comp.cad.autocad:
>Does anyone have a neat way to search for multiple hits in a association
>list?
>Ex.
>Having the list a:
>(setq a '((2 1 3)(2 2 3)(2 3 4)(1 2 3)))
>I now want to extract the entity(ies) which matches (2 1 ?).
>A function like (my_assoc '(2 1) a)?
>There's not a solution to (while...) or (repeat...) due to the time
>consumption in large lists.
>One solution is of course to remove the assoc hit and continue until the
>second (or third) is hit, but this seems a bit time consuming also, and
>most of the speed benefits of assoc is lost.
>Any better solutions ?
>Mortenw
Live long and prosper --
Vlad
Morten Warankov
Christoph Candido wrote:
>
> Morten Warankov <mor...@abacus.no> wrote:
> >Hi Reini,
> >
> >Here is a general match routine which include wildcards as ? or any
> >string pattern.
> >
> >As I said, about 10 lines long :)
> <snip>
>
> This is a good example for what can be done using recursions in real
> LISP. But i ever thought, AutoLISP has a little problem with
> recursions, because the size of Stack is limited.
> Now my question: can you use your routine with big association lists?
>
> I guess, you can't ... am i wrong?
>
There is a limitation for 'big' lists concerning recursion. For the
supplied routine, I've tested it for a 200x4 elements list on my own
installation with success, but I suppose you will hit the roof for much
larger lists.
Regards,
Mortenw