Haskell の乗算は高速フーリエ変換を使ってると聞きました。 軽く確かめてみたら、だいたい O(n * log n) なので、多分そうなんだと思います。 でも、それを明示したドキュメントを見つけられず‥。 それにしても、よく作りこまれてるなぁ。 Prelude> signum …

JAVA５．０でGO!! | プログラミングに自信があるやつこい！！ １０分でコーディング | プログラミングに自信があるやつこい！！ via なんかしらんけど配る - * *scrap* こういうのを Haskell で書くのはヒキョウだと思いつつ、書いてみたい誘惑に勝てません…

諸般の事情により、相変わらずフィボナッチ数と格闘中です。何人かの方が既に書かれていますが、フィボナッチ数を高速に計算する方法があります。 細かいバリエーションはありますが、以下のような漸化式を利用します。 F2n-1 = Fn-12 + Fn2 F2n = 2Fn-1Fn +…

All About Monads まだ第 I 部しか読んでいませんが、すごく、分かりやすいです。

なんで SKK = I なんだっけと考えていて、SKKx = Kx(Kx) = x で (Kx) は無視されるから、二つ目の K は他のコンビネータ（例えば S）でもいいよなと思ったわけです。 s x y z = x z (y z) k x y = x というように、Haskellで定義して実行すると、上手くいき…

同じ問題で悩んでました。 monomorphism restriction - bonotakeの日記 Monomorphism restriction - HaskellWiki まだ分からないのが、単相性制約の存在意義です。 自分は「型宣言をしっかり書こう派」なので実用上の問題はありません。ただ、↓のようなコー…

前回のエントリに対して、m-hiyama さんから、色々と指摘をいただきました。 以下に訂正を、と思ったら、先に bonotake さんに書かれてしまった。 そもそも問題はというと、「ラムダ抽象＝カリー化」という前提を僕が理解していなかったのが、いけなかったの…

という訳で、書き直しました。 Haskell による Grass のインタプリタです。Grass コードのファイル名を与えて実行します。 必要な仕様は、全て満たしているはず。全角文字（UTF-8、Shift_JIS）も受け付けます。 バグ報告は随時お願いします。 Grass 人口が少…

Haskell で Grass のインタプリタを書いてみました。以前から書いてみたいとは思っていたのですが、どこから手をつければいいものやら分からず、半年近く経ってしまいました。悲願達成。 Haskell 版は既に mr_konn さんが書いているので、目新しいものではあ…

id:mzp さんに触発されて、Arrow 勉強中。 Haskell/Understanding arrows - Wikibooks, open books for an open worldの図が分かりやすいです。まずは簡単なサンプルで動作を確認。 -- オリジナル f1 as = tail as ++ init as -- 引数を２つの経路に分けて、…

http://projecteuler.net/index.php?section=problems&id=113 各桁の数字が昇順または降順に並ぶ数が10100未満でいくつあるか求める。 重複順列です。 main = print $ euler113 100 euler113 :: Integer -> Integer euler113 n = sum $ map nonBouncy [1..n]…

cut-sea さんが書いている グローバル変数が欲しい理由？ について自分なりの見解を。 もとは Haskell でグローバル変数が欲しい理由 - あどけない話 の記事です。 Haskell でグローバル変数を持ちまわす必要があるかどうかは、ひとえに関数の設計にかかって…

http://projecteuler.net/index.php?section=problems&id=112 すべての数字が昇順または降順に並んでいる数を考える。2 桁以下の数はすべてそうだが、桁が増えるとその割合は減っていく。そのような数の割合がちょうど 1% になるのはいくつのときか求める。 …

http://projecteuler.net/index.php?section=problems&id=111 1 を 3 つ含むような 4 桁の素数は以下のように 9 個ある。 1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111 n 桁の素数で、数字 d が最も多く含まれるような数の和を S(n, d) とおくとき…

id:matarillo さんが、ここ とか ここ で書いている問題を解いてみました。 基本的には枝刈りありの全数探索。 c から c' までノードを一つ一つ辿りながら、a から a' までのルートと、b から b' までのルートが残っているかを都度確かめていきます。どちら…

