联合的咖喱版本？

Question

我有这个集合并集的简单版本

union (s, []) = s 
union (s, t:ts) | member (t,s) = union (s,ts) 
                | otherwise = t : union (s,ts)

其中 member 是 elem 的一个版本。但是我在教科书中找到的这个说 union 必须是咖喱 union

uniteElems [] = []
uniteElems (h:t) = union h (uniteElems t)

这让我很困惑。正如文本所说，uniteElems 是一种原型折叠（foldr？），即它应该采用单个列表并递归应用 union，从而清除重复项。这就是我的联合

的“咖喱版本”吗

union2 s []                 = s
union2 s (t:ts) | elem t s  = union2 s ts
                | otherwise = union2 (t:s) ts

无论如何，这个 union2 不能像在 uniteElems 中那样工作，给出一个错误。

     * Non type-variable argument in the constraint: Num [a]
:       (Use FlexibleContexts to permit this)
:     * When checking the inferred type
:         it :: forall a. (Eq a, Num [a]) => [a]

不过，这个版本确实有效

uniteElems [] = []
uniteElems (h:t) = union2 [h] (uniteElems t)

但我在 [h] 中陷入困境。是什么让 uniteElems（一种原型折叠）发挥作用？我想，联合函数如何寻找 foldr 的常规使用将是另一个相关问题。

Answer 1

您的代码中似乎对各种函数的预期含义（目的或语义）有些混淆。与此相关，函数的类型肯定存在一些混淆。

让我们从 uniteElems 开始。它似乎具有类型 Eq a => [a] -> [a] 以及一些记录的保证，即输入列表是一个常规的旧列表，而输出列表实际上是一个集合。它依赖于现有的函数 union :: Eq a => a -> [a] -> [a]。看uniteElems的定义，好像这个union函数应该取一个元素和一个集合（表示为一个列表），然后把元素加入到集合中。

现在，让我们看看您对 union2 的定义（或 union 的类似定义，只是未加柯里化）。它的类型是 Eq a => [a] -> [a] -> [a]，它的意思似乎是如果给它两个表示集合的列表，它将 return 一个表示两个集合并集的列表。

马上，似乎很清楚问题是什么：uniteElems 中预期的 union 和您定义的 union2 根本不同！一种是将单个元素添加到集合中，另一种是组合两个完整的集合。

现在，您对 uniteElems 的提议修改为何有效似乎也很清楚：基本上，您获取每个单独的元素，将其变成一个单例集，然后使用您的 union2 函数组合这些集合。

为了让uniteElems做你想做的事，你需要一个更简单的union定义，比如：

union :: Eq a => a -> [a] -> [a]
union t s | elem t s  = s
          | otherwise = t:s

至于折叠和原型折叠，uniteElems 是原型折叠，因为它本质上是提供了一些参数的折叠。也就是说，您可以这样写：

uniteElems = foldr union []

联合的咖喱版本？

A curried version of union for a fold?

haskell

currying