1

将Data.Set.Monad与{-# LANGUAGE MonadComprehensions}one 一起使用时，几乎可以像我们在高中时那样定义集合，我们使用诸如{x ∈ S | φ(x)}. 例如：

s' = [x | x <- s, phi(x)]

使用更广泛使用的模块这是不可能的，因为它的类型构造函数不是 monad。Data.SetSet

最近在拼凑一个玩具示例时，我需要 powersetPowerset(S) = {x | x ⊆ S}问题是这个定义没有使用“生成器” x <- Y ，这在集合论中不是问题，但在 monad 理解中是必需的：

powerset s = [ x | x `isSubsetOf` s ]

只是不编译（error: Variable not in scope: x）

可以将集合转换为列表，获取其所有子列表的列表，将此列表转换回集合，然后也将其所有元素转换为集合powerset = (map fromList) . fromList. subsequences . toList：但这感觉就像一个丑陋的黑客

{-# LANGUAGE MonadComprehensions #-} 
import Prelude hiding (map)
import Data.List hiding (map)
import Data.Set.Monad 

powerset :: Ord a => Set a -> Set (Set a)
powerset =  (map fromList) . fromList. subsequences . toList

oneToTen = fromList [1..10]
smallEvens = [x | x <- oneToTen, even x, x < 6] -- just like in high school!

statement = smallEvens `member` powerset oneToTen

main :: IO()
main = putStrLn $ if statement == True  then "yes" else "no"

...将按预期编译并打印“是”。

有没有人有更优雅的解决方案？

4

1 回答 1

1

这是一个利用 monad 理解的简单递归解决方案：

powerset :: Ord a => Set a -> Set (Set a)
powerset s = insert s [x | elem <- s, let rest = delete elem s, x <- powerset rest]
于 2020-06-07T11:31:19.253 回答