冪集合

2011-06-08にあったお題に挑戦。
まずはごくごく素直に。nobsunがなぜNatとか定義しているのか、よく分かっていません。

data Set = S [Set]

instance Show Set where
  show (S xs)
    | null xs = "0"
    | otherwise = "{" ++ drop 2 (concat [", " ++ show x | x <- xs]) ++ "}"

main :: IO ()
main = interact $ show . powerSet . read

powerSet :: Int -> Set
powerSet 0 = S []
powerSet n = S $ power xs where
  S xs = powerSet $ n-1

power :: [Set] -> [Set]
power [] = [S []]
power (x:xs) = [S z | S y <- power xs, z <- [y, x:y]]

ghci> powerSet 0
0
ghci> powerSet 1
{0}
ghci> powerSet 2
{0, {0}}
ghci> powerSet 3
{0, {0}, {{0}}, {0, {0}}}

いろいろな解があると面白そうだったので、あなごるにも出題しました。
anarchy golf - Power Set
プログラマのみなさん、ゴルファーも非ゴルファーもぜひぜひご参加を。