http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051024#p04 の正しさについてしばし考えた。リストの各要素について[0,1]区間の一様乱数を振って、その値でsortしていると理解してみた。もっと単純な解釈はないだろうか。 追記 これを実装し…

先日のアルゴリズムは逆向きにしたほうがわかりやすいと思う。Haskellで(効率を無視して)書くと、こういうこと。Arrayを使用する場合はselectOneに代えてswapにしたりすればO(N)にできる。 module Shuffle where import System.Random listShuffle :: StdGen…

http://d.hatena.ne.jp/yts/20051022#p1 で言及されたアルゴリズムを実装してみる。 {-# OPTIONS -fglasgow-exts #-} module Shuffle where import Control.Monad.Fix (fix) import System.Random import Control.Monad.ST import Data.Array.MArray import …

「与えられたリストの連続する部分列の内、和が最大となるものを求め、その和を返せ」というプログラムを書け http://d.hatena.ne.jp/yokoyamatetsuo/20050224/p2 solve = maximum . candidates . preproc preproc = map sum . groupBy (((>= 0).) . (*)) . …

普通に str = x ++ show x where x = "str = x ++ show x where "変数xを使わずに str = (flip (++) . show . take 39) str "str = (flip (++) . show . take 39) str "右辺に変数を使わずに str = fix $ (. show . take 40) . (++) $ "str = fix $ (. show …

main=putStr$x++show(' ':x);x="main=putStr$x++show(' ':x);x="「大きくなる」の解釈はバイト数。

