haskell - 将集合并集实现为幺半群

Question

这里，我需要定义一个支持下面集合数据类型的集合并运算的幺半群。

我的最小(不)工作示例是:

import Data.List

data Set a = Set [a]
  deriving (Show, Eq)

-- emptySet is a set with no elements
emptySet :: (Eq a, Ord a) => Set a
emptySet = Set []

-- member tests if an element is in a set
member :: Eq a => a -> Set a -> Bool
member _ (Set ([])) = False
member value (Set (x : xs)) = if x == value then True else member value (Set xs)

-- add a member to a set
add :: (Eq a, Ord a) => a -> Set a -> Set a
add value (Set arr) = if member value (Set arr) then (Set arr) else Set (sort (arr ++ [value]))


instance Ord a => Monoid (Set a) where
  mempty = emptySet

unionHelper :: a -> Set a -> [a] -> Set a
unionHelper value (Set xs) [] = (Set xs)
unionHelper value (Set xs) [y] = add y xs
unionHelper value (Set xs) (y : ys) = add y (unionHelper (head ys) (Set xs) (tail ys))

instance Semigroup (Set a) where
  Set xs <> Set ys = go xs ys
    where go xs [] = Set xs
          go xs (y:ys) = add y (Set xs)
          

main :: IO ()
main = do
  print (add 1 (add 2 (add 3 emptySet)) <> add 4 (add 2 emptySet)) -- Must return [1,2,3,4].

编译器对上面的代码片段有话要说:

Main.hs:47:40: error:
    • Couldn't match expected type: Set a
                  with actual type: [a]
    • In the second argument of ‘add’, namely ‘xs’
      In the expression: add y xs
      In an equation for ‘unionHelper’:
          unionHelper value (Set xs) [y] = add y xs
    • Relevant bindings include
        y :: a (bound at Main.hs:47:29)
        xs :: [a] (bound at Main.hs:47:24)
        value :: a (bound at Main.hs:47:13)
        unionHelper :: a -> Set a -> [a] -> Set a (bound at Main.hs:46:1)
   |
47 | unionHelper value (Set xs) [y] = add y xs
   |                                        ^^
Failed, no modules loaded.
 
<interactive>:1:1: error:
    • Variable not in scope: main
    • Perhaps you meant ‘min’ (imported from Prelude)

由于我还是个初学者，我很难找到正确的语法。有什么帮助吗？

Answer 1

如 a previous answer 所示让我们拆开错误消息。 Main.hs:47:40: error: 和

   |
47 | unionHelper value (Set xs) [y] = add y xs
   |                                        ^^

告诉你问题出在第 47 行。(这实际上只是 OP 中代码的第 25 行。)

请注意 xs 下的两个扬抑符，表明问题出在表达式 xs 上，而不是该行的任何其他部分。

错误信息是:

• Couldn't match expected type: Set a
              with actual type: [a]

这表示，由于类型注释和/或类型推断，编译器期望 xs 具有 Set a 类型，但实际上事实证明xs 的类型是 [a]。由于 Set a 与 [a] 的类型不同，因此这是一个问题。

您认为编译器为何期望(或要求)xs 具有 Set a 类型？ add 函数的类型是什么。它采用哪些参数，这些参数应该具有什么类型？

此外，为什么你认为编译器会推断出xs是[a]？您可以采取什么措施来解决这个问题？

---

如果您对任何类型有疑问，错误消息也会告诉您:

• Relevant bindings include
    y :: a (bound at Main.hs:47:29)
    xs :: [a] (bound at Main.hs:47:24)
    value :: a (bound at Main.hs:47:13)
    unionHelper :: a -> Set a -> [a] -> Set a (bound at Main.hs:46:1)

在这里我们看到 y 的类型为 a，xs 的类型为 [a]，并且 值也a。

希望以上信息能够帮助您解决眼前的问题。如n. m. will see y'all on Reddit写入 a comment但是，unionHelper 函数的问题不仅仅是立即出现错误。

这里还有另一个提示:在尝试代码时，不要编写任何函数的类型声明。只要坚持基本的语言功能，编译器就可以自行推断类型(一旦他们编译，也就是说)。

然而，用类型显式注释 Haskell 函数被认为是惯用的。我通常做的是在不使用类型注释的情况下开发它们，直到它们工作并具有我希望它们具有的类型。

然后我使用工具(GHCi 或 IDE 插件)来生成类型注释。