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

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

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

[-- Attachment #1: Type: text/plain, Size: 845 bytes --]

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.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: map-uniq.diff --]
[-- Type: text/x-patch; name=map-uniq.diff, Size: 1838 bytes --]

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)))

bug#50927: [External] : bug#50927: Considering only entries with unique keys in map.el?

[Drew Adams]

> 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,

But you, yourself, just said that some functions
don't ignore it.  So it's not an "invalid" entry.

This all comes from Lisp being untyped.  The same
list can serve different uses, some of which are
maps that don't allow duplicates (i.e., they're
functions, not relations).

It's not an error that "these functions" (depending
on which you mean) consider all list elements.

> entry with the same key.  This is a misleading behavior.

Actually, it's a handy behavior.  It's one of the
main ideas behind alists.  You can just remove or
skip the first match of a given key to restore or
use the next one.

My comments aren't really for `map-*' functions,
as I'm not familiar with them.  I'm just commenting
on what you said in general.  HTH.

bug#50927: [External] : bug#50927: Considering only entries with unique keys in map.el?

[Michael Heerdegen]

Drew Adams <drew.adams@oracle.com> writes:

> > entry with the same key.  This is a misleading behavior.
>
> Actually, it's a handy behavior.  It's one of the main ideas behind
> alists.  You can just remove or skip the first match of a given key to
> restore or use the next one.

I tend to agree.  And it's easy to avoid duplicate entries - they
are not introduced when using the map.el functions the right way.

OTOH: the map looping or do- tools also useful for inspecting duplicates
- this is useful.  Avoiding duplicates would also mean O(n^2) equality
tests per map - right?

Michael.

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

[Lars Ingebrigtsen]

Okamsn <okamsn@protonmail.com> writes:

> 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`.

As others have noted, this is part of how alists (etc) work, and we
can't change that -- it would break tons of code.

If you don't want duplicate keys, then you should only use functions
like `map-insert' etc to work on the maps.

So I'm closing this bug report.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no