Chat (Lingr.com)
Informaiton
Daily
Column
- MySQL日本語の旅(5/1)
- アクセス向上秘伝(5/9)
- 一風変ったHaskellλ門(6/13)
- SICP Answer Book (5/31) 問題3.26追加
Zope Solution
Extra
アーカイブ
OSS案内所
Site Info
関連リンク
- 2004: 01 02 03 04 05 06 07 08 09 10 11 12
- 2005: 01 02 03 04 05 06 07 08 09 10 11 12
- 2006: 01 02 03 04 05 06 07 08 09 10 11 12
今月の一行
- 2005-04-27 [script] リスト比較
- 2005-04-26 [misc] 整数の分割
- 2005-04-25 [Puzzle] 覆銭問題
- 2005-04-22 [skk] I=SKK とは
- 2005-04-21 [misc] 逆置換
- 2005-04-20 [LaTeX] 表の中で斜線を引く
- 2005-04-19 [misc] 巡回置換記法
- 2005-04-18 [script] 一般順列
- 2005-04-15 [暦] 復活祭の日付
- 2005-04-14 [id] 自分の所属グループを確認する
- 2005-04-13 [file] ファイルタイプを特定する
- 2005-04-12 [game] MOO (数あてゲーム)
- 2005-04-11 [script] バナー
- 2005-04-08 [Haskell] クライアント/サーバのシミュレーション
- 2005-04-07 [script] 基数変換
- 2005-04-06 [LaTeX] 部分的な多段組
- 2005-04-05 [ghc] printf
- 2005-04-04 [リスト内包表記] 推理パズル
- 2005-04-01 [global] ソースコードタグシステム
2005-04-27 [script] リスト比較
単一型の要素をもつリストを比較する場合，辞書順比較をするのが一般的で， たとえば，[1,2,3,4] < [2,3] である．しかし，場合によっては，リストの が長い方が大きく，同じ長さなら辞書順で比較というのがやりたいときがある．
ナイーブな実装(Haskell)では，
comp :: Ord a => [a] -> [a] -> Ordering
comp xs ys = case compare (length xs) (length ys) of
EQ -> compare xs ys
c -> c
実行例
*Main> compare [1,2,3] [4,5] LT *Main> comp [1,2,3] [4,5] GT
ところで，上の実装は最初にリストの長さを求めるために， 常に比較する2つのリストを全部たどる．したがって，どちらかのリストが 無限リストであると停止しなくなる．
以下のようにして，それぞれのリストを短い方のリストの長さ分だけしか たどらないようにできる．こうすれば，両方のリストがともに無限リストでない限り は停止する．
comp :: Ord a => [a] -> [a] -> Ordering
comp xs ys
= case cmp xs ys of
Left c -> c
Right c -> c
where
cmp [] [] = Left EQ
cmp [] _ = Right LT
cmp _ [] = Rigth GT
cmp (x:xs) (y:ys)
= case cmp xs ys of
p@(Right _) -> p
p@(Left _) -> case compare x y of
EQ -> p
q -> Left q
--nobsun
2005-04-26 [misc] 整数の分割
与えられた正整数 n (n > 0) を正整数の和に分割する．
Haskell によるナイーブな実装は
import List
intSeps 1 = [[1]]
intSeps n = nub $ map (1:) iss ++ concatMap foo iss
where iss = intSeps (n-1)
foo [] = []
foo (x:xs) = nub $ map sort $ (x+1:xs) : map (x:) (foo xs)
実行例
*Main> intSeps 1 [[1]] *Main> intSeps 2 [[1,1],[2]] *Main> intSeps 3 [[1,1,1],[1,2],[3]] *Main> intSeps 4 [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]] *Main> intSeps 5 [[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]
上の実装は，リストから重複を取り除く nub という関数を使っていて 効率が悪そう．もっと効率の良いものが欲しいのだけど．．．
--nobsun
There is no comment.
2005-04-25 [Puzzle] 覆銭問題
Penny Flipping Problem というのは
- n枚のコインを全部表にして積む(初期状態)
- 一番上の1 枚を裏返す．次に上から2枚を取り上げまとめてひっくりかえし て元の位置に積む．次に3枚．．．と繰り返して，n枚全体をひっくりかえした らまた一枚にもどる．
- この手順を繰り返して初期状態に戻るまでに何回ひっくりかえすかを求めよ．
という問題である．ナイーブな実装は以下のとおり，
data Penny = H | T deriving (Show, Eq)
pflip H = T
pflip T = H
nflips n = scanl nflip (replicate n H) (cycle [1..n])
nflip xs n = map pflip (reverse ys) ++ zs
where (ys,zs) = splitAt n xs
pennyFlipping n
= 1 + (length $ takeWhile (replicate n H /= ) $ tail $ nflips n)
実行すると，
*Main> pennyFlipping 10 60 *Main> pennyFlipping 100 3299
上のナイーブなプログラムは効率が悪い．n = 1000 になるともう待てない． さて，どのように解決すればよいだろう．
--nobsun
There is no comment.
2005-04-22 [skk] I=SKK とは
仮名漢字変換のSKKではなくその名の由来とも言われているコンビネータ．
- I は入力をそのまま返す． I x = x
- S は f g x を引数として取り f x (g x) を返す． S f g x = f x (g x)
- K は x y を引数として取り x を返す．K x y = x
Haskellで書いてみよう．
s f g x = f x (g x) k x y = x i = s k k
i が本当に恒等写像になっているか確かめてみよう．
*Main> :l skk.hs *Main> i 5 5 *Main> i () () *Main> i "hoge" "hoge"
参考書: ものまね鳥をまねる
--nobsun
There is no comment.
2005-04-21 [misc] 逆置換
ある置換をキャンセルするような置換を逆置換といいます． 簡略記法で書かれた置換の逆置換を求めるには
revPerm :: Ord a => [a] -> [a] revPerm xs = [ y | (x,y) <- sort (zip xs (sort xs)) ]
を使う
*Main> revPerm "cdfbea" "fdabec"
巡回記法で表現された置換の逆置換を求めるには
revCPerm :: Ord a => [[a]] -> [[a]] revCPerm = reverse . map reverse
を使う
*Main> revCPerm ["e","bd","acf"] ["fca","db","e"]
--nobsun
There is no comment.
2005-04-20 [LaTeX] 表の中で斜線を引く
slashbox.sty を使う．
\documentclass{jarticle}
\usepackage{slashbox}
\begin{document}
\begin{table}
\begin{center}
\caption{タスク表}
\begin{tabular}{|c||c|c|c|}\hline
\backslashbox{項目}{期日}& \makebox[3em]{4/30}& \makebox[3em]{5/31}& \makebox[3em]{6/30} \\
\hline \hline
企画A & 20{\%} & 50{\%} & 100{\%} \\ \hline
執筆B & 10{\%} & 20{\%} & 30{\%} \\ \hline
\end{tabular}
\end{center}
\end{table}
\end{document}
--nobsun
There is no comment.
2005-04-19 [misc] 巡回置換記法
Error in expanding macro: (img "mimetex.cgi?\\begin{pmatrix} a & b & c & d & e & f \\\\ c & d & f & b & e & a \\end{pmatrix}")
Invalid Image URL: "mimetex.cgi?\\begin{pmatrix} a & b & c & d & e & f \\\\ c & d & f & b & e & a \\end{pmatrix}"
は，a が c へ，b が d へ，c が f へ，d が b へ，e が e へ，f が a へ，という置換を表わす一般記法です．
これは，a -> c -> f -> a ，b -> d -> b ， e -> e という3つの巡回した置換からなりたっているので，
Error in expanding macro: (img "mimetex.cgi?\\begin{pmatrix} a & c & f \\end{pmatrix}\\begin{pmatrix} b & d \\end{pmatrix}\\begin{pmatrix} e \\end{pmatrix}")
Invalid Image URL: "mimetex.cgi?\\begin{pmatrix} a & c & f \\end{pmatrix}\\begin{pmatrix} b & d \\end{pmatrix}\\begin{pmatrix} e \\end{pmatrix}"
という巡回置換記法であらわすこともある．巡回置換記法はもちろん一とおり だけではなく，
Error in expanding macro: (img "mimetex.cgi?\\begin{pmatrix} c & f & a \\end{pmatrix}\\begin{pmatrix} d & b \\end{pmatrix}\\begin{pmatrix} e \\end{pmatrix}")
Invalid Image URL: "mimetex.cgi?\\begin{pmatrix} c & f & a \\end{pmatrix}\\begin{pmatrix} d & b \\end{pmatrix}\\begin{pmatrix} e \\end{pmatrix}"
も同じ置換を表わす．また，サイクルどうしの順番を変えても同じ置換を 表わす．
Error in expanding macro: (img "mimetex.cgi?\\begin{pmatrix} e \\end{pmatrix}\\begin{pmatrix} b & d \\end{pmatrix}\\begin{pmatrix} a & c & f \\end{pmatrix}")
Invalid Image URL: "mimetex.cgi?\\begin{pmatrix} e \\end{pmatrix}\\begin{pmatrix} b & d \\end{pmatrix}\\begin{pmatrix} a & c & f \\end{pmatrix}"
一般表記を2行目だけのリストで表現する簡略記法もある． 簡略記法から巡回記法への変換スクリプトを使うと
% ./cyclic.lhs cdfbea ["e","bd","acf"]
のようになる．スクリプトは以下のとおり
#!/usr/bin/env runghc
\begin{code}
module Main where
import List
import System
toCyclic p = takeWhile (not . null)
$ snd $ mapAccumL (flip mc) p (repeat [])
mc _ [] = ([],[])
mc acc ((f,s):xs) = case break ((s ==) . fst) xs of
(ys,[]) -> (xs,reverse (s:acc))
(ys,zs) -> mc (s:acc) (zs++ys)
normalize = sortBy cmp . map minfirst
where cmp (x:_) (y:_) = compare y x
minfirst xs = take (length xs) $ dropWhile (minimum xs /=) $ cycle xs
main = do { args <- getArgs
; let start = sort end
end = concat args
in putStrLn $ show $ normalize $ toCyclic $ zip start end
}
\end{code}
--nobsun
There is no comment.
2005-04-18 [script] 一般順列
一般順列というのは，
全部で m 種類のものがあって、第 i 種(1 ≦ i ≦ m)ものが n(i) 個ずつ全 部で n 個あるとき，n 個のものの並べ方
のことです．さてこの一般順列を生成するスクリプトはどうなるだろうか．
% ./gperm.lhs 1 22 122 212 221
のような出力を期待するわけです．「一般」順列というのは，たとえば， 3種類のものがそれぞれ1個ずつなら，普通の順列と同じになるからです．
% ./gperm.lhs 1 2 3 123 213 231 132 312 321
Haskell でのスクリプトコードは以下のとおり
#!/usr/bin/env runghc
\begin{code}
module Main where
import System
main = getArgs >>= mapM_ putStrLn . gperm
gperm :: [[a]] -> [[a]]
gperm = foldr (concatMap . merges) [[]]
merges :: [a] -> [a] -> [[a]]
merges [] ys = [ys]
merges xs [] = [xs]
merges xxs@(x:xs) yys@(y:ys)
= map (x:) (merges xs yys) ++ map (y:) (merges xxs ys)
--nobsun
There is no comment.
2005-04-15 [暦] 復活祭の日付
復活祭の日 付を計算する． TAOCP の§1.3.2 の演習問題14にそのアルゴリズムがのっている．以下はHaskellの スクリプト(easter.lhs)
#!/usr/bin/env runghc
\begin{code}
module Main where
import System
import IO
main = do argv <- getArgs
case argv of
[year] -> case easter (read year) of
(m,d) -> putStrLn (year++"/"++show m++"/"++show d)
_ -> hPutStr stderr "Usage: easter year"
easter :: Int -> (Int,Int)
easter y = if sunday > 31 then (4,sunday-31) else (3,sunday)
where
sunday = fullmoon + 7 - (day + fullmoon) `mod` 7
fullmoon = let n = 44 - epact in if n < 21 then n + 30 else n
epact = let e = (11*golden + 20 + z - x) `mod` 30
in if e == 25 && golden > 11
then 26
else if e == 24 then 25 else e
day = (5 * y) `div` 4 - x - 10
x = (3 * century) `div` 4 - 12
z = (8 * century + 5) `div` 25 - 5
century = y `div` 100 + 1
golden = y `mod` 19 + 1
\end{code}
実行例
% ./easter.lhs 2005 2005/3/27 % ./easter.lhs 2006 2006/4/16
--nobsun
There is no comment.
2005-04-14 [id] 自分の所属グループを確認する
久々の「おぃおぃシリーズ」
% id uid=500(nobsun) gid=501(nobsun) 所属グループ=501(nobsun),10(wheel),503(kahua)
--nobsun
There is no comment.
2005-04-13 [file] ファイルタイプを特定する
コマンドが shell スクリプトなのか実行形式バイナリなのかを知りたいとき など，どのようなファイルなのか知りたいときには file コマンドを使う．
% file `which a2ps` /usr/bin/a2ps: ELF 32-bit LSB executable, Intel 80386, version 1, for GNU/Linux 2.2.5, dynamically linked (uses shared libs), not stripped
このマシンの a2ps コマンドは Perl版ではなく，バイナリ版だということが わかる．
file コマンドは，magicfile と呼ばれるデータベースを使う．筆者の環境で は /usr/share/file/magic がそれである．
% grep Java /usr/share/file/magic # Java ByteCode 0 belong 0xcafebabe compiled Java class data, # Java serialization 0 beshort 0xaced Java serialization data
Java の ByteCode は cafebabe を見ていることがわかる．
--nobsun
cut-sea: (Thu Apr 14 07:03:27 2005
)
とりびあ。 cafe babeの類似ネタで。 SunOSの/stand/rootconfってファイルの マジックナンバーはdead beaf。
cut-sea: (Thu Apr 14 17:13:17 2005
)
微妙にガセビアでした。 s/beaf/beef/ => dead beefが正着。
2005-04-12 [game] MOO (数あてゲーム)
ルールは以下の通り
- 出題者は 0 から 9 までの互いに異なる数字を使った４桁の数(以下ＭＯＯ 数と呼ぶ)を正解として用意し，解答者からは隠しておく．
- 解答者は質問としてＭＯＯ数を一つ提示する．出題者は質問と正解を比較し， 同じ数字が同じ桁に出現する回数と，同じ数字が別の桁に出現する回数の組を ヒントとして与える
- 解答者はなるべく少い質問で正解を当てる
ルールだけでは判りにくいので，ゲームの進行(後述の moo.lhs スクリプトに よるもの)を示す．(ここでは正解は4832)
% ./moo.lhs Guess : 0123 ← 解答者:質問 Score : (0,2) ← 出題者:ヒント Guess : 2345 ← 解答者:質問 Score : (0,3) ← 出題者:ヒント Guess : 3467 ← 解答者:質問 Score : (0,2) ← 出題者:ヒント Guess : 4238 ← 解答者:質問 Score : (2,2) ← 出題者:ヒント Guess : 4832 ← 解答者:質問 You Got it in 5 guesses. %
要領が会得すると大抵の場合 5回程度の質問で正解に達っすることができるら しい．さてあなたは何回くらいの質問で正解にたどりつけますか？
出題用プログラムは簡単ですので，自分で作っても簡単でしょう．
GHC-6.4がインストールされていれば，以下のHaskellスクリプトで遊べます．
#!/usr/bin/env runghc
\begin{code}
module Main where
import Monad
import Random
---- MOO ---------------------------------------------------------------
type Moo = String
type Bulls = Int
type Cows = Int
type Prod = (Bulls,Cows)
type History = [(Moo,Prod)]
type Candidates = [Moo]
type State = (Candidates,Moo,History)
score :: Moo -> Moo -> Prod
score answer guess
= (bulls,cows)
where
bulls = sum (zipWith ((fromEnum .) . (==)) answer guess)
cows = sum (map (fromEnum . (`elem` answer)) guess) - bulls
guess :: Prod -> State -> (Moo, State)
guess prod (cads,moo,his)
= (moo',(cads',moo',his'))
where
his' = (moo,prod):his
moo':cads' = filter (\ x -> and [ score x m == p | (m,p) <- his' ]) cads
ndig :: Int
ndig = 4
digs :: String
digs = "0123456789"
cs :: [Moo]
cs = perm digs 4
main = do { gen <- newStdGen
; let (r,_) = randomR (0,nPr (length digs) ndig - 1) gen
ans = nthPerm digs ndig r
reqs = client getLine (const getLine) resps
resps = server (scoreIO ans) reqs
in catch (foldM trav 0 resps) (const (return 0)) >> return ()
}
scoreIO :: Moo -> IO Moo -> IO Prod
scoreIO ans moo = do { putStr "Guess: "; moo >>= return . score ans }
trav :: Int -> IO Prod -> IO Int
trav i iop
= do { p <- iop
; if p == (4,0)
then putStrLn ("You got it in "++show (i+1)++" guesses.") >> fail ""
else (putStr "Score: " >> putStrLn (show p)) >> return (i+1)
}
-- Combinatorials ------------------------------------------------------
splits :: [a] -> [([a],[a])]
splits [] = [([],[])]
splits xxs@(x:xs) = ([],xxs) : [ (x:ys,zs) | (ys,zs) <- splits xs ]
perm :: [a] -> Int -> [[a]]
perm _ 0 = [[]]
perm [] _ = []
perm xs n = concat [ pm n hs ts | (hs,ts) <- splits xs ]
where pm _ _ [] = []
pm n hs (t:ts) = [ t:ys | ys <- perm (hs++ts) (n-1) ]
nPr :: Int -> Int -> Int
nPr n r = product [n-r+1..n]
nthPerm :: [a] -> Int -> Int -> [a]
nthPerm xs r m = nprm xs (length xs) r m
where
nprm _ _ 0 0 = []
nprm xs n r m = case divMod m (nPr (n-1) (r-1)) of
(p,q) -> case splitAt p xs of
(xs,y:ys) -> y : nprm (xs++ys) (n-1) (r-1) q
---- Client/Server simulation ------------------------------------------
server :: (a -> b) -> ([a] -> [b])
server _ [] = []
server process (req:reqs) = process req : server process reqs
client :: a -> (b -> a) -> ([b] -> [a])
client req0 next ~(resp:resps)
= req0 : client (next resp) next resps
\end{code}
--nobsun
There is no comment.
2005-04-11 [script] バナー
単なるお遊びですが．
% ./banner.lhs "Hello, world!" H H EEEEE L L OOO W W OOO RRRR L DDDD ! H H E L L O O W W O O R R L D D ! HHHHH EEEEE L L O O W W O O RRRR L D D ! H H E L L O O ,, W W W O O R R L D D ! H H EEEEE LLLLL LLLLL OOO , W W OOO R R LLLLL DDDD .
コードは，以下のとおり(gofer-2.30b のサンプルプログラムをほんの少し改変)．
import Char
import List
import System
main = getArgs >>= putStrLn . say . head
say = ('\n':) . unlines . map join . transpose . map picChar
where join = foldr1 (\xs ys -> xs ++ " " ++ ys)
picChar c | isUpper c = alphas !! (ord c - ord 'A')
| isLower c = alphas !! (ord c - ord 'a')
| isSpace c = blank
| isDigit c = digits !! (ord c - ord '0')
| c=='/' = slant
| c=='\\' = reverse slant
| otherwise = head ([ letter | (c',letter) <- punct, c'==c ]
++ [empty])
blank = [" ", " ", " ", " ", " "]
slant = [" ", " ", " ", " ", "" ]
empty = repeat ""
punct = [(',', [" ", " ", " ", " ,, ", " , "]),
('.', [" ", " ", " ", " .. ", " .. "]),
('?', [" ??? ", "? ?", " ? ", " ? ", " . "]),
('!', [" ! ", " ! ", " ! ", " ! ", " . "]),
('-', [" ", " ", "-----", " ", " "]),
('+', [" + ", " + ", "+++++", " + ", " + "]),
(':', [" ", " :: ", " ", " :: ", " "]),
(';', [" ", " ;; ", " ", " ;; ", " ;; "])
]
digits = [[" 000 ", "0 00", "0 0 0", "00 0", " 000 "],
[" 1 ", " 11 ", " 1 ", " 1 ", " 111 "],
[" 222 ", "2 2", " 2 ", " 2 ", "22222"],
["3333 ", " 3", " 333 ", " 3", "3333 "],
[" 4 ", " 44 ", " 4 4 ", "44444", " 4 "],
["55555", "5 ", "5555 ", " 5", "5555 "],
[" 666 ", "6 ", "6666 ", "6 6", " 666 "],
["77777", " 7", " 7 ", " 7 ", " 7 "],
[" 888 ", "8 8", " 888 ", "8 8", " 888 "],
[" 999 ", "9 9", " 9999", " 9", " 999 "]]
alphas = [[" A ", " A A ", "AAAAA", "A A", "A A"],
["BBBB ", "B B", "BBBB ", "B B", "BBBB "],
[" CCCC", "C ", "C ", "C ", " CCCC"],
["DDDD ", "D D", "D D", "D D", "DDDD "],
["EEEEE", "E ", "EEEEE", "E ", "EEEEE"],
["FFFFF", "F ", "FFFF ", "F ", "F "],
[" GGGG", "G ", "G GG", "G G", " GGG "],
["H H", "H H", "HHHHH", "H H", "H H"],
["IIIII", " I ", " I ", " I ", "IIIII"],
["JJJJJ", " J ", " J ", "J J ", " JJ "],
["K K", "K K ", "KKK ", "K K ", "K K"],
["L ", "L ", "L ", "L ", "LLLLL"],
["M M", "MM MM", "M M M", "M M", "M M"],
["N N", "NN N", "N N N", "N NN", "N N"],
[" OOO ", "O O", "O O", "O O", " OOO "],
["PPPP ", "P P", "PPPP ", "P ", "P "],
[" QQQ ", "Q Q", "Q Q Q", "Q Q ", " QQ Q"],
["RRRR ", "R R", "RRRR ", "R R ", "R R"],
[" SSSS", "S ", " SSS ", " S", "SSSS "],
["TTTTT", " T ", " T ", " T ", " T "],
["U U", "U U", "U U", "U U", " UUU "],
["V V", "V V", "V V", " V V ", " V "],
["W W", "W W", "W W", "W W W", " W W "],
["X X", " X X ", " X ", " X X ", "X X"],
["Y Y", " Y Y ", " Y ", " Y ", " Y "],
["ZZZZZ", " Z ", " Z ", " Z ", "ZZZZZ"]
]
--nobsun
There is no comment.
2005-04-08 [Haskell] クライアント/サーバのシミュレーション
Haskell では遅延パターンとストリームをつかって，クライアント/サーバの シミュレーションができる．
サーバの処理は，クライアントからの要求に含まれる数を 1 増して 応答とする．クライアントは応答に含まれる数を次の要求に含めるという 単純なものを Haskell で書くと，
data Request = Req Int deriving Show data Response = Res Int deriving Show reqs :: [Request] ress :: [Response] reqs = client req0 ress ress = server reqs client :: Request -> [Response] -> [Request] server :: [Request] -> [Response] client req0 ~(res:ress) = req0 : client (next res) ress server (req:reqs) = process req : server reqs req0 :: Request req0 = Req 0 next :: Response -> Request next (Res n) = Req n process :: Request -> Response process (Req n) = Res (n+1)
実際の動きを見るには，たとえば，要求と応答の組のリストの最初の 5 個を 見てみればよい．
*Main> take 5 (zip reqs ress) [(Req 0,Res 1),(Req 1,Res 2),(Req 2,Res 3),(Req 3,Res 4),(Req 4,Res 5)]
単純なプログラムですが，計算の進行を追ってみると遅延評価の不思議さが 体験できます．(正確に追うのはちょっとむずかしいかもしれませんが．．．)
--nobsun
There is no comment.
2005-04-07 [script] 基数変換
整数をr進法で表現する．
radixConv :: Integral a => a -> a -> (a,[a])
radixConv n r
= (r,map snd $ reverse $ takeWhile (not . (==) (0,0)) $ tail $ iterate f (n,0))
where
f (x,_) = divMod x r
実行例
*Main> radixConv 123 2 (2,[1,1,1,1,0,1,1])
mapAccumL を使うと
import List
radixConv' :: Integral a => a -> a -> (a,[a])
radixConv' n r
= (r, reverse $ takeWhile (0 <=) $ snd $ mapAccumL f n $ repeat r)
where f 0 _ = (-1,-1)
f n r = divMod n r
こんな感じかなぁ．
--nobsun
There is no comment.
2005-04-06 [LaTeX] 部分的な多段組
multicolpar.styを使う． 文書の途中に対訳などを入れたいときに便利．
\documentclass{jsarticle}
\usepackage{multicolpar}
\begin{document}
\begin{multicolpar}{2}
\textbf{Wizard Book}
\textbf{魔法使い本}
Structure and Interpretation of Computer Programs
(Hal Abelson, Jerry Sussman and Julie Sussman; MIT Press,
1984, 1996; ISBN 0-262-01153-0), an excellent computer
science text used in introductory courses at MIT. So called
because of the wizard on the jacket. One of the bibles of
the LISP/Scheme world. Also, less commonly, known as the
Purple Book. Now available on the
http://mitpress.mit.edu/sicp/
『計算機プログラムの構造と解釈』(ハル・エイブル
ソン，ジェリー・サスマン，ジュリー・サスマン著；MITプレス，
1984，1996；ISBN 0-262-01153-0)，MIT(マサチュセッツ工科大学)
の初学年のコースで使われている計算機科学の秀逸の教科書．表紙
に魔法使いが描かれているのでこう呼ばれている．LISP/Scheme界
のバイブルのひとつ．「紫本」と呼ばれることもある．現在，
http://mitpress.mit.edu/sicp/ で公開されている．
\end{multicolpar}
~
~
The Jargon File (http://www.catb.org/jargon/html/W/Wizard-Book.html)より
\end{document}
There is no comment.
2005-04-05 [ghc] printf
ghc-6.4 から GHCのbaseライブラリにText.Printfというモジュールが はいった．これは C の printf のフォーマットが使えるというもの．
ちょいと怪しい雰囲気のある関数 printf の使用例は
Prelude> :m Text.Printf Prelude Text.Printf> printf "%d\n" (23::Int) 23 Prelude Text.Printf> printf "%s %s\n" "Hello" "World" Hello World Prelude Text.Printf> printf "%.2f\n" (pi::Double) 3.14
さて，printf の型は？
--nobsun
There is no comment.
2005-04-04 [リスト内包表記] 推理パズル
2005-02-17に非決定計算で推理パズルが解けるか もと言ったが，Haskellのリスト内包表記を使うと簡単に解けそうなのでやっ てみた．解いてみる問題は， ニコリの推理パズルです．
コードは以下の通り
data Item = Umbrella | Shoes | Paper | Thread deriving (Enum, Eq, Show)
data Color = Red | Blue | White | Black deriving (Enum, Eq, Show)
data Person = Akira | Isamu | Tadashi | Hiroshi deriving (Enum, Eq, Show)
is = [Umbrella .. Thread]
cs = [Red .. Black]
ps = [Akira .. Hiroshi]
bs = [ ics | ics <- map (zip is) (perm 4 cs)
, notElem (Thread, White) ics
, elem (Paper, Blue) ics
, notElem (Shoes, Red) ics ]
solution = [ pbs | pbs <- map (zip ps) $ concat $ map (perm 4) bs
, case lookup Akira pbs of { Just (_,c) -> c == White}
, case lookup Isamu pbs of { Just (i,_) -> i /= Paper }
, case lookup Tadashi pbs of { Just (i,_) -> i == Shoes } ]
perm は順列を求める関数で2005-03-14で定義したもの 実行結果は
Main> solution [[(Akira,(Umbrella,White)) ,(Isamu,(Thread,Red)) ,(Tadashi,(Shoes,Black)) ,(Hiroshi,(Paper,Blue))]]
問題文を上手く論理式にさえもっていければ，難しい問題でもいけそうです．
--nobsun
There is no comment.
2005-04-01 [global] ソースコードタグシステム
ソースコードに索引付けを行うことで、大規模システムのハックや レビューを効率化するためのツール群．インストールは簡単． 対応言語は C, C++, Yacc, Java, PHP4 だそうだ．
global-4.8.4.tar.gz をダウンロードしたら，
% tar zxvf global-4.8.4.tar.gz % cd global-4.8.4 % ./configure % make % sudo make install
これでインストール完了． でたとえば，Hugs のソースコードを読むなら，
% tar zxvf hugs98-Mar2005-patched.tar.gz % cd hugs98-Mar2005-patched % ./configure --enable-char-encoding
と準備しておいて
% cd src % gtags % htags -saFf
とかやると，HTMLというサブディレクトリに html ファイルができる． トップは，HTML/index.html ここからbrowserで読む．簡単で便利．
--nobsun
There is no comment.
There is no comment.