Hatena::ブログ(Diary)

Life Goes On このページをアンテナに追加 RSSフィード

2011-06-11

[] 冪集合

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

プログラマのみなさん、ゴルファーも非ゴルファーもぜひぜひご参加を。

nobsunnobsun 2011/06/11 21:08 R(n)とR(n+1)を別の型として解釈したかったのでした。で、依存型っぽくしようとして。。。

notogawanotogawa 2011/06/12 00:05 ゴルフ的にも結構キレイでおいしゅうございます.

rst76rst76 2011/06/12 07:02 > nobsun
> R(n)とR(n+1)を別の型として解釈
なるほど。nobsunの2番目のやつとはだいぶ近いだろうと思ってるのですが、こっちはPretty Printerの解読に時間がかかりそうです。

> notogawa
134Bまで行きましたか。140B切るのは確認していて、さっき135Bまでは縮めたのですが、またあと1B。。。orz

nobsunnobsun 2011/06/12 16:21 2つめのは要素がListのListということなのでrst76さんのSetとたぶん同型。
pprは"," "{" 、"}" に対応するためのもので関数適用をぷりてぃぷりんとする
ときの括弧のあつかいと同じ構造

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rst76/20110611/1307787216