文字列間のレーベンシュタイン距離を求める(2)Haskell版

一昨日のお題を、Haskell でやってみた。

0 で初期化した二次元リスト(マトリックス)から foldl を使ってレーベンシュタイン距離のマトリックスを作る、というアイデアは出たんだけど、マトリックスを 0 で初期化する(ldInit)のと要素を置き換えたマトリックスを作る(mReplace)のがなかなか難産だった。結果として ldInit はリスト内包表記を使って簡潔にかけたけど、mReplace のほうはなんか泥臭くなってしまった。もっとエレガントにいかないもんだろうか。

実行例:

takatoh@nightschool $ runhaskell ld.hs apple play
4
takatoh@nightschool $ runhaskell ld.hs perl pearl
1

文字列を指定した文字数ごとに分割する

今日は Windows マシンから更新。

 cf. ruby 文字列を指定数で分割する – それマグで!

Haskell でやってみた。

^o^ > runhaskell stringSlices.hs
["abc","def","ghi","jkl","mno","pqr","stu","vwx","yz"]

Scheme だとこう。

^o^ > gosh string-slices.scm
(abc def ghi jkl mno pqr stu vwx yz)

最後に JavaScript。

^o^ > node stringSlices.js
[ 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz' ]

これ、もうちょっとスマートにいかないかな。

[追記]

JavaScript 版、Haskell 版や Scheme 版と同じように考えてみた。少しはスマートになったかな。そうでもないか?

^o^ > node stringSlices2.js
[ 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz' ]

scanlでフィボナッチ数列

たまには Haskell のエントリを。

昨日、unfoldr の使い方を調べてるときに気づいたんだけど、scanl を使ってもフィボナッチ数列を作れる。Haskell だから当然無限リストだ。

Prelude> let fib = scanl (+) 0 (1:fib)
Prelude> take 20 $ fib
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]

これは以前書いた zipWith を使うやつよりももっと簡単。

Haskellでランダムな文字列を得る

先日のお題を、今度は Haskell でやってみた。Haskell はだいぶ忘れてるな。
乱数の使い方は↓ここを参考にした。
cf. haskell で乱数 – はわわーっ

実行結果:

^o^ > runhaskell randomString.hs 20
GhDADFMuNNxrUBbpMXw3

Luhnアルゴリズムでクレジットカードの番号をチェック:Haskell版

こないだやったLuhnアルゴリズムでのチェックをHaskellでもやってみた。

実行結果:

^o^ > runhaskell checkCardNumber.hs
True
True
True
True
True
True
True
True
True
True
True
True
True

suffix array ってのは

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

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

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

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

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

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

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

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

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

課題1-1

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

実行例:

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

課題1-2

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

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

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

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

実行例:

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

課題1-3

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

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

実行例:

^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から変えたとこだけ:

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

実行例:

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

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

急勾配の判定

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

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

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

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

実行結果:

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

-1 を 10 で割ったあまりは?

どう書く?org のこのお題,はじめはHaskellで書いた。

すでに投稿があったのでOCamlで書き直したんだけど,そのまま移植したんではうまくいかない。

# let modular n l h = l + n mod (h - l + 1);;
val modular : int -> int -> int -> int = <fun>
# modular (-1) 100 200;;
- : int = 99

しばらく悩んだけど,要するに mod の引数に負数が現れた場合の振る舞いが Haskell と OCaml で違う。思わぬ盲点だよな。

Haskellの場合:

Prelude> mod (-1) 10
9
Prelude> mod 1 (-10)
-9

OCamlの場合:

# (-1) mod 10;;
- : int = -1
# 1 mod (-10);;
- : int = 1

さて,算術的にはどっちが正しいんだろうか。

Problem 31

今日は Problem 31。

 cf. Project Euler – Problem 31
 cf. Life Goes On – 31問目

id:rst76さんのをちょっと改良して1pのコインがない場合にも対応できるようにしてみた。問題の解答には必要ないんだけど。

^o^ >runhaskell euler031.hs
73682

1pのコインがない場合:

*Main> euler031 [200,100,50,20,10,5,2] 200
1784