时间戳

首页 > 解决方案 > 一个咖喱版的 union 折叠？

haskell - 一个咖喱版的 union 折叠？

问题描述

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

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]. 什么会使uniteElemsproto-fold 起作用？我想，联合函数如何定期使用foldr将是另一个相关问题。

标签： haskellcurrying

解决方案

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

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

现在，让我们看看您对union2（或类似的union，只是未加咖喱的）的定义。它有 type Eq a => [a] -> [a] -> [a]，其含义似乎是，如果给它两个表示集合的列表，它将返回一个表示两个集合并集的列表。

马上，问题出在哪里似乎很清楚：union预期的 inuniteElems和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 []

推荐阅读