CPS, Continuation Monad, and Writer Monad の例。 part :: (a -> Bool) -> [a] -> [a] part p l = let f [] z = z f (x:xs) z = if p x then x : f xs z else f xs (z++[x]) in f l []をいろいろに書いてみる*1。 *1:[id:yokoyamatetsuo:20050219#p5]より

接頭辞 prop_ には何の意味もない。適当な名前 (i_want_to_check x = ... ) でもよい。ただし、引数が最低一つは必要で、かつ、引数の型を "types" という関数で教える必要がある(テストできる型に型推論できる場合はその必要はないが、しかしテストできる型…

一応最後まで書いておく。でも随分前に書いたのでどう考えたのかは忘れてしまった。 13.4 Coroutines まずcoroutine macroを定義する。 (define-macro coroutine (lambda (x . body) `(letrec ((+local-control-state (lambda (,x) ,@body)) (resume (lambda…

HXML ToolboxのparseDocumentは、a_validate="0"にしているのに、XHTMLのDTDをw3.orgに取りにいく。時間がかかった挙げ句に一部のファイルが無いといってエラーに終わった。validateしないんだからいらないでしょ。 getXmlDocumentあたりを使えばいいのかも…

ちょっとしたテストデータの生成にrunhugsを使おうとして詰まった。 多分CAF leak> putChar 'a' ... というものに評価されてだんだん大きくなる">*1なのだろうけれど、Hugs(runhugs)では「長い時間」データの出力をつづけることはできないのだろうか？ 例 1 …

perl(,ruby, python, php..)のpack/unpackがHaskellから使いたい。 Gnet LibraryにFFI?

appAndShow (Func f) (Obj x) = let f' = fromJust $ cast f in show $ f' xだと、f'の型は、引数の型はObjの中身から決まりますが、返り値については showの引数なので Show a castの返り値となっている関数のものだから Typeable a -- (Obj (x :: x)) f' :…

Int as Monoid 整数は加法についてモノイドである*1。Monoidのインスタンスにしてみよう。 instance Monoid Int where mempty = 0 mappend = (+)sum' :: [Int] -> Int sum' = mconcat vecPlus :: (Int, Int) -> (Int, Int) -> (Int, Int) vecPlus = mappend …

探索とは、まず解の候補を葉とする木を作って*1、それからその木の枝をあるアルゴリズムで辿って解を発見することである*2。リストによるバックトラックを利用した探索は、木を作る端から全部フラットにして深さ優先探索をしているのである。探索アルゴリズ…

http://d.hatena.ne.jp/syd_syd/20041224#1103830417より。

一時間半もかかったが解読できたのでメモ。腕力がない… 相異点 最初にtransposeしてColor視点にはしない*1 module D050115_2 where import Data.List type Color = Int type Box = [Int] tama :: [Box] -> (Int, [[Color]]) tama = head . tamas tamas boxes…

Quiz 次をみたす関数groupsを定義せよ。 groups [p_1, p_2, ..., p_n] listは { {s_1, s_2, ..., s_n} | s_i ⊂ list, #s_i = p_i, s_i ∩ s_j = φ }を返す。順序は(与えられたリストの並びを基準にして)Haskellのsortが並べる順であることが望ましい。 例 *Gr…

このコードにいたく感心したので、探索について考えた。 dfs :: (a -> [a]) -> a -> [a] dfs f x = x:(f x >>= dfs f)bfs :: (a -> [a]) -> a -> [a] bfs f = bfs' . (:[]) where bfs' xs = xs ++ bfs' (xs >>= f)http://www.lab2.kuis.kyoto-u.ac.jp/~hanat…

[id:yts:20050112#p2]の続き。ReaderTの特別な場合なので: module ReaderTick where import Control.Monad.Reader type TickT m a = ReaderT (m ()) m a runTickT :: Monad m => TickT m a -> m () -> m a runTickT = runReaderT tick :: Monad m => m a -> …

http://d.hatena.ne.jp/syd_syd/20050111#p1モナド則は満たしません。 *Main> flip fromOIO signal $ return () >>= return >>= return ! ! !liftされたアクションに「タグ」をつけてそのタグが出てくるごとに何かする、という感じでやればいいような気がし…

http://www.sampou.org/cgi-bin/haskell.cgi?blog:Everyday%3a2005-01-11&l=jp 取り残された気分だけど、最短記録部門(何？)で挑戦。 f n = foldr (\x y -> (x:last y):init y) (replicate n []) g n=foldr(\x y->(x:last y):init y)$[1..n]>>[[]]それぞれ 5…

Parsecを少し改造*1した。whiteSpaceなどの定義を(矛盾無く)変更できるようにした。 module Test where import Text.ParserCombinators.Parsec as P import Text.ParserCombinators.Parsec.Language as P import Text.ParserCombinators.Parsec.Char as P im…

Quiz: [QUIZ] LCD Numbers (#14) via: http://www.sampou.org/cgi-bin/cahier.cgi?blog%3aCahier%3a2005-01-08 (日付指定のリンクはできないのだろうか？)コメントで教えて頂きました。 module Main where import Data.Array (listArray, (!)) import Data.L…

http://www.sampou.org/cgi-bin/haskell.cgi?blog%3aEveryday%3a2005-01-04&l=jpより。篩い。 sieve _ [] = [] sieve elem (x:xs) = x:sieve elem [y | y <- xs, not (head y `elem` x)] orbits elem span = sieve elem . map span数学的にはelemはパラメー…

http://www.sampou.org/cgi-bin/haskell.cgi?blog%3aEveryday%3a2005-01-04&l=jpより。 import Data.Graph (stronglyConnComp, flattenSCC) toCycles xs = filter ((1 /=) . length) $ map flattenSCC $ stronglyConnComp [(x, x, [y]) | (x, y) <- xs]*D050…

[Haskell] Continuation Monad (2) [id:yts:20050103#p1] の続き。 13.3 Tree matching まずTree型の定義をしておく。 data Tree a = Tree [Tree a] | Leaf a deriving (Eq, Show) car (Tree (x:xs)) = x cdr (Tree (x:xs)) = Tree xs isNull (Tree []) = Tr…

率直な感想…構文木を作るコード書くのめんどくさすぎ…自分で書こうと思っても全然書けない。慣れの問題なのだろうか…? 2004-12-27 「構文木」というのを意識しすぎなのだと思います。 例3 任意個のzip (引用略) zip3 = $(zipN 3)と書ければ嬉しいという話。 …

[Haskell] Continuation Monad (1) [id:yts:20050102#p2] の続き。 13.2 Escaping continuations Example (define list-product (lambda (s) (call/cc (lambda (exit) (let recur ((s s)) (if (null? s) 1 (if (= (car s) 0) (exit 0) (* (car s) (recur (cd…

Movedのminor nit. イヤなことにはかわりなし。 class VAFun a r f | f -> r where withVAList :: ([a] -> r) -> f instance VAFun a Int Int where withVAList g = g [] instance VAFun a r x => VAFun a r (a -> x) where withVAList g x = withVAList (g …