本買った

プログラミングClojure

プログラミングClojure

本屋で見かけたのでついうっかりと。Scalaの本は迷った挙句にやめたのに……大きさが手頃だからかも。

で,第1章 Getting Started と第2章 Clojureひとめぐり だけ読んでみた。以下メモ。

  • JVMの上で動くLisp リ・ローデッド。
  • カッコはやや少ない。
  • 関数型。
  • Javaのクラスが利用できる。
  • 並行プログラミングが簡単。
  • 動的型。
  • 一般にデータは変更不可能だけど,リファレンスは状態を持つことができる。
 user=> #{}
 #{}
 user=> (def visitors (ref #{}))
 #'user/visitors
 user=> (dosync (alter visitors conj "Stu"))
 #{"Stu"}
  • マクロとリーダマクロがある(どうちがう?)
  • マップ
 user=> {:Lisp "McCarty", :Clojure "Hickey"}
 {:Lisp "McCarty", :Clojure "Hickey"}
  • :(コロン)出始まってるのはキーワード。Ruby の Symbol のようなもの。
  • マップは関数としても働く。引数としてキーを与えると対応する値が返る。
 user=> ({:Lisp "McCarty", :Clojure "Hickey"} :Clojure)
 "Hickey"
  • キーも関数として働く。引数としてマップを与えるとキーに対応する値が返る。
 user=> (:Clojure {:Lisp "McCarty", :Clojure "Hickey"})
 "Hickey"
  • 関数を定義するには defn。もちろん無名関数もあり。
  • 分配束縛。
  • 副作用を扱うには,do を使う。この do は Haskell のとはべつもの。
 user=> (defn is-small? [number]
   (if (< number 100)
     "yes"
     (do
       (println "Saw a big number" number)
       "no")))
 #'user/is-small?
 user=> (is-small? 101)
 Saw a big number 101
 "no"

suffix array ってのは

こないだのを参考にしてくれたらしい。

なんだか俺のコードよりもHaskellらしく見えるよ。

ところで,リンク先のコードだと検索するたびに suffix array というか suffix のリストを作っているように見える。俺の理解では,suffix array を利用するメリットというのは,suffix array を作るときには大量にメモリを必要とするけど検索するときには必要ない,ってことだと思うんだけど。


それはそれとして forever という関数を初めて知った。今度使ってみよう。

簡単なWebサーチエンジンの作り方を試す

気がつけば12月も中旬だよ……。

少し前になるけど,「あとで試す」タグをつけといたやつをやってみる。これ↓:

具体的な手順はこっちのページで公開されている。


さて,順にやってみよう。

課題1-1

与えられた文字列のsuffix arrayを作成するプログラムを作成せよ.

 import Data.List
 
 suffixArray :: String -> [Int]
 suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs
   where
     sort' = sortBy (\a b -> compare (snd a) (snd b))

実行例:

 *Main> suffixArray "abcbccab"
 [7,1,8,2,4,6,3,5]

課題1-2

与えられた文字列に対し,その部分文字列を入力し,部分文字列が出現する全位置を列挙する検索プログラムを作成せよ.(ヒント: suffix array上の2分探索を行う)

二分探索とはいうものの,検索対象の部分文字列の出現箇所すべてを列挙するには,中央の値(suffix)の右か左を単純に無視してしまうわけには行かない。場合によっては左右両方にあるかもしれないから。なので,まずは整理してみる。

  1. 検索文字列よりも小さい → 左にはない。右を検索。
  2. 検索文字列と等しい → 当たり。左にはないが,まだ右にはあるかもしれないので検索。
  3. 検索文字列よりも大きい → これはさらに2ケースに分けられる。
    1. 検索文字列がプレフィックスになっている → 当たり。さらに左にも右にもあるかもしれないので両方を検索。
    2. 検索文字列がプレフィックスになっていない → 右にはない。左を検索。

これをコードにするとこうだ:

 import Data.List
 
 suffixArray :: String -> [Int]
 suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs
   where
     sort' = sortBy (\a b -> compare (snd a) (snd b))
 
 suffixOf :: String -> Int -> String
 suffixOf s n = drop (n-1) s
 
 search :: String -> [Int] ->  String -> [Int]
 search _ []  _  = []
 search s ary sb = let n = (length ary) `div` 2
                       sfx = suffixOf s (ary !! n)
                   in
                   if sfx < sb then
                       search s (drop (n+1) ary) sb
                     else if sfx == sb then
                       (ary !! n) : search s (drop (n+1) ary) sb
                     else if isPrefixOf sb sfx then
                       (search s (take n ary) sb) ++ [ary !! n] ++ (search s (drop (n+1) ary) sb)
                     else
                       search s (take n ary) sb

実行例:

 *Main> search "abcbccab" (suffixArray "abcbccab") "ab"
 [7,1]

課題1-3

指定された1個のHTMLテキストファイルをメモリ中に読み込んで1個の文字列とし,それに対する suffix array をメモリ中に作成し,ユーザから入力された文字列を検索して,入力文字列が出現する全位置を列挙するプログラムを作成せよ.

ファイルを読み込んで,searchを適用して,あとは適当にフォーマットして出力すればいいだけだ。ファイルは課題のページからリンクしてるこのページをダウンロードして使った(ファイル名決めうち)。

 module Main where
 
 import Data.List
 import System.Environment ( getArgs )
 
 -------------------------------------------------------------------------------
 
 filename = "CodeConvTOC.doc.html"
 
 main :: IO ()
 main = do argv <- getArgs
           contents <- readFile filename
           substring <- return $ head argv
           mapM_ (putStrLn . format contents) $ search contents (suffixArray contents) substring
 
 format :: String -> Int -> String
 format str pos = show pos ++ ": " ++ take 10 (suffixOf str pos)
 
 -------------------------------------------------------------------------------
 
 suffixArray :: String -> [Int]
 suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs
   where
     sort' = sortBy (\a b -> compare (snd a) (snd b))
 
 suffixOf :: String -> Int -> String
 suffixOf s n = drop (n-1) s
 
 search :: String -> [Int] ->  String -> [Int]
 search _ []  _  = []
 search s ary sb = let n = (length ary) `div` 2
                       sfx = suffixOf s (ary !! n)
                   in
                   if sfx < sb then
                       search s (drop (n+1) ary) sb
                     else if sfx == sb then
                       (ary !! n) : search s (drop (n+1) ary) sb
                     else if isPrefixOf sb sfx then
                       (search s (take n ary) sb) ++ [ary !! n] ++ (search s (drop (n+1) ary) sb)
                     else
                       search s (take n ary) sb
 
 -------------------------------------------------------------------------------

実行例:

 ^o^ >runhaskell suffixArray.hs File
 10208: File Examp
 1959: File Names
 1664: File Names
 2250: File Organ
 1815: File Suffi
 2422: Files</a>

課題1-4

ちょっと時間があいたけど続き。

以下の手順で,複数ファイルに対して全文検索を行うプログラムを作成せよ.

1. 指定された1個以上のm個のファイルをメモリ内で連結した長い文字列を作る.そのときにファイルの境 界に,テキストファイル中には通常は現れない文字(例えばヌル文字'\0'等)を入れ,検索時に複数ファイルを またいだ文字列にマッチしないようにしておく.
2. 1.で作った作った長い文字列中の文字位置から元のファイル名を得られるようにするための表を作る. 例えば,file1.html, file2.html, file3.htmlがそれぞれ100, 200, 300のファイルサイズをもつとき,[("file 1.html", 100), ("file2.html", 200), ("file3.html", 300)]というような表を作る(効率的な方法,プログ ラムしやすい方法を各自工夫せよ).
3. 課題1-3で作成したプログラムと,1.および2.で作ったデータを用いて,ユーザから入力された文字列を 検索し,入力文字列が出現するファイル名とファイル内の位置(ファイルの先頭から数えた文字数)を全て列 挙するプログラムを作成せよ.

課題1-3から変えたとこだけ:

 main :: IO ()
 main = do argv <- getArgs
           files <- mapM readFile $ tail argv
           let contents = concat $ intersperse "\0" files
           let table = makeFileTable (tail argv) $ map length files
           let substring = head argv
           mapM_ (putStrLn . format table contents) $ search contents (suffixArray contents) substri ng
 
 -------------------------------------------------------------------------------
 
 format :: [(String, Int)] -> String -> Int -> String
 format t str pos = let (f, p) = filePos t pos
                    in
                    f ++ ": " ++ show p ++ ": " ++ take 15 (suffixOf str pos)
 
 -------------------------------------------------------------------------------
 
 makeFileTable :: [String] -> [Int] -> [(String, Int)]
 makeFileTable fs ls = zip fs $ snd $ mapAccumL (\a x -> (a+x+1, a)) 1 ls
 
 
 filePos :: [(String, Int)] -> Int -> (String, Int)
 filePos (f:[])     n              = (fst f, n - snd f + 1)
 filePos (f1:f2:fs) n | snd f2 < n = filePos (f2:fs) n
                      | otherwise  = (fst f1, n - snd f1 + 1)
 
 -------------------------------------------------------------------------------

元ファイルの表はファイル名とその開始位置をタプルにした。

実行例:

 ^o^ >runhaskell suffixArray.hs Intro CodeConvTOC.doc.html CodeCOnventions.doc.html
 CodeConvTOC.doc.html: 1063: Introduction</a
 CodeCOnventions.doc.html: 517: Introduction</h

今日はここまで。続きは明日……やれるといいなぁ。

ISBN 出版者記号の割り当て規則

ISBNを扱うのに ISBN Tools というライブラリを使っている。
なんでかっていうと ISBN_Tools.hyphenate_isbn13 っていうメソッドがあって,数字だけのISBNをハイフンの入ったISBNに変換してくれるのが使えると思ったからだ。
こんな感じ:

 irb(main):006:0> ISBN_Tools.hyphenate_isbn13('9780672328848')
 => "978-0-6723-2884-8"


ところがこのメソッド,肝心の日本(グループ番号4)に対応してくれてない。
ソースを見たところ,data/ranges.dat にグループ番号と出版者記号の定義を追加すればいいみたいだ。

というわけでちょっと調べてみた。


日本国内のことなんだから日本のISBNを管理しているところへいけばいいんだろう,と思ったんだけど,その日本図書コード管理センターのサイトの中を探してみても規則で割り当ててるのか,どうもどこにも載ってない。
同じ不満をもっる人がネットのあちこちにいるみたいだな。どうなってんだ。

で,結局 ISBN の本家 International ISBN Agency のサイトでPDFを見つけた。これでいいんだよな。

これによると日本の出版者記号は下のような規則になっているようだ。

2ケタ 00〜19
3ケタ 200〜699
4ケタ 7000〜8499
5ケタ 85000〜89999
6ケタ 900000〜949999
7ケタ 9500000〜9999999


さて,ISBN Tools に戻ろう。
調べた成果を反映するには前述の data/ranges.dat に次の1行を追加すればいい。

 4,00..19,200..699,7000..8499,85000..89999,900000..949999,9500000..9999999

カンマ区切りになってて,はじめの値がグループ番号,2つめ以降に出版者記号の連続する範囲を列挙している。これで日本の出版者にも対応するようになった。

 irb(main):007:0> ISBN_Tools.hyphenate_isbn13('9784863540224')
 => "978-4-8635-4022-4"

10ケタのISBNでもできる。

 irb(main):008:0> ISBN_Tools.hyphenate_isbn10('4873110238')
 => "4-87311-023-8"

急勾配の判定

id:edvakfさんがやってるのを見かけたので久しぶりに。


どう書く?org にはこれをポストしたんだけど:

 import List
 
 steep xs = and $ zipWith (>) xs $ map sum $ tail $ tails xs


$ が多くてうっとうしいからがんばって無くしてみた。ついでに引数もなくなった。

 import List
 
 steep2 = and . s (zipWith (>)) sums
   where
     s f g x = f x (g x)
     sums = map sum . tail . tails

なんかかえって解りにくいかも。


実行結果:

 *Main> steep2 [32,16,8,4,2,1]
 True
 *Main> steep2 [31,16,8,4,2,1]
 False

Windows上のApacheでFastCGIを動かすメモ


自分用のメモ。


cf. Windows + Apache + FastCGI - h4yの日記
cf. WindowsでRuby on Rails その4 Ruby on RailsをFastCGIで動かす - 色々な事を忘れないよう忘備録と日記


FastCGIのダウンロードは公式サイトダウンロードコーナーから。Apache のバージョンが 2.0.63 なので mod_fastcgi-2.4.2-AP20.dll をダウンロードした。これを mod_fastcgi.dll にリネームして,Apache の modules ディレクトリにコピー。

つぎは Ruby 側の準備。gem で fcgi をインストールしようとしたけど ruby のヘッダファイルがないって怒られる:

 ^o^ >gem install fcgi --remote
 Building native extensions.  This could take a while...
 ERROR:  Error installing fcgi:
         ERROR: Failed to build gem native extension.
 
 C:/usr/ruby/bin/ruby.exe extconf.rb install fcgi --remote
 can't find header files for ruby.
 
 
 Gem files will remain installed in C:/usr/ruby/lib/ruby/gems/1.8/gems/fcgi-0.8.7
  for inspection.
 Results logged to C:/usr/ruby/lib/ruby/gems/1.8/gems/fcgi-0.8.7/ext/fcgi/gem_mak
 e.out

ググってみると,RubyForApache というのが見つかったので version 1.3.1 をダウンロード。なんか2005年って古いんだけど。
ファイルはインストーラなのでダブルクリックしてインストール。途中でインストールするコンポーネントを聞かれるので,mod_fastcgi 以外のコンポーネントのチェックをはずす。mod_rubymysql.soは今回はパス。
あと C:\Windows\System32\msvcp71.dll に書き込めないというメッセージが出るけど,これは無視して進める。


最後に Apache の設定。httpd.conf につぎの行を追加する。

 LoadModule fastcgi_module modules/mod_fastcgi.dll
 AddHandler fastcgi-script .fcgi

Apache を再起動して終了。


テスト用のスクリプトはこんなの。

 #! C:/usr/ruby/bin/ruby.exe
 
 require 'fcgi'
 
 FCGI.each_cgi do |cgi|
   print "Content-Type: text/plain\n\n"
   print "Hello world. This is FastCGI.\n"
 end

それと ExcecCGI を有効にしておく必要があるみたいなので .htaccess で設定する。

 Options +ExecCGI

Ruby 1.9 で FizzBuzz

Ruby 1.9.1 もリリースされたことだし,新機能(Fiber と Array#cycle)を使ってFizzBuzz を書いてみたよ。d:id:takatoh:20070509:fizzbuzzRuby版。

cf. Ruby 1.9.1 の歩き方 - るびま 0025号

 # -*- encoding: utf-8 -*-
 
 fizzbuzz = Fiber.new do
   fizz = ["", "", "Fizz"].cycle
   buzz = ["", "", "", "", "Buzz"].cycle
   n = 1
   while
     s = fizz.next + buzz.next
     Fiber.yield(s == "" ? n.to_s : s)
     n += 1
   end
 end
 
 
 100.times{ puts fizzbuzz.resume }

実行結果は省略。

追記:

Fiber ってスレッドに似た云々とかいうより,途中で評価を中断出来る(&途中の値を返せる)クロージャだと考えた方がわかりやすいんじゃないかと思った。

MXML

MXML は,ウィンドウの構成を記述する。こんな感じ。

 <?xml version="1.0" encoding="utf-8"?>
 <mx:WindowedApplication xmlns:mx="http://www.adobe.com/2006/mxml"
                         layout="absolute"
                         title="Hello AIR">
 
   <mx:Script>
     <![CDATA[
       private function hello():void {
         myLabel.text = "Hello AIR!";
       }
     ]]>
   </mx:Script>
 
   <mx:Label id="myLabel" horizontalCenter="0" verticalCenter="0"/>
   <mx:Button id="myButton" label="click" horizontalCenter="0" verticalCenter="20" c lick="hello();"/>
 
 </mx:WindowedApplication>

ルートエレメントは WindowedApplication で,これがウィンドウ全体を表す。この例では,他に Label と Button が配置されている。
配置できるのはコントロールとかコンテナとか呼ばれるもの。実体は ActionScript のクラスで,パッケージにまとまっている。わかりやすい一覧表みたいなものは見つからないんだけど,リファレンスのこのあたりに情報がある。

  • mx:Controls パッケージ
  • mx:COntainers パッケージ

Web上の情報とか

ここまで Adobe のページ。ここからは参考にした記事など。