Haskell二叉树集合的幂集实现：初学者求非Data.Set式方案

Hey there! Let's tackle this powerset problem using your custom binary tree-based Set—no Data.Set tricks here, just good old recursive logic tailored to your structure.

First, a quick tweak to your Set definition: you're missing an empty set constructor, which is critical for powersets (since the powerset of the empty set is a set containing only the empty set). Let's update it:

data Set a = Empty | Node a | Tree a (Set a) (Set a) deriving (Show, Eq)

• Empty: Represents the empty set
• Node a: A set containing just the single element a
• Tree a left right: A set containing a plus all elements in left and right

Core Powerset Logic #

The recursive intuition for powersets is straightforward:

For any non-empty set S with an element x, the powerset of S is:

1. All subsets of S that don't include x (this is the powerset of S with x removed)
2. All subsets of S that do include x (this is every subset from step 1, with x added to it)

We then combine these two collections of subsets to get the full powerset.

Step 1: Helper Functions #

We'll need a few helper functions to make this work:

1. Insert an Element into a Set

First, a function to add an element to a set (we'll use this to build subsets with x):

insert :: Eq a => a -> Set a -> Set a
insert x Empty = Node x
insert x s@(Node y)
  | x == y    = s  -- Don't add duplicates (it's a set!)
  | otherwise = Tree x s Empty
insert x s@(Tree y left right)
  | x == y    = s
  | otherwise = Tree y (insert x left) right

This checks for duplicates (since sets can't have them) and inserts the element into the tree structure.

2. Union Two Sets

Next, a function to merge two sets—we'll use this to combine the two subsets collections from our core logic:

union :: Eq a => Set a -> Set a -> Set a
union s Empty = s
union Empty s = s
union s (Node x) = insert x s
union s (Tree x left right) = union (union (insert x s) left) right

This takes every element from the second set and inserts it into the first set.

3. Extract an Element and the Rest of the Set

We need a way to grab one element from a non-empty set, plus the set that's left when we remove that element:

extractOne :: Set a -> (a, Set a)
extractOne Empty = error "Can't extract from empty set"
extractOne (Node x) = (x, Empty)
extractOne (Tree x left right) = (x, union left right)

For a Tree, we take the root element and merge its left and right subtrees to get the remaining set.

4. Map a Function Over a Set

Finally, a function to apply a transformation to every element in a set—we'll use this to add x to every subset from the first part of our powerset logic:

mapSet :: (a -> b) -> Set a -> Set b
mapSet _ Empty = Empty
mapSet f (Node x) = Node (f x)
mapSet f (Tree x left right) = Tree (f x) (mapSet f left) (mapSet f right)

Step 2: The Powerset Function #

Now we can put it all together into the powerset function:

powerset :: Eq a => Set a -> Set (Set a)
powerset Empty = Node Empty  -- Powerset of empty set is {∅}
powerset s = 
  let (x, rest) = extractOne s
      subsetsWithoutX = powerset rest
      subsetsWithX = mapSet (insert x) subsetsWithoutX
  in union subsetsWithoutX subsetsWithX

How It Works #

Let's walk through a small example to see it in action:

• If we have s = Node 1, then:
  1. extractOne s gives (1, Empty)
  2. subsetsWithoutX = powerset Empty = Node Empty (this is {∅})
  3. subsetsWithX = mapSet (insert 1) (Node Empty) = Node (insert 1 Empty) = Node (Node 1) (this is {{1}})
  4. Unioning these gives a structure equivalent to {∅, {1}}—the correct powerset!

Notes #

• If your binary tree is supposed to be ordered (like a search tree), you can adjust the insert function to maintain order, but the core powerset logic stays the same.
• The Eq a constraint is needed to handle duplicates in insert—if you're sure your sets never have duplicates, you can remove it, but it's safe to keep for correctness.

内容的提问来源于stack exchange，提问作者hafhut