> さかいです。

> 今回の問題に特化するなら、not(le_a a c) || (le_b b d) は
> 順番を逆にしたほうが効率的ですよ。

いえこれは微妙で、チェックの回数は多いけど、le_a の方が le_b
よりコストが低いのです。試してみると、、、
酒井さんの方が速いですね。^^;


> それにしても、
> 3^126 = 1310020508637620352391208095712502073964245732475093456566329 個
> の関数のうち、いったいどれだけの関数が単調なんでしょうね。
> 少なくとも一千万個以上はありそう……

想像を絶しますねー。

> data Poset = forall a. Poset [a] (a -> a -> Bool)
> power :: Poset -> Poset -> Poset


これです!私も iterate を使えるような型を作ろうとしていたんですが、
どうしてもできなくて。forall というのがあるんだ!

と、いうことは Haskell で、逆極限法の一歩手前まで実現できるという
ことですね。一歩手前と後とどのぐらいのギャップがあるか知らないけど。


> ところで、これを原さんのRuby版と同様にコマンドライン引数を受け取るように
> 変更しようと思ったのですが、思うように書くことが出来ませんでした。
> コマンドライン引数を扱う際の定石みたいなものってあるのでしょうか?

以下、少しいじってみましたが、そんなにしっくりしているわけでもない。
定石があるなら私も知りたいです。


import System

data Poset = forall a. Poset [a] (a -> a -> Bool)

power :: Poset -> Poset -> Poset
power (Poset bx le_b) (Poset ax le_a) = Poset set le where
    set = foldr extend [[]] ax
    extend a funcs = [(a,b):func | func <- funcs, b <- bx, check a b func]
    check a b func = and [(le_b b d) || not(le_a a c) | (c, d) <- func ]
    le f1 f2 = and [le_b b d | ((_, b), (_, d)) <- zip f1 f2]

showGraph :: Poset -> String
showGraph x = "digraph G {\nrankdir=TB;\n" ++ pointshow x ++ graphshow x ++ "}"
    where 
    printGraph x = putStrLn ("digraph G {\nrankdir=TB;\n" ++
                     pointshow x ++ graphshow x ++ "}")
    pointshow (Poset v _) = concat ["x" ++ show i ++ ";\n" |
                              (_, i) <- zip v [0..]]
    graphshow (Poset u le) = concat ["x"++show i++" -> "++"x"++show j++";\n"
                           | ((_, i), (_, j)) <- graph le (zip u [0..])]
    graph le ui = [(fi, gj) | fi <- ui, gj <- foldr (extend_graph le fi) [] ui]
    extend_graph le (f, i) (g, j) fs
      | i == j = fs
      | (or [le g h | (h, _) <- fs]) = fs
      | (le g f) = (filter (\(h, _) -> not (le h g)) fs) ++ [(g, j)]
      | True = fs

main :: IO ()

main =
    do n:o:_ <- mfunct (map read . update ["3", "2"]) getArgs
       putStrLn (showGraph ((chain o) !! n))
    where update (d:ds) (a:as) = a : update ds as
          update [] as = as
          update ds [] = ds
          mfunct f = (>>= return.f)
          chain o = iterate (power omega) (Poset [0::Int] (<=))
              where omega = Poset (take (o+1) [(0::Int) ..]) (<=)


ところで 0::Int の ::Int ってどういう意味ですか?


--
ML: haskell-jp / quickml.com
使い方: http://QuickML.com/