Re: need help with data structure problem

B. Pym wrote:

B. Pym wrote:
 

hi, I need to write a function  (join_similar expr) where expr is
adata structure with the following format ( (x1 y1) (x2 y2) (x3 y3)...
(xn yn)),
 
join_similar  will return an expression like ( (x1 y1 y2) (x3 y3) ...)
when x1=x2
 
for instance:
*(join_similar '((3 4) (7 5) (3 6) (7 8) (3 9) (0 1))
 
would return:
((3 4 6 9) (7 5 8) (0 1))

 
 
Kenny Tilton wrote:
 

Lieven Marchand wrote:

CL-USER 9 > (defun join-similar (list)
              (loop with ht = (make-hash-table)
                    for (first second) in list
                    do
                    (pushnew second (gethash first ht nil))
                    finally (return (loop for first being each hash-key in ht using (hash-value rest) collect (cons first rest)))))
JOIN-SIMILAR

 

Isn't LOOP beautiful? <g,d&r>

 
<g> No...
 
(defun join-similar (pairs &aux result)
  (dolist (pair pairs (nreverse result))
    (nconc (or (assoc (first pair) result)
               (first (push (list (first pair)) result)))
           (list (second pair)))))

 
Gauche Scheme
 
(use gauche.collection)   ;; group-collection
 
(define (meld groups)
  (map (lambda(xs) (cons (caar xs) (map cadr xs))) groups))
 
(define (join-similar pairs)
  (meld (group-collection pairs :key car :test equal?)))
 
(join-similar '((foo 4)(bar 7)(foo 5)(bar 8)(fun 9)))
 
  ===>
((foo 4 5) (bar 7 8) (fun 9))

 
Without "cheating" by using group-collection.
 
(define (join-similar pairs)
  (let1 keys (delete-duplicates (map car pairs))
    (map
      (lambda(key)
        (cons key
          (map last (filter (lambda(xs) (equal? key (car xs))) pairs))))
      keys)))
 

Using Tilton's approach.

(define (foo pairs :optional (alist '()))
  (dolist (p pairs  alist)
    (if-let1 e (assoc (car p) alist)
      (append! e (cdr p))
      (push! alist (list-copy p))) ;; Avoid immutability.
  ))

(foo '((foo 4)(bar 7)(foo 5)(bar 8)(fun 9)))
  ===>
((fun 9) (bar 7 8) (foo 4 5))
 
--
"It suffices that the past is exempt from mutation."
--- Charles Brockden Brown (Wieland)