5 functional-programming ml sml smlnj mosml
我想创建一个函数remove_duplicates，它接受list任何类型的 a （例如可以是 anint list或 abool list或 aint list list或 a whatever list）并返回没有重复的相同列表，这在标准机器学习中可能吗？
\n\n在标准机器学习中，是否有一个函数可以接受任何类型的列表并返回没有重复的列表？
\n
不。
\n要确定一个元素是否与另一个元素重复，它们的值必须具有可比性。“任何类型”，或者\'a在标准机器学习中，对于相等性来说是不可比较的。因此，虽然您无法使用val nub : \'a list -> \'a list删除重复项，但这里有四个替代选项：
@qouify 建议的是内置的 equals type \'\'a，所以你可以使用任何东西=：
val nub : \'\'a list -> \'\'a list\n@kopecs 建议的，一个以相等运算符作为参数的函数：
\nval nub : (\'a * \'a -> bool) -> \'a list -> \'a list\n这是 1. 的概括，因为在这里，nub op= : \'\'a list -> \'\'a list. 这个解决方案很巧妙，因为它不仅可以让您删除重复项，还nub (fn (x, y) => (x mod 3) = (y mod 3))可以删除任意等价类的冗余表示，例如，仅保留模 3 不同的整数。但其复杂度为O(n\xc2\xb2)。(-_- )\xef\xbe\x89\xe2\x8c\x92\xe2\x94\xbb\xe2\x94\x81\xe2\x94\xbb
因为它是O(n\xc2\xb2)，nub被认为是有害的。
正如本文还建议的，另一种方法是使用排序而不是相等来将复杂性降低到O(n log n)。在 Haskell 中，这意味着仅更改类型类约束：
\nnub :: Eq a => [a] -> [a]\nnubOrd :: Ord a => [a] -> [a]\n并调整算法，用 SML 表达这个约束会变得有点复杂。虽然我们确实必须\'\'a表示Eq a => a（我们可以=在输入上使用），但我们没有类似的特殊语法支持可以比较为小于/等于/大于的元素，而且我们也没有类型类。我们有以下内置订单类型：
datatype order = LESS | EQUAL | GREATER\n因此，如果您喜欢 kopecs 的解决方案，则具有更好运行时间的变体是：
\nval nubOrd : (\'a * \'a -> order) -> \'a list -> \'a list\n因为它可以使用类似于先前见过的元素的数学集合之类的东西，并使用某种平衡搜索树来实现；n插入每个复杂度为O(log n) 的操作总共需要O(n log n)个步骤。
\nSML 的获奖特性之一是其可组合的模块系统。nubOrd您可以创建一个将另一个模块作为参数（函子）的模块，而不是使用参数多态性并向函数提供顺序比较函数。
首先，让我们为表示类型排序的模块定义一个签名：
\nsignature ORD =\nsig\n type t\n val compare : t * t -> order\nend\n\'（注意前面有\'ta t。）
这意味着任何人都可以struct ... end : ORD通过指定 at和 s 的相应compare函数来创建 a t。许多内置类型都有预定义的compare函数：int hasInt.compare和real has Real.compare。
然后，定义一个基于树的集合数据结构；我使用了二叉搜索树，并且跳过了大多数函数，但执行此任务所必需的函数除外。理想情况下，您可以扩展接口并使用更好的树类型，例如自平衡树。（不幸的是，由于您已将此问答标记为 SML/NJ 和莫斯科 ML，所以我不确定要使用哪个模块，因为它们在平衡树方面以不同的方式扩展了标准库。）
\nfunctor TreeSet (X : ORD) =\nstruct\n type t = X.t\n datatype \'a tree = Leaf | Branch of \'a tree * \'a * \'a tree\n\n val empty = Leaf\n\n fun member (x, Leaf) = false\n | member (x, Branch (left, y, right)) =\n case X.compare (x, y) of\n EQUAL => true\n | LESS => member (x, left)\n | GREATER => member (x, right)\n\n fun insert (x, Leaf) = Branch (Leaf, x, Leaf)\n | insert (x, Branch (left, y, right)) =\n case X.compare (x, y) of\n EQUAL => Branch (left, y, right)\n | LESS => Branch (insert (x, left), y, right)\n | GREATER => Branch (left, y, insert (x, right))\nend\n最后，ListUtils函子包含nubOrd效用函数。函子采用的结构与函子X : ORD一样TreeSet。它通过使用相同的排序模块XSet专门化函子来创建结构。TreeSet然后它使用它XSet来有效地记录它之前见过的元素。
functor ListUtils (X : ORD) =\nstruct\n structure XSet = TreeSet(X)\n\n fun nubOrd (xs : X.t list) =\n let\n val init = ([], XSet.empty)\n fun go (x, (ys, seen)) =\n if XSet.member (x, seen)\n then (ys, seen)\n else (x::ys, XSet.insert (x, seen))\n in rev (#1 (foldl go init xs))\n end\nend\n使用此函子删除 中的重复项int list：
structure IntListUtils = ListUtils(struct\n type t = int\n val compare = Int.compare\n end)\n\nval example = IntListUtils.nubOrd [1,1,2,1,3,1,2,1,3,3,2,1,4,3,2,1,5,4,3,2,1]\n (* [1, 2, 3, 4, 5] *)\n所有这些混乱的目的是nubOrd没有直接的额外函数参数。
不幸的是，为了将其扩展到int list list，您需要compare为该类型创建函数，因为与 不同的是Int.compare，标准库中也没有可用的通用函数。（这就是 Haskell 更符合人体工程学的地方。）
因此，您可能会编写一个通用的字典列表比较函数：如果您知道如何比较类型 的两个元素\'a，那么您就知道如何比较其中的两个列表，无论元素类型是什么：
fun listCompare _ ([], []) = EQUAL (* empty lists are equal *)\n | listCompare _ ([], ys) = LESS (* empty is always smaller than non-empty *)\n | listCompare _ (xs, []) = GREATER (* empty is always smaller than non-empty *)\n | listCompare compare (x::xs, y::ys) =\n case compare (x, y) of\n EQUAL => listCompare compare (xs, ys)\n | LESS => LESS\n | GREATER => GREATER\n现在，
\nstructure IntListListUtils = ListUtils(struct\n type t = int list\n val compare = listCompare Int.compare\n end)\nval example2 = IntListListUtils.nubOrd [[1,2,3],[1,2,3,2],[1,2,3]]\n (* [[1,2,3],[1,2,3,2]] *)\n因此，即使[1,2,3]和包含重复项，当您使用它们时[1,2,3,2]它们也不是。但第三个元素相对于第一个元素，因此它会作为重复项被删除。EQUALcompare EQUAL
最后一些观察：
\n您可能会认为，即使每个compare仅运行O(log n)compare次，但对于某些复杂的数据结构（例如 a），单个运行(whatever * int) list list可能仍然很昂贵。因此，您可以在此处进行的另一个改进是缓存每个compare输出的结果，这实际上就是 HaskellnubOrdOn运算符的作用。\xe2\x94\xb3\xe2\x94\x81\xe2\x94\xb3 \xe3\x83\xbd(\xe0\xb2\xa0\xd9\x84\xcd\x9c\xe0\xb2\xa0)\xef\xbe \x89
函子方法在Jane Street 的 OCaml Base 库中得到广泛使用。\'a * \'a -> order快速的解决方案是每次执行某件事时都传递一个函数nub。不过，一个寓意是，虽然模块系统确实增加了冗长性，但如果您在标准库中提供足够的这种机制，它将变得相当方便。
如果您认为从O(n\xc2\xb2)到O(n log n)的改进还不够，请考虑 Fritz Henglein\'s Generic top-down discrimination for sorting and partitioning in Linear time (2012) 和 Edward Kmett\ Haskell判别包nub的O(n) nub。
| 归档时间： |
|
| 查看次数： |
874 次 |
| 最近记录： |