4

I have a list of elements. Each element is structured as followed:

('symbol "string" int-score)

An example list:

(list (list 'object1 "wabadu" 0.5)
      (list 'object2 "xezulu" 0.6)
      (list 'object1 "yebasi" 0.5)
      (list 'object1 "tesora" 0.2))

I want to retrieve the maximum values for a specific symbol. When I search with the symbol object2, I should get back:

('object2 "xezulu" 0.6)

If I search with object1, I should get back:

(('object1 "wabadu" 0.5) ('object1 "yebasi" 0.5))

I want to collect all the highest elements of a specific object. What I can do is this: assume that the above list is the list used below and that I'm searching for object1. I can retrieve all elements of a specific object:

(loop for element in list
     when (equal 'object1 (first element))
     collect element)

I can also retrieve one highest element of the list:

(loop for element in list
     when (equal 'object1 (first element))
     maximize (third element))

However, this will only return one element. What I want is all maximum elements. I've tried some combinations with collect and maximize, but my knowledge on the syntax is little. Is there a way to collect all the highest elements in a ‘simple’ function?

1
  • Hmm... The first example for iterate seems to be meant to do what you're trying to do... I tried briefly, though, and failed to get iterate to actually work for me, so... not treating this as an answer, for now. If I figure it out, I'll post one; others are encouraged to beat me to the punch.
    – lindes
    Oct 8, 2013 at 1:27

7 Answers 7

2

A sketch of a LOOP-based version:

(defun mymax (target list &aux result max)
  (loop for (item name value) in list
        when (eql item target)
        do (cond ((or (null result)
                      (> value max))
                  (setf result (list (list item name value))
                        max value))
                 ((= value max)
                  (push (list item name value) result))))
  result)
1

This will create a hash-table with the keys being the symbols and the values being arranged in the way (maximum . (list of strings corresponding to maximum))

(let ((data (list (list 'object1 "wabadu" 0.5)
                  (list 'object2 "xezulu" 0.6)
                  (list 'object1 "yebasi" 0.5)
                  (list 'object1 "tesora" 0.2))))
  (loop
     :with table := (make-hash-table)
     :for (item string num) :in data :do
     (destructuring-bind (&optional max strings)
         (gethash item table)
       (cond
         ((or (null max) (< max num))
          (setf (gethash item table) (list num (list string))))
         ((= max num)
          (setf (cdr strings) (cons string (cdr strings))))))
     :finally (return table)))

;; #<HASH-TABLE {1005C6BE93}>
;; --------------------
;; Count: 2
;; Size: 16
;; Test: EQL
;; Rehash size: 1.5
;; Rehash threshold: 1.0
;; [clear hashtable]
;; Contents: 
;; OBJECT1 = (0.5 ("wabadu" "yebasi")) [remove entry]
;; OBJECT2 = (0.6 ("xezulu")) [remove entry]

I think your life would be later easier with this hash table then with the data structure you currently have.

0

You can do that by looping through the list once for selecting all the sublists with the right first elements and determining the maximum (you can use into to let loop accumulate multiple values), and then a second loop in the finally clause go through the selection and now select only those with the maximum score:

(loop for triple in *l*
      for (key nil score) = triple
      when (eq key 'object1)
        collect triple into selection
        and maximize score into max-score
      finally (return (loop for triple in selection
                            when (eql (third triple) max-score)
                              collect triple)))

Edit: Alternatively, instead of a second loop, the delete function can be used here quite concisely:

(loop for triple in *l*
      for (key name score) = triple
      when (eq key 'object1)
        collect triple into selection
        and maximize score into max-score
      finally (return (delete max-score selection
                              :test #'/=
                              :key #'third)))
1
  • In the end I choose for your solution, I found it a good one. Oct 17, 2013 at 11:46
0

The maximize returns only one element. You can sort all the list by the 3rd component and then gets the front one(s). Like this:

;;; suppose a copy of the data is stored in l

;; get all 'object1 and sort them
(setf l (sort (remove-if-not
                (lambda (x) (equal (first x) 'object1)) l)
              #'> :key #'third))
;; remove the ones with smaller value than the first one
(setf l (remove-if
          (lambda (x) (< (third x) (third (first l)))) l))
0

Abstract your data to create basic building blocks; combine building blocks into your needed functionality:

(defun make-foo (type name score)
   (list type name score))

(defun foo-type (foo) (elt foo 0))
;; ...

(defun make-foos (&rest foos)
  foos)

(defun foos-find-if (foos predicate)
  ;; return all foos satisfying predicate
  )

(defun foos-maximize (foos orderer)
  ;; return the maximum foo (any one)
  )

(defun foos-find-if-maximized (foos)
  (foos-find-if foos 
    (let ((max (foos-maximize foos #'foo-score)))
      (lambda (foo)
        (= (foo-score max) (foo-score foo))))))
0

Here is an approach by first saving symbol-list that only contains the lists with the search object. Then we can easily get the maximum value and remove those lists with a smaller value.

(defun foo (symbol list)
  (let* ((symbol-list (remove-if-not #'(lambda (l) (eq (first l) symbol))
                       list))
         (max (apply #'max (mapcar #'third symbol-list))))
    (remove-if-not #'(lambda (l) (= (third l) max))
     symbol-list)))

We can call it: (foo 'object1 l)

0

As a rule of thumb, if you are really wanting to boil down a list of things into a single result, there should be a nice way to do this with reduce.

And there is:

(defun collect-maxima-by-third (list)
  (reduce
   #'(lambda (max-list next-element)
       (let ((max-value (third (first max-list)))
             (next-value (third next-element)))
         (cond ((< max-value next-value)
                (list next-element))
                ((= max-value next-value)
                 (cons next-element max-list))
                (t max-list)))) ; the greater-than case
   (rest list)
   :initial-value (list (first list))))

It's not perfect, as if you give it an empty list it will give you a list containing an empty list instead of just an empty list, but you can easily add a case for this if you think that will happen often.

This type of technique (maybe not this exact example) is detailed in various texts on functional programming; some Haskell texts do a particularly good job (Learn You a Haskell comes to mind).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.