Subject: bug#50927: Considering only entries with unique keys in map.el?

From: Okamsn <[email-masked]>
Date: Fri, 01 Oct 2021 00:55:21 +0000

Some kinds of maps, such as alists and plists, can contain duplicate
keys.  These duplicates are effectively ignored in functions like
`map-elt`, but are not ignored in functions like `map-do` or `map-length`.

To me, it would make more sense if these functions only considered the
valid entries in the map.  For example,

    (map-pairs '(a 1 b 2 a 3))

currently returns '((a . 1) (b . 2) (a . 3)), even though '(a . 3) is
meant to be ignored in actual usage, as it is preceded by an earlier
entry with the same key.  This is a misleading behavior.

I do not know whether the current behavior is desirable.  Is it?

Please consider changing the library so that the duplicate,
meant-to-be-ignored entries are actually ignored for functions that
operate on the entire map.

I have attached an example diff.

Thank you.

diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el
index 77431f0c59..9db2ddd95f 100644
--- a/lisp/emacs-lisp/map.el
+++ b/lisp/emacs-lisp/map.el
@@ -202,6 +202,25 @@ map-nested-elt
                   map)
       default))
 
+(defun map--remove-duplicate-keys (map)
+  "Make a version of MAP without duplicated keys.
+
+Unlike hash tables, association and property lists allow
+duplicate keys in the data structure.  This function returns the
+map with such keys and their respective data removed."
+  (if (map--plist-p map)
+      (let ((found-keys)
+            (result))
+        (while map
+          (let ((key (pop map))
+                (value (pop map)))
+            (unless (member key found-keys)
+              (push key found-keys)
+              (push key result)
+              (push value result))))
+        (nreverse result))
+    (seq-uniq map (lambda (a b) (equal (car a) (car b))))))
+
 (cl-defgeneric map-keys (map)
   "Return the list of keys in MAP.
 The default implementation delegates to `map-apply'."
@@ -234,6 +253,7 @@ map-length
   (hash-table-count map))
 
 (cl-defmethod map-length ((map list))
+  (setq map (map--remove-duplicate-keys map))
   (if (map--plist-p map)
       (/ (length map) 2)
     (length map)))
@@ -489,7 +509,7 @@ map-apply
       (cl-call-next-method)
     (mapcar (lambda (pair)
               (funcall function (car pair) (cdr pair)))
-            map)))
+            (map--remove-duplicate-keys map))))
 
 (cl-defmethod map-apply (function (map hash-table))
   (let (result)
@@ -504,6 +524,7 @@ map-apply
                    map))
 
 (cl-defmethod map-do (function (map list))
+  (setq map (map--remove-duplicate-keys map))
   (if (map--plist-p map)
       (while map
         (funcall function (pop map) (pop map)))