functional-programming - 是否可以在标准 ML 中创建“通用”函数？

Question

我想创建一个remove_duplicates采用list任何类型的函数（例如可以是 anint list或 abool list或 aint list list或 a whatever list）并返回相同的列表而没有重复，这在标准 ML 中是否可行？

Answer 1

在标准 ML 中，是否有一个函数可以获取任何类型的列表并返回没有重复的列表？

不。

要确定一个元素是否与另一个元素重复，它们的值必须是可比较的。“任何类型”或'a标准 M​​L 中的“任何类型”都无法进行相等性比较。因此，虽然您不能使用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²)。(-_- )ﾉ⌒┻━┻</p>

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
   

   '（注意前面没有a t。）

   这意味着任何人都可以struct ... end : ORD通过为 s 指定 at和相应的compare函数来生成 a t。许多内置类型都有预定义的compare函数：int hasInt.compare和real has Real.compare。

   然后，定义一个基于树的集合数据结构；我使用了二叉搜索树，并且跳过了大多数功能，但执行此壮举所必需的功能。理想情况下，您可以扩展接口并使用更好的树类型，例如自平衡树。（不幸的是，由于您已将此 Q&A 标记为 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 更符合人体工程学的地方。）

   因此，您可以编写一个通用的字典式列表比较函数：如果您知道如何比较 type 的两个元素'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对于某些复杂的数据结构（例如 a ）来说，单个(whatever * int) list list可能仍然很昂贵。因此，您可以在此处进行的另一项改进是缓存每个compare输出的结果，这实际上是 HaskellnubOrdOn运算符所做的。┳━┳ヽ(ಠل͜ಠ)ﾉ</p>

• 仿函数方法在Jane Street 的 OCaml Base 库中被广泛使用。'a * 'a -> order快速的解决方案是每次你nub做某事时都传递一个函数。不过，一个道理是，虽然模块系统确实增加了冗长，但如果您在标准库中提供足够多的这种机制，它将变得非常方便。

• 如果您认为从O(n²)到O(n log n)的改进还不够，请考虑 Fritz Henglein 的Generic top-down discriction for sorting and partitioning in linear time (2012) 和 Edward Kmett 的 Haskell判别包nub对于O(n ) nub .

Answer 2

是的。通过使用参数多态性，这在 SML 中是可能的。您想要一个最通用类型的函数，'a list -> 'a list其中'a是一个类型变量（即，范围超过类型的变量），它将被读取为 alpha。

有关如何应用它的一些更具体的示例（之后的显式类型变量fun是可选的）：

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

这里我们有 type 的标识函数'a -> 'a。

例如，我们可以声明具有某种程度特殊化类型的类似函数

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

Wheremap具有最通用的类​​型('a -> 'b) -> 'a list -> 'b list，即采用两个柯里化参数，一个具有某种函数类型，另一个具有某种列表类型（与函数的域一致）并返回一个新列表，其类型由函数的 codomain 给出。

对于您的特定问题，您可能还需要使用相等函数来确定什么是“重复”，或者您可能会将自己限制为“相等类型”（可以与 比较op=的类型，由类型变量表示两个前导撇号，例如''a)。

Answer 3

是的，sml 提供了多态性来做这些事情。在许多情况下，您实际上并不关心列表（或其他结构）中项目的类型。例如，此函数检查（已存在于List结构中）列表中是否存在项目：

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

只要为这种类型定义了相等运算符（这种类型称为相等类型），这种函数就适用于任何类型的列表。您可以对remove_duplicates. 为了使用非相等类型的项目列表，您必须提供remove_duplicates一个额外的函数来检查两个项目是否相等。