From cd6397519fe8f94fae3646050d8742b11e287bfa Mon Sep 17 00:00:00 2001
From: polykernel <81340136+polykernel@users.noreply.github.com>
Date: Mon, 1 Nov 2021 00:16:52 -0400
Subject: lib/lists: mutuallyExclusive function optimization

The current implementation of `mutuallyExclusive` builds a new list with
length subtracted by one on every recursive call which is expensive. When
b is empty, the function still traverses a in its entirety before returning
a result.

The new implementation uses `any` to check if each element of list b is in
list a using `elem`. This maintains short circuiting when list a or b is empty
and has a worst case time complexity of O(nm).
---
 lib/lists.nix | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

(limited to 'lib')

diff --git a/lib/lists.nix b/lib/lists.nix
index e469f3ef2652..1dbff7668d75 100644
--- a/lib/lists.nix
+++ b/lib/lists.nix
@@ -642,7 +642,7 @@ rec {
        unique [ 3 2 3 4 ]
        => [ 3 2 4 ]
    */
- unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
+  unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) [];
 
   /* Intersects list 'e' and another list. O(nm) complexity.
 
@@ -663,9 +663,6 @@ rec {
   /* Test if two lists have no common element.
      It should be slightly more efficient than (intersectLists a b == [])
   */
-  mutuallyExclusive = a: b:
-    (builtins.length a) == 0 ||
-    (!(builtins.elem (builtins.head a) b) &&
-     mutuallyExclusive (builtins.tail a) b);
+  mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b);
 
 }
-- 
cgit v1.2.3