リストのシャッフル

Haskell Puzzle

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

2005-10-25

リストのシャッフル

Haskell

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

2005-10-24

前のページ・次のページ

Misc

前のページ・次のページ。 Web を徘徊していて気になった「次のページ」という記述。これは「後のページ」の方がわかりやすいんではないか。時間を一方向にしか進めない人にとっては次 = 未来なのかもしれないけど。http://www.lab2.kuis.kyoto-u.ac.jp/~h…

2005-10-23

リストのシャッフル

Haskell

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 …

2005-10-22

シャッフル・クイズ

Puzzle

http://www.hyuki.com/d/200510.html#i20051020

2005-08-19

[Memo] ペアマッチあみだくじ

こういうものらしい。単に普通のあみだくじの(隣り合う)二本を底で繋げればいいと思う。どっちに進むかわかりやすいし、下から一度折れば良い。けれん味に欠けるからだろうか？

2005-03-18

■

「あー、もういいわ。キャンセルする」そう言って斜め後ろの客は出ていった。店に入る時に見た後ろ姿では、白髪交じりのボサボサ髪、歳の頃は五十ぐらいの男であった。注文してからは一分と経ってない。苦笑しながら給仕の女性が厨房にキャンセルを告げた。…

2005-03-13

[Memo] 最近の疑問

代数的変形による効率の向上を当てにして(予測して)プログラミングできるのか自動的な最適化(ヒューリスティックを含んでもよい)の結果がプログラマによる最適化(問題を「理解」して解く)の結果よりも優れた効率のプログラムを生むことがあり得るが、そのよ…

2005-02-24

最大部分列和問題

Haskell

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

2005-02-23

自分の定義式に評価される文字列

Haskell

普通に 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 …

2005-02-23

繰り返し実行するたびに大きくなるプログラム

Haskell

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

2005-02-20

Examples

Haskell

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]より

2005-02-14

CGIデバッグ用shスクリプト

1 #!/bin/sh echo -e "Content-type: text/plain\n" env 2 #!/bin/sh decode () { awk 'BEGIN { RS = "&"; FS = "=" } {print $1 " = {" $2 "}\n"}' \ | /usr/local/bin/urldecode -p } echo -e "Content-type: text/plain\n" env echo -e "\n-- Get data --…

2005-02-14

関数型shスクリプトによる掲示板

#!/bin/sh DATAFILE="data/bbs.txt" cat >> $DATAFILE; echo "" >> $DATAFILE cat << EOF Content-type: text/html <html><body><form method="post" action="$SCRIPT_NAME"> <textarea name="msg" rows="5" cols="80"></textarea><br/> <input type="submit" name="write" value="Write"/> </form> EOF cat $DATAFILE | se…</body></html>

2005-02-02

■

大半のGPLの利用者は、勝手にGPLにしたのであって、FSFと契約してGNU softwareにしたわけじゃない。 FSFと契約すれば安全ですってのは何の反論にもなってない。裁判すればいいというのは、無責任な意見に聞こえる。GPLが契約かただの宣言かということすら確…

2005-02-02

■

今日は雪だった。ここでは、少しでも積もるのは年に数回しかない。川縁を歩いて下っていると、散歩中の犬に出会った。耳の垂れた、白っぽい毛の犬だった。尻尾を振ってうれしそうに走り回りながら、雪の中に鼻を突っ込んでいた。私はもちろん走り回らなかっ…

2005-01-31

虹色の曲線

Mathematica

ParametricPlot3Dは変なところでオプションを指定する。 ParametricPlot3D[{Cos[5 t], Sin[3 t], Sin[t], {Thickness[.02], Hue[t]}}, {t, 0, 2 \[Pi]}, PlotPoints -> 500];

2005-01-30

Re:http://www.sampou.org/cgi-bin/haskell.cgi?HowTo%3aQuickCheck&l=jp

Haskell

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

2005-01-30

再犯者率に関する反論への反論

Misc

私のblogを見ていてhttp://sheepman.parfait.ne.jp/さんを見ていないひとが居られるのかどうか甚だ疑問ではありますが: sheepmanさんからhttp://d.hatena.ne.jp/yts/20050120への反論を頂きました。書き換えないつもりでしたが、寿命を終えたと思うので、対…

2005-01-29

Continuation Monad (4)

Haskell

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

2005-01-28

■

ヒラガナ。平仮名。かたかな。片仮名。かんじ。カンジ。反応時間を測る実験ができそうだ。

2005-01-28

GPLの問題点

Misc

Kazuho Oku氏の主張がなぜ理解されないのか不思議だ。私の理解するところによると、こういうことだ。世の中には、GPLを良く理解しないまま自分のソフトウェアをGPLにしてしまう、あるいはしてしまった人がいる。その人達に、GPL*1の危険性に対する、つまり、…

2005-01-27

parseDocument (HXT)

Haskell

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