Posted By

jarnaldich on 04/30/08

Tagged

list

Versions (?)

Last Edited at 04/30/08 02:23pm

Statistics

Viewed 754 times

Favorited by 1 user(s)

Related snippets

Grouping keys of an associative list

/ Published in: Scheme

Given an an associative list ((k1 . v1) (k2 . v2) ... (kn . vn)), with possibly equal values for ki, it returns another alist where all cells have distinct keys and where values originally associated to the same key have been grouped as a list in the new cons cell. Ouch! This is much harder to explain than to code. Just check the commented example in the code.

Highlighted TextExpand

;; it requires srfi-1 (lists), for fold-right.
(define (alist-group-keys alist)
  (let ((create-cons-cell-or-append-to-existing 
         (lambda (current acum) 
           (let* ((key (car current))
                  (value (cdr current))
                  (cell (assoc key acum)))
             (if cell ; Key already seen, append current value to the list
                 (begin
                   (set-cdr! cell (cons value (cdr cell)))
                   acum)
                 ;else
                 (cons (list key value) acum))))))
    (fold-right create-cons-cell-or-append-to-existing '() alist)))

;; Example. Given an alist of authors and books:
;
; (alist-group-keys '(("Roth, Henry" . "Call It Sleep")
;                     ("Roth, Henry" . "Mercy of a Rude Stream")
;                     ("Houllebecq, Michel" . "Extension du domaine de la lutte")
;                     ("Houllebecq, Michel" . "Plateforme")))
;
;; It would return the books grouped by author:
;
;(("Roth, Henry" "Call It Sleep" "Mercy of a Rude Stream")
; ("Houllebecq, Michel" "Extension du domaine de la lutte" "Plateforme"))
;

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.