http://projecteuler.net/index.php?section=problems&id=109 ダーツで、100 未満の得点でチェックアウトできる場合の数を求める。3 投以下で、最後は Double で終わらないといけない。1 投目と 2 投目は入れ替わっても同じとみなす。 1 投目と 2 投目が同じ…

引き続きモナドと格闘中。できるようになったこと。 STArray や IOArray を動かせるようになった。 Disjoint Set が実装できた。→ 9400 分（ 6 日と 12 時間 40 分）かかっていたコードが 1 分で返ってくるようになった。ちなみに STArray で 1 分、STUArray…

以前に、なぜ Haskell の if は関数じゃないの？という疑問を持ったことがあるのですが、そもそもなぜそう思ったかというと、↓のようなコードをポイントフリースタイルにできないからなのです。 ほら、意味もなくワンライナーで書きたいときってあるじゃない…

最近 IO 周りが騒がしいので、鋭意モナドを勉強中です。 個人的に do 記法に馴染めないので、ここを見て脱糖を試みているのですが、どうも上手く動きません。 もともとはこんなコード。 関数 changed の中で、配列の読み込みをした後に書き込みをしています…

１０８問目と同じ。

1/x + 1/y = 1/n を満たす x, y の組を考える。n = 4 のとき、解は (x, y) = (5, 20), (6, 12), (8, 8) の 3 組であるが、解の個数が初めて 1,000 を超えるのは n がいくつのときか。 ずいぶん前に解いたので、自分で書いたコードが読めなくなっていて、改め…

「最小全域木」を求める問題、だそうです。グラフ問題に疎い自分は超俺流アルゴリズムで実装したため、UPする気にならず、放ったらかしてました。 jeneshiccさんの方法が簡単そうなのだけど、fglパッケージを入れていないので、まずは自分で書くことに。 ど…

チャーチ数の演算をコンビネータで表すと (^) はλabcd.bacd = λab.ba = CI（引数の順序を気にしないなら I ） (*) はλabcd.a(bc)d = λabc.a(bc) = B (+) はλabcd.ac(bcd) = λabcd.B(ac)(bc)d = λabc.(BBac)(bc) = λabc.S(BBa)bc = λa.BS(BB)a = BS(BB) (+) …

よくあるクイックソートのプログラムを List モジュールの sort 関数（マージソート）と比べてみました。 import Data.Ratio quickSort :: Ord a => [a] -> [a] quickSort [] = [] quickSort (l:ls) = quickSort (filter (< l) ls) ++ [l] ++ quickSort (fil…

会社に落ちてたので、有難く頂戴いたしました。 ラムダ計算とかパターンマッチとか多相型チェックとか SK コンビネータとか遅延評価とか、どっかで見たような話題が並んでるなと思ったら、作者の Simon Peyton Jones って Haskell 界の大御所でした。 うわぁ…

最近、計算可能性とか不完全性定理とかについて勉強しています。その中でグッドスタイン数列というのが出てきて、これを Haskell で書いてみようと思いました。 遺伝的記述をリストで表現しようとしていて、値と遺伝的記述を変換する関数を書きたいのですが…

以前に出られなかった勉強会の資料を見てたら、flip id は flip ($) と同じと書いてありました。たしかに id :: a -> a で ($) :: (a -> b) -> (a -> b) だから、id の a を関数 a -> b と見れば、同じだ。 ということは main = print $ (+3) $ (*2) $ 1 こ…

utf8-string モジュールをインストールしました。 物は HackageDB: utf8-string-0.3.1.1 で入手。 インストールの仕方がどこかに載ってたなと探し回って どう書く？org 3513 nobsun - 投稿の詳細 で発見。 $ runhaskell Setup.lhs configure $ runhaskell Se…

そもそもなぜ utf8-string モジュールを入れたかというと、こんなの が出てきたからです。 すごい、Hello, world! も v も動いてる！しかも 100 行で書けるんだ。 IO 周りがよく分かっていないので勉強して、自分でも書けるようになりたい。 しばらくは勉強…

http://projecteuler.net/index.php?section=problems&id=104 最初の 9 桁にも最後の 9 桁にも 1 から 9 の数字が 1 回ずつ現れるようなフィボナッチ数で、最小のものを求める。 最初の 9 桁と最後の 9 桁だけ抜き出して計算しています。ただし最初の 9 桁を…