ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Nix List Uniqueness Check

Nix

Goal -- WPM

Ready
Exercise Algorithm Area
1{

2let

3# Helper function to check for duplicates within a list.

4# It iterates through the list and compares each element with the rest.

5hasDuplicates = list:

6if list == null || lib.length list == 0 then

7false # An empty list has no duplicates

8else

9let

10first = lib.head list;

11rest = lib.tail list;

12in

13lib.elem first rest || hasDuplicates rest;

14

15in

16{

17# Main function to check if all elements in a list are unique.

18# Returns true if all elements are unique, false otherwise.

19areElementsUnique = list:

20if list == null then

21true # A null list can be considered to have unique elements (vacuously true)

22else

23!hasDuplicates list;

24}

25}
Algorithm description viewbox

Nix List Uniqueness Check

Algorithm description:

This Nix function checks if all elements in a given list are unique. It's a fundamental operation for data validation and manipulation in Nix, ensuring that no duplicate values exist within a list before further processing. This is commonly used when processing package lists or configuration options where uniqueness is a requirement.

Algorithm explanation:

The `areElementsUnique` function determines if a Nix list contains only unique elements. It leverages a recursive helper function, `hasDuplicates`, which checks if the head of the list exists in its tail. The base case for `hasDuplicates` is an empty or null list, which contains no duplicates. The main function `areElementsUnique` simply negates the result of `hasDuplicates`. The time complexity is O(N^2) in the worst case, where N is the length of the list, due to the nested nature of `lib.elem` within the recursion. The space complexity is O(N) due to the recursion depth for `hasDuplicates`. Edge cases like null or empty lists are handled.

Pseudocode:

function hasDuplicates(list):
  if list is null or empty:
    return false
  else:
    first_element = head of list
    rest_of_list = tail of list
    if first_element is in rest_of_list:
      return true
    else:
      return hasDuplicates(rest_of_list)

function areElementsUnique(list):
  if list is null:
    return true
  else:
    return not hasDuplicates(list)