Haskell Power Set 函数

Question

我收到错误：

working.hs:186:25: error:
* Couldn't match expected type: Set (Set a)
              with actual type: [[a]]
* In the expression:
    union (map (insert x) (powerSet s)) (powerSet s)
  In an equation for `powerSet':
      powerSet (Node x s)
        = union (map (insert x) (powerSet s)) (powerSet s)
* Relevant bindings include
    s :: Set a (bound at working.hs:186:20)
    x :: a (bound at working.hs:186:18)

working.hs:186:48: error:
* Couldn't match expected type: [[a]]
              with actual type: Set (Set a)
* In the second argument of `map', namely `(powerSet s)'
  In the first argument of `union', namely
    `(map (insert x) (powerSet s))'
  In the expression: union (map (insert x) (powerSet s)) (powerSet s)
* Relevant bindings include
    s :: Set a (bound at working.hs:186:20)
    x :: a (bound at working.hs:186:18)

working.hs:186:62: error:
* Couldn't match expected type: [[a]]
              with actual type: Set (Set a)
* In the second argument of `union', namely `(powerSet s)'
  In the expression: union (map (insert x) (powerSet s)) (powerSet s)
  In an equation for `powerSet':
      powerSet (Node x s)
        = union (map (insert x) (powerSet s)) (powerSet s)
* Relevant bindings include
    s :: Set a (bound at working.hs:186:20)
    x :: a (bound at working.hs:186:18)

Failed, no modules loaded.

我的职能是：

powerSet :: Set a -> Set (Set a)
powerSet EmptyS = singleton EmptyS
powerSet (Node x s) = union (map (insert x) (powerSet s)) (powerSet s)

为什么我会收到错误消息？

Answer 1

正如其他贡献者在对该问题的评论中提到的那样，

map

仅适用于列表。要将

insert x

“映射”到

powerSet s

，您必须为

Set

类型创建一个仿函数实例，然后使用

fmap

代替。

instance Functor Set where
    fmap f EmptyS      = EmptyS
    fmap f (Node x s') = Node (f x) (fmap f s')

那么你就会：

powerSet :: Ord a => Set a -> Set (Set a)
powerSet EmptyS = singleton EmptyS
powerSet (Node x s') = union (fmap (insert x) (powerSet s')) (powerSet s')

我没有看到你的代码

singleton

，所以为了完整起见，我将包括我的代码。

singleton :: Ord a => a -> Set a
singleton x = Node x EmptyS

我注意到您的

powerSet

类型签名不包含

Ord a

约束。您将需要这个，因为

insert

需要

Ord a

。然后，为了在集合本身上使用它，您还必须定义

Ord

和

Eq

的实例

Set a

。这相当简单：

instance (Ord a) => Eq (Set a) where
  (==) EmptyS EmptyS = True
  (==) EmptyS _      = False
  (==) _ EmptyS      = False
  (==) s0 s1         = (toList s0) == (toList s1)

instance (Ord a) => Ord (Set a) where
  compare s0 s1 = compare (toList s0) (toList s1)

（欢迎来到 StackOverflow！感谢您选择 Haskell！）