状態をモナドで実現する方法を考えます。 リスト 例は簡単な方がいいので、データ構造として Lisp 風のリストを定義しましょう。 data List a = Nil | Cons a (List a) deriving Show リストは、こんな風に表せます。 Cons "c" (Cons "b" (Cons "a" Nil)) Lisp 風の cons も定義してみましょう。 cons :: a -> List a -> List a cons x xs = Cons x xs cons "c" $ cons "b" $ cons "a" Nil → Cons "c" (Cons "b" (Cons "a" Nil)) 状態を持つリスト さて、この Lisp 風のリストに、要素の数を覚えさせておきたいとしましょう。もちろん、数えれば分りますが、数えなくても一瞬で分るようにしたいのです。
なるほどなと思った A Neighborhood of Infinity: MSFP 2008 より HaskellでのListデータ型の定義 data List A = Nil | Cons A (List A) 各項を以下の数式記号に、置き換える List A => L(A) a | b => a + b Nil => 1 Cons A b => A × b L(A) = 1 + A × L(A)L(A)を左辺へまとめる (1 - A) × L(A) = 1係数で割る L(A) = 1 / (1 - A)テイラー展開する テイラー展開 - Wikipediaの幾何級数 L(A) = 1 + A + A^2 + A^3 + ...各項は、 A = A × 1 A^2 = A × A × 1 A^3 = A × A × A × 1 L(A) = 1 + A × 1 + A × A × 1
ふと思い立って Haskell で brainfuck を書いてみた。そんな事やってる人は沢山いると思うので、一つ制限をつけた。モナドは main 関数の中だけしか使わない。つまり、後は全部副作用なしでやる。 それから、大体の方針を立てた。brainfuck の文法はとても単純なので、もしかしてパーサすらいらないんじゃ無いかと思ったのだけど、ループがある関係上やっぱり最初に構文木を作ったほうがやりやすい。という事でオーソドックスに、ソースコード -> 構文木 -> 実行、と言う順序で進める事にした。 -- Parser data Command = Inc | Dec | Next | Prev | Put | Get | While [Command] deriving (Show, Eq) type Program = [Command] parse :: String -> Prog
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く