How to add up the elements for a structure in Scheme/Lisp

Question

I have an input which is of this form:

(((lady-in-water . 1.25)
  (snake . 1.75)
  (run . 2.25)
  (just-my-luck . 1.5))
 ((lady-in-water . 0.8235294117647058)
  (snake . 0.5882352941176471)
  (just-my-luck . 0.8235294117647058))
 ((lady-in-water . 0.8888888888888888)
  (snake . 1.5555555555555554)
  (just-my-luck . 1.3333333333333333)))

(context: the word denotes a movie and the number denotes the weighted rating submitted by the user)

I need to add all the quantity and return a list which looks something like this

((lady-in-water 2.5)
 (snake 2.5)
 (run   2.25)
 (just-myluck 2.6))

How do I traverse the list and all the quantities? I am really stumped. Please help me.

Thanks.

Answer 1

You need to break the problem into two parts: first, transform the list into something like this:

'(((lady-in-water . 1.25) (lady-in-water . 0.82) (lady-in-water . 0.88))
  ((snake . 1.75) ...)
  ...)

I'll do that using transpose:

(define (transpose ls)
  (if (null? (car ls))
      '()
      (cons (map car ls) (transpose (map cdr ls)))))

Then it's easy to reduce the transposed movie list to a single list of pairs:

 (define (sum-movie movie)
   (cons (caar movie) (apply + (map cdr movie))))
 (define (sum-movies movies)
   (map sum-movie (transpose movies)))

Note that transpose is unsafe: it will crash if you are missing a movie in one sub-list. Also, using transpose in the first place assumes that movies come in the same order each time.

Answer 2

In Common Lisp:

(defun marginalize (data)
  (let ((table (make-hash-table)))
    (loop for row in data do
      (loop for (k . v) in row do
        (incf (gethash k table 0.0) v)))
    (loop for k being the hash-key of table using (hash-value v)
          collect (cons k v))))

Answer 3

My approach is similar to huaiyuan's above, but I prefer using dolist to loop:

(defun parse-ratings (all-ratings)
  (let ((hash (make-hash-table)))
    (dolist (rating-list all-ratings)
      (dolist (rating rating-list)
        (incf (gethash (car rating) hash 0)
              (cdr rating))))
    (maphash (lambda (key value) 
               (format t "total for ~a: ~a~%" key value))
             hash)))

which results in the following output:

CL-USER> (parse-ratings '(((lady-in-water . 1.25) (snake . 1.75) 
                          (run . 2.25) (just-my-luck . 1.5))
                         ((lady-in-water . 0.8235294117647058) 
                          (snake . 0.5882352941176471) 
                          (just-my-luck . 0.8235294117647058))
                         ((lady-in-water . 0.8888888888888888)
                          (snake . 1.5555555555555554) 
                          (just-my-luck . 1.3333333333333333))))
total for LADY-IN-WATER: 2.9624183
total for SNAKE: 3.893791
total for RUN: 2.25
total for JUST-MY-LUCK: 3.6568627
NIL
CL-USER>

Answer 4

To avoid the wrong impression that CL is superior in any way, here is a PLT Scheme solution using the hash table approach. I've added a sort of the results for extra credit.

(define (data->movies data)
  (define t (make-hasheq))
  (for* ([x (in-list data)] [x (in-list x)])
    (hash-set! t (car x) (+ (cdr x) (hash-ref t (car x) 0))))
  (sort (hash-map t cons) > #:key cdr))