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

1 files changed, 2 insertions, 5 deletions

diff --git a/lib/lists.nix b/lib/lists.nix
index e469f3ef265..1dbff7668d7 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);
 
 }