Можно ли создать "универсальную" функцию в Standard ML?

Question

Я хотел бы создать функцию remove_duplicates это требует list любого типа (например, может быть int list или bool list или int list list или whatever list) и возвращает тот же список без дубликатов, возможно ли это в Standard ML?

Answer 1

Возможна ли функция, которая принимает список любого типа и возвращает список без дубликатов в стандартном ML?

Нет.

Чтобы определить, является ли один элемент дубликатом другого, их значения должны быть сопоставимы. "Любой тип", или'aв Стандартном ML несопоставимо для равенства. Итак, пока у вас не может бытьval nub : 'a list -> 'a list который удаляет дубликаты, вот четыре альтернативных варианта:

1. Что предлагает @qouify, встроенный тип равенства ''a, так что все, что вы можете использовать = на:

   val nub : ''a list -> ''a list
   

2. Что предлагает @kopecs, функцию, которая принимает в качестве параметра оператор равенства:

   val nub : ('a * 'a -> bool) -> 'a list -> 'a list
   

   Это обобщение 1., поскольку здесь nub op= : ''a list -> ''a list. Это удобное решение, так как оно позволяет удалять не только дубликаты, но и избыточные представители произвольных классов эквивалентности, напримерnub (fn (x, y) => (x mod 3) = (y mod 3))сохранит только целые числа, различающиеся по модулю 3. Но его сложность равна O(n²). (-_-) ï¾ ‰ âŒ'â "" â "â" "

3. Поскольку это O(n²), nubсчитается вредным.

   Как также предлагается в статье, альтернативой является использование упорядочения, а не равенства, чтобы уменьшить сложность до O(n log n). В Haskell это означает только изменение ограничения класса типа:

   nub    :: Eq a  => [a] -> [a]
   nubOrd :: Ord a => [a] -> [a]
   

   и настраивая алгоритм, становится немного сложнее выразить это ограничение в SML. Пока у нас есть''a представлять Eq a => a (что мы можем использовать =на нашем входе), у нас нет подобной специальной поддержки синтаксиса для элементов, которые можно сравнить как меньше / равно / больше, а также у нас нет классов типов. У нас есть встроенный тип ордера:

   datatype order = LESS | EQUAL | GREATER
   

   поэтому, если вам нравится решение kopecs, вариант с лучшим временем работы:

   val nubOrd : ('a * 'a -> order) -> 'a list -> 'a list
   

   поскольку он может использовать что-то вроде математического набора ранее замеченных элементов, реализованного с использованием некоторого сбалансированного дерева поиска; n вставляет каждый со сложностью O(log n), занимает в общей сложности O(n log n) шагов.

4. Одна из лучших особенностей SML - его система составных модулей. Вместо использования параметрического полиморфизма и подачи функцииnubOrdс помощью функции сравнения порядков вы можете создать модуль, который принимает другой модуль в качестве параметра (функтор).

   Во-первых, давайте определим сигнатуру для модулей, которые представляют упорядочение типов:

   signature ORD =
   sig
     type t
     val compare : t * t -> order
   end
   

   (Обратите внимание, что нет ' спереди t.)

   Это означает, что любой может сделать struct ... end : ORD указав t и соответствующий compare функция для tс. Многие встроенные типы имеют предопределенныеcompareфункции: int имеетInt.compareи реальное имеет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, в стандартной библиотеке также нет универсального. (Вот где Haskell намного эргономичнее.)

   Итак, вы можете пойти и написать общую функцию сравнения лексикографических списков: если вы знаете, как сравнивать два элемента типа '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 к первому, и поэтому он удаляется как дубликат.

Некоторые последние наблюдения:

• Вы можете считать, что даже если каждый compareвыполняется только O(log n) раз, одинcompare для некоторой сложной структуры данных, такой как (whatever * int) list listвсе еще может быть дорогим. Итак, еще одно улучшение, которое вы можете сделать здесь, - это кэшировать результат каждогоcompare вывод, который на самом деле является тем, что Haskell nubOrdOn оператор делает. â ”³â” â ”³ ヽ (ಠل œà²) ï¾

• Функторный подход широко используется в библиотеке Jane Street OCaml Base. Быстрое решение заключалось в том, чтобы передать'a * 'a -> order функционировать каждый раз, когда вы nubчто нибудь. Одна мораль, однако, заключается в том, что хотя модульная система действительно добавляет многословия, если вы предоставите достаточное количество этого оборудования в стандартной библиотеке, это станет довольно удобным.

• Если вы считаете, что улучшения с O(n²) до O(n log n) недостаточно, рассмотрите универсальную нисходящую дискриминацию Фрица Хенглейна для сортировки и разделения в линейном времени (2012) и пакет дискриминации Haskell Эдварда Кметта .nub для O(n) nub.

Answer 2

Да, sml предоставляет полиморфизм для таких вещей. Во многих случаях вам фактически не важен тип элемента в ваших списках (или других структурах). Например, эта функция проверяет (уже присутствует вList структура) на предмет наличия элемента в списке:

fun exists _ [] = false
  | exists x (y :: l) = x = y orelse exists x l

Такая функция работает для любого типа списка, если для этого типа определен оператор равенства (такой тип называется типом равенства). Вы можете сделать то же самое дляremove_duplicates. Для работы со списком элементов не равных типов вам нужно будет указатьremove_duplicates дополнительная функция, которая проверяет, равны ли два элемента.

Answer 3

Да. Это возможно в SML за счет использования параметрического полиморфизма. Вам нужна функция самого общего типа'a list -> 'a list где 'a - это переменная типа (т. е. переменная, которая варьируется между типами), которая будет читаться как альфа.

Для получения более конкретных примеров того, как вы можете применить это (явная переменная типа после fun необязательно):

fun 'a id (x : 'a) : 'a = x

Здесь у нас есть функция идентичности с типом 'a -> 'a.

Мы можем объявить аналогичные функции с некоторой степенью специализации типов, например

fun map _ [] = []
  | map f (x::xs) = f x :: map f xs

куда map имеет самый общий тип ('a -> 'b) -> 'a list -> 'b list, т. е. принимает два каррированных аргумента, один с некоторым типом функции, а другой с некоторым типом списка (согласуется с доменом функции), и возвращает новый список с типом, заданным codomain функции.

Для вашей конкретной проблемы вы, вероятно, также захотите использовать функцию равенства, чтобы определить, что является "дубликатом", или вы, вероятно, ограничитесь "типами равенства" (типами, которые можно сравнить с op=, представленные переменными типа с двумя ведущими апострофами, например, ''a).