Skip to content

Instantly share code, notes, and snippets.

@pchiusano
Created October 13, 2021 19:32
Show Gist options
  • Save pchiusano/f09eb3cd3afe24fe4c00de96a289174d to your computer and use it in GitHub Desktop.
Save pchiusano/f09eb3cd3afe24fe4c00de96a289174d to your computer and use it in GitHub Desktop.
Quickselect in Unison
{{
``List.selectBy o k as`` yields the same results as ``List.at k sorted``
where ''sorted'' is a sorted version of ''as'', but in (expected) linear time
without fully sorting the list.
```
List.selectBy Universal.ordering 2 [4,1,3,2,5]
```
```
List.selectBy Universal.ordering 2 [1,2,5,4,3]
```
This implementation has quadratic performance if the list is already sorted.
}}
List.selectBy : (a -> a -> Ordering) -> Nat -> [a] -> Optional a
List.selectBy o n = cases
[] -> None
(pivot +: as) ->
as' = List.filter (a -> Ordering.ltBy o a pivot) as
match List.size as' with
s | s == n -> Some pivot
| s < n -> List.selectBy o (Nat.drop n (s+1)) (List.drop s as)
| otherwise -> List.selectBy o n as'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment