鳥たちと戯れる
To Mock a Mockingbird を読んでいます。言わずと知れたコンビネータ論理の教科書（？）です。
そこで算術や論理を関数で表すという、ラムダ計算でよくある話が登場するのですが、自然数の定義が一般的なチャーチ数と違っていて分かりにくかったので、検算用のコードを書きました。
ふつうのチャーチ数では、zero f x = x = KIfx、one f x = f x = Ifx、two f x = f (f x) = SBIfx と定義しますが、zero = I、one = V(KI)I、two = V(KI)(V(KI)I) という定義になってます。
こんな感じ（↓）で遊べます。
Main> toInt $ exp five (multi three two) 15625 Main> toBool $ greater (multi two five) (multi three three) True Main> toInt $ concat (multi three four) three 123
コンビネータの本なので、下にあげた plus とか greater みたいな再帰関数をコンビネータで（ポイントフリーで）書く方法なんかも載っていて、勉強するにはとてもいい本だと思います。お薦め。
ちょっと確認する程度ならこんなコードで十分だけど、unsafeCoerceも鬱陶しいし、やはりここはちゃんとした処理系の実装に挑戦しようかな。
import Prelude hiding (succ,pred,exp,even,not,and,or,length,concat) import Unsafe.Coerce u = unsafeCoerce -- 事前準備 各種コンビネータ i x = x k x y = x t x y = y x l x y = x (y (u y)) b x y z = x (y z) c x y z = x z y v x y z = z x y r x y z = y z x s x y z = x z (y (u z)) -- 論理 true = k false = k i not = v false true and = r false or = t true imply = r true equiv = c s not -- 算術 zero = i succ = v false one = succ zero two = succ one three = succ two four = succ three five = succ four ten = multi two five pred = t false isZero = t true -- 各種関数 plus m n = isZero m n $ plus (pred $ u m) (succ $ u n) multi m n = isZero m zero $ plus n (multi (pred $ u m) n) exp m n = isZero n one $ multi m (u exp m (pred $ u n)) even n = isZero n true $ not $ u even $ pred $ u n greater m n = isZero m false $ isZero n true $ greater (pred $ u m) (pred $ u n) length n = a1 zero n where a1 l n = a l n (u l) $ u a1 (succ l) n a l n = greater (exp ten l) n concat m n = plus (multi m (exp ten (length $ u n))) n -- 表示・デバッグ用関数 toBool b = b True False :: Bool toInt n = isZero n 0 $ (+) 1 $ toInt $ pred $ u n :: Int
- 作者: Professor of Philosophy Raymond M Smullyan
- 出版社/メーカー: Oxford University Press
- 発売日: 2000/11/30
- メディア: ペーパーバック
- 購入: 3人 クリック: 23回
- この商品を含むブログ (8件) を見る
BFS
「人材獲得作戦・４ 試験問題ほか」を解こうとしている（続・未完） - IKB: 雑記帖 について、コメント欄に書こうと思ったのですが、長くなったのでこちらに。
この場合、遅延評価云々はあまり関係なくて、元エントリのコードでも解が一つ見つかった時点ですぐに返ってきます。
ただこの迷路は自由度が大きいので、やはり既訪の場所を除外しないと何度も同じところを通ってしまいます。
例えば A : 1→2→3→4、B : 1→2→5→3 というような順序で探索する（2 のノードで分岐する）とき B の方では 3 のノードが既訪だということが分からないので、再探索してしまいます。
これを除外するためには探索の分岐に関わらず既訪のノードを記憶しておく必要があって、以下のコードでは solve の引数を追加しています。
その他、細かいところをちょこちょこいじってますが、ご参考まで。（Maybe にしたら mplus の意味がなくなってしまった）
import Control.Monad type Position = (Int, Int) type Board = [String] type State = (Position, Board) main :: IO () main = do input <- fmap lines getContents let answer = solve [] $ next (startOf input, input) putStrLn $ maybe "no route found" unlines answer startOf :: Board -> Position startOf input = head [(x,y) | (y,cs) <- zip [0..] input, (x,c) <- zip [0..] cs, c=='S'] solve :: [Position] -> [State] -> Maybe Board solve _ [] = mzero solve vs ((p@(x,y), b) : queue) | symbol=='G' = return b `mplus` solve vs queue | symbol==' ' && notElem p vs = solve (p:vs) $ queue ++ next (p, b) | otherwise = solve vs queue where symbol = b!!y!!x next :: State -> [State] next ((x,y), b) = zip [(x,y-1), (x,y+1), (x-1,y), (x+1,y)] $ repeat b' where b' = putAt y (putAt x '$' $ b!!y) b putAt n v vs = take n vs ++ v : drop (n+1) vs
リストも関数も同じもの
注：この文章は Haskell 布教のため、 Haskell を知らない人向けに書いています。なので、ちょっとでも分かりにくいところはどんどん指摘してください。
しばらく前に、hasekll-jp のメーリングリストで Haskell の型クラスの体系が話題になっていたのですが、そこで衝撃を受けたメールがありました。
http://www.sampou.org/cgi-bin/w3ml.cgi/haskell-jp/msg/463
何に驚いたのかを以下に説明したいと思います。
リストと要素の変更
Haskell にはリストというデータ構造があります。他の言語と同じように特定の種類の要素を複数格納していて、インデックスを指定すると要素を取り出すことができます。
list = [1,5,7,6,2,8,3,0,9,4] -- 0から1までの整数を格納したリスト val = list !! 3 -- インデックスを指定して中身を取り出す（この場合は 6 が返る）
また map という関数があって、リストの要素をまとめて変更をすることができます。Ruby なんかにもありますね。
f x = x + 5 -- 引数に 5 を足す関数 f を定義 list' = map f list -- list の要素それぞれに 5 を足す val' = list' !! 3 -- 今度は 6 + 5 = 11 が返る
関数と関数の結合
今度は違った例を考えて、引数を 2 倍する関数を定義してみます。
func x = x * 2 -- 引数を 2 倍する関数 func を定義 res = func 3 -- func の引数に 3 を渡す（3 * 2 = 6 が返る）
また Haskell には、複数の関数をつなげて順番に適用する（結合する）関数 (.) があります。
func' = (.) f func -- func してから f する（2 倍してから 5 を足す） res = func' 3 -- 3 * 2 + 5 = 11 が返る
Functor と fmap
これまでリストの要素の変更と関数の結合という異なる操作を挙げましたが、実は fmap という関数を使うと、これらは同じように書くことができます。
import Control.Monad.Instances list' = fmap f list -- fmap を使って、list の要素を f で変更する val' = list' !! 3 -- これも 11 が返る func' = fmap f func -- fmap を使って、f と func を結合する res' = func' 3 -- これも 11 が返る
つまり、リストも関数も同じように扱うことができるのです。
なぜこんなことができるかを考えてみます。以下の図のように捉えると、リストも関数も値を格納した箱（コンテナ）であり、インデックスを指定したり引数を与えたりすることで、値を取り出すことができるのだとみなすことができます。
このように何らかの値を格納したコンテナのことを、Haskell では Functor クラスと定義しています。Haskell のクラスは Java や C# でのインタフェースに相当し、必要なメソッド（この場合は fmap）を定義することで、そのクラスのインスタンスとして扱うことができます。
さらに fmap はコンテナの構造を変えずに値を変更する操作だと言えます。僕は関数が Functor クラスとして定義できることを知識としては知っていましたが、関数結合の (.) が fmap で置き換えられることには気づいておらず、とても驚いたのです。
Functor のような型クラスは Applicative、Arrow、モナド など色々あります。実際、モナドは Functor の制約を厳しくしたサブクラスであり、リストに対応するリストモナド、関数に対応する Reader モナドといったインスタンスがあります。
このような抽象化ができると、使う側もこれまでと違った新しい見方ができるようになります。リストと関数を同じように扱える言語なんて、そうそうありません。そこが Haskell の大きな魅力の一つだと思っています。
参考文献：
素因数分解
inamori さんが Project Euler の解説記事で素因数分解について触れているのですが、そこで「あまりHaskellっぽくない」と書いてあるのが、気になってしまいました。
Haskell っぽいコードってどんなだろう、やっぱり自前で再帰せずに高階関数を使うのかな、そうするとこの場合は unfoldr だよな。とか考えながら書いたのが下のコード。
n の平方根以上の数では割らないようにするのがちょっと面倒でした。もっとすっきりした書き方があるでしょうか。
ちなみに、2以上のすべての数を素因数の候補にしていますが、もちろん 2と奇数だけでも、きちんとした素数列にしてもいいと思います。（性能差を確認できませんでした）
import Data.List main = print $ last $ factors 600851475143 factors :: Integer -> [Integer] factors n = unfoldr phi (n, takeWhile (\p -> p * p < n) [2..]) phi (1, _ ) = Nothing phi (n, ps) = case dropWhile (\p -> mod n p > 0) ps of [] -> Just (n, (1, [])) ps'@(p:_) -> Just (p, (div n p, ps'))
詳細設計書
ネタ元：詳しすぎる詳細設計書 - SiroKuro Page
自分だったらこんな風に書きたかったりするので、やっぱりまだ詳細設計書が邪魔だと思いました。:p
あ、詳細設計書なんて要らんだろ、という話には激しく同意です。
import Control.Arrow import Data.List data Sex = Man | Woman deriving (Eq, Show) type Height = Double data Person = P {sex :: Sex, height :: Height} main = print $ calc [P Man 50, P Woman 40, P Woman 50, P Man 70, P Man 90] calc :: [Person] -> Height calc = uncurry (-) . (avg *** avg) . partition ((== Man) . sex) avg :: [Person] -> Height avg = uncurry (/) . (sum . map height &&& toEnum . length)
if を追放する
Kコンビネータと真偽値に関する話題が挙がっていたので、それを使って何か書いてみようと思いました。
条件分岐と言えば FizzBuzz。以下のようなプログラムを考えます。
main = mapM putStrLn [ max (show n) $ fizz n ++ buzz n | n <- [1..100] ] fizz n = if mon n 3 == 0 then "Fizz" else "" buzz n = if mon n 5 == 0 then "Buzz" else ""
まずは以下のように if' を定義しますが、これだけだとまだあまり変わっていません。
Haskell 標準の Bool 型を使っているし、パターンマッチで結局 if 相当のことをやっているからです。（ポイントフリーで書けない！！）
fizz n = if' (mod n 3 == 0) "Fizz" "" buzz n = if' (mod n 5 == 0) "Buzz" "" if' True = const if' False = const id
なので、数値型から直接条件分岐することを考えます。リストを使ってこんな感じ。
fizz n = if' (mod n 3) "Fizz" "" buzz n = if' (mod n 5) "Buzz" "" if' b = foldr id const $ take b [flip]
foldl を使えば、False = flip const ではなく False = const id で定義することもできますが、型推論が上手くいかないので流行りの Unsafe.Coerce が必要になります。
import Unsafe.Coerce if' b = foldl (unsafeCoerce id) const $ take b [id]
一般的には 0 が False、0 以外が True かな。そうすると↓のような感じ。
fizz n = if' (mod n 3) "" "Fizz" buzz n = if' (mod n 5) "" "Buzz" if' b = foldr id (flip const) $ take b [flip]
うん、とりあえず if や case が無くてもプログラムは組めそう。
ちなみに if-then-else という糖衣構文をやめて、Prelude に if' 関数を追加しようということを主張しているページはこちら。
http://www.haskell.org/haskellwiki/If-then-else
速い素数の求め方
ちょっと前に haskell-cafe で速い素数の求め方が話題になっていました。
どんなもんだか確認した結果を記録。
僕がよく使ってたコードはこんな感じ。改めて見るとツッコミどころ満載です。
106 番目の素数を求めるのに手元のマシンで 2 分以上かかります。
primes0 = 2 : filter isPrime0 [3..] isPrime0 x = all ((/=0).mod x) $ takeWhile (<= (floor$sqrt$fromIntegral x)) primes0
というあたりを修正したのが↓のコード。1 分 20 秒。
primes1 = 2 : 3 : filter isPrime1 [5,7..] isPrime1 x = all ((/=0).rem x) $ takeWhile (\y -> y*y<=x) primes1
偶数だけでなく 3 の倍数もチェック対象から外したら、というのはよく話題になりますが、あまり速くなりません。たぶんそういう数列（内包表記の部分）を生成するのにコストがかかるのでしょう。1 分 20 秒。
primes2 = 2 : 3 : 5 : filter isPrime [ 6*i+j | i<-[1..], j<-[1,5] ] where isPrime x = all ((/=0).rem x) $ takeWhile (\y -> y*y<=x) $ drop 2 primes2
という訳で、アルゴリズムを考え直します。
32 未満の数が素数かどうかをチェックするには、2 で割り切れるかどうかを調べれば十分です。
同様に 52 未満の数が素数かどうかをチェックするには、2, 3 で割り切れるかどうかを調べれば十分です。（5 以上の素数で割ってみる必要はありません）
つまり n 番目の素数の二乗未満までは、最初の素数 n-1 個で割り切れるかを調べればよいわけです。
これを愚直に実装したのが以下のコード。特に何も効率化していませんが、50 秒くらいで終わります。
（以前のコードと同じようなフィルタリングですが、判定の回数が減っています）
primes3 = 2 : sieve 0 [3..] where sieve i xs = filter isPrime as ++ sieve (i+1) bs where (ps,p:_) = splitAt i primes3 (as,bs) = span (<p*p) xs isPrime x = all ((/=0).rem x) ps
さらに偶数をチェック対象から除くと、40 秒くらいに縮みます。
primes4 = 2 : sieve 0 [3,5..] where sieve i xs = filter isPrime as ++ sieve (i+1) bs where (ps,p:_) = splitAt i primes4 (as,bs) = span (<p*p) xs isPrime x = all ((/=0).rem x) ps
関数 sieve の引数にリストを渡すよりは、数を渡して内部でリストを生成するほうが、速くなります。
Haskell Wiki に素数についてのページがありますが、その IV 番目に相当します。
30 秒。今のところ、これが最終形です。
ちなみに 32bit で収まるなら、primes5 :: [Int] と明示的に宣言した方が速くて 20 秒で終わります。（コンパイル時に Unbox 化されるらしい）
primes5 = 2 : primes' where primes' = 3 : sieve 0 5 sieve i x = filter isPrime [x,x+2..p*p-2] ++ sieve (i+1) (p*p+2) where (ps,p:_) = splitAt i primes' isPrime x = all ((/=0).rem x) ps
おまけ。Haskell らしさを追及して高階関数で書くと以下のようになります。
人によってはこの方が分かりやすいかもしれません。
primes6 :: [Int] primes6 = 2 : primes' where primes' = 3 : (concat $ snd $ mapAccumL sieve 5 [0..]) sieve x i = (p*p+2, filter isPrime [x,x+2..p*p-2]) where (ps,p:_) = splitAt i primes' isPrime x = all ((/=0).rem x) ps
もっと速い求め方があれば、ぜひぜひコメントを。
