Monad TransformerのTutorialを発見．読みやすそうなので読んでみることに．簡単なインタープリータを徐々にmonadicにしていくとのことで，ErrorTによるエラー処理もあるようです． 半分くらい読んだ 2.2節まで読みました．読みやすい英語で中身も面白いです…

デバグ オペレータsubの定義が間違ってました． -- procExp i (Invoke "sub") = procStack i (\(x1:x2:xs) -> (x1-x2):xs) procExp i (Invoke "sub") = procStack i (\(x1:x2:xs) -> (x2-x1):xs) スタックの順番を間違えてました． 簡単な対話型シェル（REPL…

rollの実装 保留していたrollに戻ります． rollはn個の要素をk回だけ「上に」巡回させます．例えば， 10 20 30 40 50 3 1 roll => 10 20 50 30 40 10 20 30 40 50 3 2 roll => 10 20 40 50 30 10 20 30 40 50 3 3 roll => 10 20 30 40 50 という具合です．大…

算術オペレータの追加 普通に使われる演算で以下のものを追加します．PostScript Level 1のサブセットです． add : n1 n2 add => n1+n2 sub : n1 n2 sub => n1-n2 mul : n1 n2 mul => n1 x n2 idiv : n1 n2 idiv => d mod : n1 n2 mod => r (n1 = n2 x d +r …

Evaluator さらに，スタックも type Stack = [Stackable] から type Stack = [Stackable] data Stackable = Pushed Literal | Opname Word | Code AST deriving Show と変更します．つまり「新しいオペレータの名前」と「コードのブロック」もスタックに積め…

Parserの改造 新しいオペレータを定義する際に /a { 1 2 } def という構文を使って，これをパースして [NewWord "a" [Push 1 ,Push 2]] というASTを構築しました．これを評価すると Interp {stack = [], dict = fromList [("a",[Push 1,Push 2])]} という状…

評価器（Evaluator） ASTが作れるようになったので，評価器の番です．harrorth--では省いた「新しいオペレータの定義」があるので，その部分を作らないといけません．新しいオペレータは「名前」，「内容」そしてその間の「対応関係」であり，また定義したら…

Harrorthを適当にいじった結果なんとなく雰囲気が分かったので，好きなようにHarrothを真似て作ってみます． 文法を（いい加減に）考える forthの文法では，何かのコード片に名前をつけるのは :NAME <code>; とします．:（コロン）の後，;（セミコロン）の前の空白</code>…

始めに forthという言語があります．逆ポーランド記法（RPN）を使うちょっと見た目が変わった言語ですが，こっそりいろいろな形であちこちに使われています．例えば（商業的な）印刷には欠かせないAdobeのPostScriptの原型になってたりJavaのVMが似たような…

コラッツ問題でなんとか答えはでていますが，せっかくStateモナドを頑張ったので，それで書いてみます．StateモナドがMonadFixのインスタンスだとかは・・・スルーします． import Control.Monad.State import Data.List {- Project Euler Problem 14 e14-8.…

ここまではpairwise swapという具体的なもので考えてきたので，こんどは抽象的に攻めてみます．MonaFixのインスタンスのmfixには満たすべき性質があるのでした． -- purity mfix (return . h) = return (fix h) -- left shrinking (or tightening) mfix (\x …

前回はリストモナドでlistfixという関数をでっちあげてそれが期待した動作をすることを主張しました．実際コードを走らせて見れば動きます．今回はまずは，その動きを追いかけてみます． pairwise swapでリストモナドのmfixを追いかける 面倒なので，listfix…

後だしジャンケンかつ自分を納得させるためだけのような内容です(^^; 再帰的な束縛を模索する ここでは強引な議論を展開します．先走るとリストモナドのmfixのあの妙な定義を引っ張り出す「発見的手法」を無理やり延々と展開します．前回の考察の続き．pairw…

かなりfixを使ってみたので，そもそもの本題に向かいます． リストはMonad ひとまず，リストはモナドであることの定義は instance Monad [] where m >>= k = foldr ((++) . k) [] m m >> k = foldr ((++) . (\ _ -> k)) [] m return x = [x] fail _ = [] と…

decWithMin問題 まだ具体例にこだわります．もうfixから離れている気もしますが，まあ，再帰すなわちfixということで．さて，Otter_OさんのところのArrowの話題ArrowLoopとCircularPrograming - 取り急ぎブログですに関連して（私はArrowって何？の人です）…

しつこく再帰処理とfixに粘着します．果たして，mfixにたどり着くのか（苦笑）． repmin（A recursive do for Haskell, by Levent Erk\"ok, John Launchbury, Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvaniaより） 次のお題は「repmin」で…

具体例を頑張ってみます．fixに無名関数を与えるか，名前をつけるかは見やすくなる方を独断で決めて使うことにします． 条件を満たす値の和（プログラミングGauche，p.72より） リストの中から条件を満たす要素だけの和を求めてみます．普通なら条件を与える…

Control.Monad.FixとData.Functionにfixなる関数が定義されています． fix:(a->a)->a fix f = let x = f x in x 何か詐欺みたいな定義です．この定義から分かることは fixは関数fに対して，x=f xとなるx，つまりfの不動点（fixed point）を返す ということで…

ついでなのでStateモナドの定義を最後まで． MonadFixクラス StateモナドはMonadFixクラスのインスタンスでもあります．Stateモナドから離れて，MonadFixクラスを考えてみます．何なんでしょう，これ．Fixというからには何かを固定するはずです． class (Mon…

モナド則の確認 一個一個モナド則を確認してみます．Haskellの表記としては間違っているかもしれませんが，意味が通じるように書きます． -- return a >>= k == k a runState (return a) s = (a,s) runState (m >>= k) s = let (a, s') = runState m s in ru…

Stateモナドがモナドであることの定義は以下の通りです． -- Monadクラスとクラスメソッド class Monad m where (>>=) :: forall a b. m a -> (a -> m b) -> m b return :: a -> m a -- State sをMonadクラスのインスタンスにする instance Monad (State s) …

分からないときは定義をみるのはお約束．ということでControl.Monad.Stateをみます． module Control.Monad.State ( module Control.Monad.State.Lazy ) where import Control.Monad.State.Lazy はうっ・・別の呼んでますね．本体はControl.Monad.State.Lazy…

sampou.orgのhttp://www.sampou.org/cgi-bin/haskell.cgi?Memoiseをほとんど丸写しして，Stateモナドを使ってフィボナッチを書いてみました． import Control.Monad.State rfib :: Integer -> Integer rfib 0 = 0 rfib 1 = 1 rfib n = rfib (n-1) + rfib (n-…

Project Euler Problem 14に関連して，どうにもStateモナドがしっくりこない．キャッシュを持ちまわすため方法がすっきりしない．たぶんモナドの理解が甘いのであろう．とりあえずお約束のフィボナッチ数列からスタートでしょう．

コメント欄でご指摘いただいたことを考えてみます．素因数分解をする際に素数の列として，エラトステネスの篩ではなく， primes = 2:3:([6,12..] >>= (\x->[x-1,x+1] ) を使うというテクニック．6の倍数の「前後」を「素数のタネ」として使うということです…

昨日の虫食い算[id:dachs_hippo:20080315]をHaskellで書いてみました． {- mushikui.hs -} import List f::[Int]->[Int]->[[String]] f ns = concat . map (\y -> (map (\x->[show x, show y, show $ x*y ]) ns)) g::[Int]->[Int] -> [([String],String)] g …

sepBy1を使うことで「英語の文」を単語のリストに分解するパーサをsentenceを作ります． word:: Parser String word = many1 (letter <|> digit) sentence:: Parser [String] sentence = do words <- sepBy1 word separator oneOf ".?!" return words separa…

many/many1はパースしたものを返しますが，パースしたものを返さないskipMany/skipMany1というパーサコンビネータも用意されています． skipMany :: GenParser tok st a -> GenParser tok st () skipMany1 :: GenParser tok st a -> GenParser tok st () |ha…

「単語」をパースするパーサwordを考えてみます．ここで「単語」というのは一つ以上の「大文字・小文字のアルファベット」から構成されます． word:: Parser String word = do { c <- letter ; do { cs <- word; return (c:cs) ;} <|> return [c]; } do記法…

前に，ライブラリのソースコードの所在が分からないと書きました．たしかにGHCをインストールすると見当たらないのですが，GHCそのもののソースコードには入ってるのではなかろうかと思い至り（遅い(^^;;），GHC6.6.1のソースコードを入手，解凍してみました…