前回はリストモナドで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」で…
寝ようと思ったけども・・・・結城さんのところで続編のアナウンスがあって,しかもFermatだとあったので,中身の予想をしてました(主に通勤の電車にて(笑)).けど,勝手に書いていいものかと思ってたのですが,結城さん本人がネタばらし的なエントリを…
具体例を頑張ってみます.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モナドがしっくりこない.キャッシュを持ちまわすため方法がすっきりしない.たぶんモナドの理解が甘いのであろう.とりあえずお約束のフィボナッチ数列からスタートでしょう.
なぜスタックがあふれるのか.答えは自明で何でも溜め込むからなんですよね.1000000までの各整数に対してコラッツ列の長さを求めて,最大のものを求めると1000000個の要素のリストを扱わないといけないのは当たり前で,当然あふれても仕方がないです.キャ…
わからない・・・どうやっても1000000で処理すると *** Exception: stack overflow がでるか,異常な時間がかかってやってられない・・・むむーー.前のコード {- Project Euler Problem 14 e14.hs -} collatz::Integer -> [Integer] collatz n | n == 1 = […
The following iterative sequence is defined for the set of positive integers:n n/2 (n is even) n 3n + 1 (n is odd)Using the rule above and starting with 13, we generate the following sequence: 13 40 20 10 5 16 8 4 2 1It can be seen that th…
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 7432498619952474105947423330951305812372661730962…
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...Let us list the factors o…
In the grid below, four numbers along a diagonal line have been marked in red.08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88…
レポジトリが応答しない なぜかレポジトリが落ちててemacsが入りませんでしたが,これはレポジトリを変えればOKでした.http://www.ubuntulinux.jp/switch-archive-mirror を参照. 「マウスのホイール(wheel)が動かない」「マウスがシームレスに動かない」…
ポスタンブル ヘッダ ポスタンブルの先頭です. post p[4] num[4] den[4] mag[4] l[4] u[4] s[2] t[2]post(248)から始まる,4+4+4+4+4+4+2+2=29バイトです. p (4バイト):最後のページのbopの位置(開始位置) num:プリアンブルと同じ den:プリアンブルと…
TeXが生成するdviファイルは当然バイナリですが,実際は普通にテキストにしたって問題ないようなもの,つまり機械語とかになってるわけでもなく,要は中間コード,仮想コードのようなものです.実際,dvioutの大島先生が,dviファイルの可視化やページ独立性…
ちょっと必要があって,dviファイルのページをdviファイルから引き出すスクリプトを書きました.紛失防止の意味も込めて超いいかげんなものを晒します. ノンブルは一貫している(つまり,途中でリセットとかされない)のが大前提です. use strict; use war…
やっぱりお馬鹿してたわけで,pushを使えば十分な速さでした. use strict; use warnings; use Time::HiRes qw/gettimeofday tv_interval/; my $x=primefactory2(); my $sum; my $start = [gettimeofday]; while (1){ my $p=$x->(); last if $p>2000000; $su…
素数関係なので着手. The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.Find the sum of all the primes below two million. 訳 10未満の素数の和は2 + 3 + 5 + 7 = 17.2,000,000未満のすべての素数の和を求めよ. [Haskell] 前に考えたものをそのま…
A Pythagorean triplet is a set of three natural numbers, [tex:$a 訳 ピタゴラス数とは自然数の三つ組で[tex:$a [Haskell] {- Project Euler Problem 9 e9.hs -} line:: Int -> [(Int,Int)] line k = [(i,k-i) | i<-[0..k], i*k == 500, i>k-i ] lattice:…
「mod 6で1か5」を探索する方法でいってみます. use Benchmark; $x=primefactory2(); $count=5000; timethese($count, {'p1' => '$x->();', } ); sub next_cand{ $_[0] + 2 * ($_[0] % 6 ==5) + 4*($_[0] % 6 ==1); } sub primefactory2{ my @primes=(2,3,5…
キーボードが小さくなって誤入力倍増キャンペーン開催中. ##単純なエラトステネスの篩 use Benchmark; $x=primefactory1(); $count=5000; $i=0; timethese($count, {'p1' => '$x->();', } ); sub primefactory1{ my @primes=(2,3); my $state=-1; return su…
素数を列挙するは最適化の罠にはまったようです.ただいま原因の探求中(正しくは「自分の納得させる」作業中). すくなくとも「探索範囲を縮小するための処理のコスト」が「縮小による効果」を大幅に上回ったのは間違いないでしょう(grepは遅いということ…