K Isn't Lisp (2004)

That K solution is O(n^2) complexity, vs O(n*log(n)) for Lisp.

I kinda hate it how all the K advocacy always uses old-style languages with small stdlibs, _and_ always ignores the complexity.. How about matlab (which does have "unique" in stdlib), python/numpy or even R?

The exact semantics of the problem aren't clear (do we need to maintain order? Do we need to use the initial count? Why do we have counts on subsequent elements if we only add 1?), but the logical Clojure solution would just be:

  (frequencies (map second v))
  ;; => {"one" 2, "two" 2, "three" 1, "four" 1}

  ;; or:

  (update-vals (group-by second v) count)
  ;; => {"one" 2, "two" 2, "three" 1, "four" 1}

  ;; +(#:'=v[;1];?v[;1])
  ;; flip(count each group v[;1];unique v[;1])

So, shorter than the readable K version in a Lisp.

What did we learn here? Probably nothing.

K is great for sequence operations--not sure what we're trying to imply about Lisps.

It's trivial to extend the SERIES library to allow collecting sums in a hash-table (It was just a cut-paste of the collect-hash function with setf changed to incf; further extending to allow generic modifications of values is an exercise left to the reader). That allows a shorter (but not as short as I'd like) implementation. It could be shorter if the output list were to have elements like ("one" 1) as the multiple-value-bind exists to reverse that ordering for unpacking the hash-table at the end.

Here's the result (if you wanted to further optimize and know that the result will fit in a fixnum (i.e. +/- 2^62 on modern implementations, you can change the "'number" to "'fixnum"):

  (defun unique-sum (list)
    (multiple-value-bind (keys values)
        (scan-hash
         (collect-hash-sum
          (map-fn 'string #'cadr (scan list))
          (map-fn 'number #'car (scan list))
          :test #'equal))
      (map-fn 'list #'list values keys)))

And the extension to SERIES:

  (series::defS collect-hash-sum (keys values &rest option-plist)
    "(collect-hash keys values :test :size :rehash-size :rehash-threshold)
  
  Combines a series of keys and a series of values together into a hash
  table.  Duplicate keys sum the values. The keyword arguments specify
  the attributes of the hash table to be produced.  They are used as
  arguments to MAKE-HASH-TABLE"
    (fragl ((keys t) (values t) (option-plist))
    ((table))
    ((table t (apply #'make-hash-table option-plist)))
    ()
           ()
           ((incf (gethash keys table 0) values)) () () nil)
   :optimizer
    (series::apply-literal-frag
      (list '(((keys t) (values t) (table)) ((table)) () ()
              () ((incf (gethash keys table 0) values)) () () nil)
            keys values `(make-hash-table ,@ option-plist)))
   :trigger t)

Doing the naive thing in CL without thinking about things like 'efficiency' or 'maintainability':

  (let ((test-input '((1 "one") (1 "two") (1 "three") (1 "one") (1 "four") (1 "two"))))
    (mapcar (lambda (string)
              (list (count string test-input :test #'string= :key #'second)
                    string))
      (remove-duplicates (mapcar #'second test-input)
                         :test #'string= :from-end t)))

I will admit it's not as short as:

  v:((1;"one");(1;"two");(1;"three");(1;"one");(1;"four");(1;"two"))
  +(#:'=v[;1];?v[;1])

awk:

  echo '1 "one"\n1 "two"\n1 "three"\n1 "one"\n1 "four"\n1 "two"' | awk '{ counters[$2] += $1 } END { for (id in counters) { print counters[id], id } }'

  2 "two"
  1 "four"
  1 "three"
  2 "one"

Does the K solution handle non-unity values in the beginning of each sublist? e.g. ((1 "one")(2 "one")) should result in ((3 "one"))

If they wanted to have a language that isn't lisp but whose name started with a K, wouldn't it have made more sense to call it kil?