`list.unique` needs quadratic time

[radekm]

Hello. According to the documentation list.unique returns in loglinear time.

But it's implementation

pub fn unique(list: List(a)) -> List(a) {
  case list {
    [] -> []
    [x, ..rest] -> [x, ..unique(filter(rest, fn(y) { y != x }))]
  }
}

is quadratic instead. It's especially slow if list is already unique or almost unique.

I believe that the following implementation is faster (if set.contains and set.insert are logarithmic):

pub fn unique(xs: List(a)) -> List(a) {
  let #(result_rev, _) =
    xs
    |> list.fold(#([], set.new()), fn(acc, x) {
      let #(result_rev, seen) = acc
      case set.contains(seen, x) {
        False -> #([x, ..result_rev], set.insert(seen, x))
        True -> #(result_rev, seen)
      }
    })
  result_rev |> list.reverse
}