Поскольку это O (n²) , nub считается вредным .
Как также предлагается в статье, альтернативой является использование упорядочения, а не равенства, чтобы уменьшить сложность до O (n log n) . В то время как в Haskell это означает только изменение ограничения класса типа:
nub :: Eq a => [a] -> [a]
nubOrd :: Ord a => [a] -> [a]
и настройку алгоритма, express это ограничение в SML становится немного сложнее. В то время как у нас do есть ''a для представления Eq a => a (что мы можем использовать = на нашем вводе), мы не имеем аналогичную поддержку специального синтаксиса для элементов, которые можно сравнить как меньше / равно / больше, и у нас также нет классов типов. У нас do есть следующий встроенный тип заказа:
datatype order = LESS | EQUAL | GREATER
, поэтому, если вам нравится решение kopecs, вариант с лучшим временем выполнения:
val nubOrd : ('a * 'a -> order) -> 'a list -> 'a list
, поскольку он может использовать что-то вроде математического набора ранее замеченных элементов, реализованного с использованием некоторого сбалансированного дерева поиска; n вставляет каждую сложность O (log n) занимает всего O (n log n) шагов.
Одной из отличительных черт SML является его составная модульная система. Вместо использования полиморфизма параметри c и подачи функции nubOrd с функцией сравнения порядка вы можете создать модуль, который принимает другой модуль в качестве параметра ( функтор ).
Во-первых, давайте определим подпись для модулей, которые представляют упорядочение типов:
signature ORD =
sig
type t
val compare : t * t -> order
end
(обратите внимание, что перед t нет '. )
Это означает, что любой может создать struct ... end : ORD, указав t и соответствующую функцию compare для t s. Многие встроенные типы имеют предопределенные compare функции: int имеет Int.compare и real имеет Real.compare.
Затем определите дерево- основанная структура данных набора; Я использовал двоичное дерево поиска и пропустил большинство функций, кроме тех, которые строго необходимы для выполнения этой задачи. В идеале вы могли бы расширить интерфейс и использовать более качественный тип дерева, например самобалансирующееся дерево. (К сожалению, поскольку вы пометили эти вопросы и ответы как SML / NJ и Moscow ML, я не был уверен, какой модуль использовать, поскольку они по-разному расширяют стандартную библиотеку, когда дело касается сбалансированных деревьев.)
functor TreeSet (X : ORD) =
struct
type t = X.t
datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree
val empty = Leaf
fun member (x, Leaf) = false
| member (x, Branch (left, y, right)) =
case X.compare (x, y) of
EQUAL => true
| LESS => member (x, left)
| GREATER => member (x, right)
fun insert (x, Leaf) = Branch (Leaf, x, Leaf)
| insert (x, Branch (left, y, right)) =
case X.compare (x, y) of
EQUAL => Branch (left, y, right)
| LESS => Branch (insert (x, left), y, right)
| GREATER => Branch (left, y, insert (x, right))
end
Наконец, функтор ListUtils содержит служебную функцию nubOrd. Функтор принимает структуру X : ORD точно так же, как функтор TreeSet. Он создает структуру XSet, специализируя функтор TreeSet с использованием того же модуля упорядочивания. Затем он использует это XSet для эффективно сохраняет запись элементов, которые он видел раньше.
functor ListUtils (X : ORD) =
struct
structure XSet = TreeSet(X)
fun nubOrd (xs : X.t list) =
let
val init = ([], XSet.empty)
fun go (x, (ys, seen)) =
if XSet.member (x, seen)
then (ys, seen)
else (x::ys, XSet.insert (x, seen))
in rev (#1 (foldl go init xs))
end
end
Использование этого функтора для удаления дубликатов в int list:
structure IntListUtils = ListUtils(struct
type t = int
val compare = Int.compare
end)
val example = IntListUtils.nubOrd [1,1,2,1,3,1,2,1,3,3,2,1,4,3,2,1,5,4,3,2,1]
(* [1, 2, 3, 4, 5] *)
Цель всего этого беспорядка - nubOrd без прямого дополнительного параметра функции.
К сожалению, чтобы это распространялось на int list list, вам необходимо создать функцию compare для этого типа, поскольку, в отличие от Int.compare, в стандартной библиотеке нет универсальной c функции. либо. (Здесь Haskell намного больше эргономики c.)
Так что вы можете go и написать общую c, функцию сравнения лексикографических списков: если вы знаете, как сравнивать два элемента типа 'a, вы знаете, как сравнить два списка из них, независимо от типа элемента:
fun listCompare _ ([], []) = EQUAL (* empty lists are equal *)
| listCompare _ ([], ys) = LESS (* empty is always smaller than non-empty *)
| listCompare _ (xs, []) = GREATER (* empty is always smaller than non-empty *)
| listCompare compare (x::xs, y::ys) =
case compare (x, y) of
EQUAL => listCompare compare (xs, ys)
| LESS => LESS
| GREATER => GREATER
А теперь,
structure IntListListUtils = ListUtils(struct
type t = int list
val compare = listCompare Int.compare
end)
val example2 = IntListListUtils.nubOrd [[1,2,3],[1,2,3,2],[1,2,3]]
(* [[1,2,3],[1,2,3,2]] *)
Итак, хотя [1,2,3] и [1,2,3,2] содержат дубликаты, они не EQUAL, когда вы compare их. Но третий элемент соответствует EQUAL первому, поэтому он удаляется как дубликат.