;; Hi. I would like to invert an alist of the form ;; ;; ((reference-1
referent-a referent-b...) (reference-2 referent-c ...)...) ;; ;; to
another alist of the form ;; ;; ((referent-a reference-1) (referent-b
reference-1) ;; (referent-c reference-2) ...) ;; ;; I have gotten
something to work but it's so stupefyingly *UGLY* that I ;; just know
someone out there can demonstrate a more better beautiful ;; elegant
means of achieving the same result. ;; ;; [ I'm working in emacs-lisp
with the 'cl' package, so the code below ;; ought to be reasonably close
to Common Lisp...] ;; ;; ;; Mind you, I am teaching myself lisp and THIS
IS *NOT* A HOMEWORK ;; ASSIGNMENT. Please bear this in mind when flaming
me. ;;
(require 'cl)
(defmacro dohash (spec &rest body) "(dohash (KEY VALUE HASH-TABLE
[RESULT]) BODY...): loop over a hash table. 'dohash' is to hash-tables as
'dolist' is to lists. This assumes 'maphash' in package 'cl-extra'."
(let ((mapper (gensym "MAPPER-")) (key (car spec)) (value (nth 1 spec))
(tab (nth 2 spec)) (result (nth 3 spec))) `(block nil (flet ((,mapper
( ,key ,value ) ,@body)) (maphash (function ,mapper) ,tab) ,result))))
(defalias 'puthash 'cl-puthash)
(put 'dohash 'common-lisp-indent-function '((&whole 4 2 1) &body))
(put 'dohash 'lisp-indent-function 1)
(defun invert-alist (alist) "Inverts an alist. Given an alist
((reference referent referent...) (reference referent...) ...) return
another alist ((referent reference... reference...) ...).
This is pretty ugly -- via brute force && ignorance.
There's gotta be a better way."
(let ((reference nil)
(result nil)
(tab (make-hash-table :test 'equal)))
(dolist (elem alist tab)
(setf reference (car elem))
(dolist (referent (cdr elem))
(if (gethash referent tab)
(push reference (gethash referent tab))
(puthash referent (list reference) tab))))
(dohash (key dat tab result)
(setf result (acons key (reverse dat) result)))))
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
From: Christopher N. Vogt
Subject: Re: Inverting alists -- *NOT* a homework assignment!!
Date:
Message-ID: <34B40019.22345759@home.com>
····@lehman.com wrote:
>
> ;; Hi. I would like to invert an alist of the form ;; ;; ((reference-1
> referent-a referent-b...) (reference-2 referent-c ...)...) ;; ;; to
> another alist of the form ;; ;; ((referent-a reference-1) (referent-b
> reference-1) ;; (referent-c reference-2) ...) ;; ;; I have gotten
> something to work but it's so stupefyingly *UGLY* that I ;; just know
> someone out there can demonstrate a more better beautiful ;; elegant
> means of achieving the same result. ;; ;; [ I'm working in emacs-lisp
> with the 'cl' package, so the code below ;; ought to be reasonably close
> to Common Lisp...] ;; ;; ;; Mind you, I am teaching myself lisp and THIS
> IS *NOT* A HOMEWORK ;; ASSIGNMENT. Please bear this in mind when flaming
> me. ;;
>
> (require 'cl)
>
> (defmacro dohash (spec &rest body) "(dohash (KEY VALUE HASH-TABLE
> [RESULT]) BODY...): loop over a hash table. 'dohash' is to hash-tables as
> 'dolist' is to lists. This assumes 'maphash' in package 'cl-extra'."
> (let ((mapper (gensym "MAPPER-")) (key (car spec)) (value (nth 1 spec))
> (tab (nth 2 spec)) (result (nth 3 spec))) `(block nil (flet ((,mapper
> ( ,key ,value ) ,@body)) (maphash (function ,mapper) ,tab) ,result))))
>
> (defalias 'puthash 'cl-puthash)
>
> (put 'dohash 'common-lisp-indent-function '((&whole 4 2 1) &body))
> (put 'dohash 'lisp-indent-function 1)
>
> (defun invert-alist (alist) "Inverts an alist. Given an alist
> ((reference referent referent...) (reference referent...) ...) return
> another alist ((referent reference... reference...) ...).
>
> This is pretty ugly -- via brute force && ignorance.
>
> There's gotta be a better way."
> (let ((reference nil)
> (result nil)
> (tab (make-hash-table :test 'equal)))
> (dolist (elem alist tab)
> (setf reference (car elem))
> (dolist (referent (cdr elem))
> (if (gethash referent tab)
> (push reference (gethash referent tab))
> (puthash referent (list reference) tab))))
> (dohash (key dat tab result)
> (setf result (acons key (reverse dat) result)))))
>
I'd do it something like this:
(defun invert-alist (alist)
(loop for list in test
for reference = (first list)
appending (loop for referent in (cdr list)
collect (list referent reference))))