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

去年の12月に2つの文字列のレーベンシュタイン距離を求めるっていうのを、JavaScriptHaskell でやった。もともとは Python での実装を参考に2次元配列を使ってやってみたもので、JavaScript版はともかく Haskell版は2次元配列の更新に苦労した。
それが、今日ふと1次元配列でやってみたらどうだろうを思いついた。
つまりこうだ。(m + 1)行×(n + 1)列(m、n は比較する文字列2つの長さ)の各行をつなげた1次元配列を考えて、2次元配列の時の座標を表すタプル (i, j) で初期化しておく。0 < i, 0 < j のとき、(i, j) の値はひとつ左(i-1, j)、ひとつ上(i, j-1)、左上(i-1, j-1)から決まるから、これを1次元配列のインデックスに直すと次のようになる:

  • ひとつ左: i * (n + 1) + j – 1
  • ひとつ上: (i – 1) * (n + 1) + j
  • 左上: (i – 1) * (n + 1) + j – 1

これをコードに落としこんでやるとこうなった:

結果はこうだ。

takatoh@apostrophe $ runhaskell ld2.hs apple play
4
takatoh@apostrophe $ runhaskell ld2.hs perl pearl
1

OK、うまくいった。

だけど、上のコードはまだ2次元配列の意識を引きずっている。もっと単純にできるはずだ。1次元配列のインデックスを x とすると:

  • ひとつ左: x – 1
  • ひとつ上: x – (n + 1)
  • 左上: x – (n + 1) – 1

となる。これで一般部については2次元配列を気にしなくて良くなった。ただし問題がある。いちばん上の行(第0行)といちばん左の列(第0列)だ。少し考えて、x を (n + 1) で割った商と余りを使えばいいと気がついた。コードにするとこう:

1行だけだけど長くなってしまった。だけど考え方はシンプルのように思う。実行してみよう。

takatoh@apostrophe $ runhaskell ld3.hs apple play
4
takatoh@apostrophe $ runhaskell ld3.hs perl pearl
1

OK。

2次元のリストの指定した座標を含むブロックの座標を列挙する

タイトルがわかりにくいな。
ホントは図を描けばいいのかもしれないけど、まず、2次元のリストを考える。で、そのリストの中に3×3のブロックが並んでいると考えてほしい。今日やりたいのは、ある座標(インデックス、0始まり、2次元なので当然2つの整数)を与えたときに、その座標を含むブロックの全座標を列挙したいってこと。
最初、どうやったらいいか悩んだけど、出来てみれば案外簡単だった。

実行例:

takatoh@apostrophe $ runhaskell block.hs 4 2
[(3,0),(3,1),(3,2),(4,0),(4,1),(4,2),(5,0),(5,1),(5,2)]
takatoh@apostrophe $ runhaskell block.hs 1 5
[(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]

こんな感じ。

リストから要素を削除する

Haskell での話。リストから特定の要素を削除したくて、ググってみたけどそれらしい関数が見当たらない。需要がないはずがないと思いながらしばし考えて、filter を使えばいいということに思い当たった。
というわけでメモ。

Prelude> let delete x xs = filter (/= x) xs
Prelude> delete 3 [1..9]
[1,2,4,5,6,7,8,9]

[追記]

Data.List モジュールに delete という関数があった。探し方が悪いな。
でも、この関数は上のと違って、最初にマッチした要素しか削除してくれない。

Prelude> import Data.List
Prelude Data.List> delete 3 [1,3,2,3]
[1,2,3]

文字列を長さ1の文字列のリストに分割したい(Haskell編)

以前、Scheme では書いた。

 cf. 文字列を長さ1の文字列のリストに分割したい – blog.PanicBlanket.com

今日は Haskell でやってみよう。

Prelude> map (\ c -> [c]) "abcdefg"
["a","b","c","d","e","f","g"]

というわけで、とりあえず出来たわけだけどなんだか冗長できれいじゃない。
こんなふうじゃダメなんだろうか。

Prelude> map ([]) "abcdefg"

<interactive>:3:6:
    Couldn't match expected type `Char -> b0' with actual type `[a0]'
    In the first argument of `map', namely `([])'
    In the expression: map ([]) "abcdefg"
    In an equation for `it': it = map ([]) "abcdefg"

ダメだった。
いや、空リストに cons すればいいのか。

Prelude> map (:[]) "abcdefg"
["a","b","c","d","e","f","g"]

出来た。

Text.Parsecで固定長データをパースする(2)

一昨日の記事で、パーサの型も(一応)解った。なので、今度は Text.Parsecで固定長データをパースする で省いていたヘッダのパースをすることにする。さらに、パースしたデータをCSV形式のデータに変換する。

まずは、対象の地震動波形のファイルを再掲しておこう。

ヘッダは2行。1行目は地震動の名前、2行目はいくつかのパラメータで、ここで重要なのは「DT=0.010」の部分。DT は時刻刻み―つまりサンプリングレートで、0.01秒ごとにデータを記録していることを意味している。ほかのパラメータは今回は無視。

で、手始めに地震動を表すデータ型 Wave を作った。

それから、ヘッダを含む地震動ファイル全体をパースする関数 waveFile

waveFileWave を返すので、型は Parser Wave だ。

あとは、コード全体を示そう。

これで出来たはずだ。

実行例:

takatoh@apostrophe $ runhaskell parsewave4.hs data1.dat > result.csv
takatoh@apostrophe $ head result.csv
,Example wave 1
0.00,-0.05
0.01,-0.05
0.02,-0.05
0.03,-0.05
0.04,-0.06
0.05,-0.06
0.06,-0.06
0.07,-0.06
0.08,-0.06

OK。うまくいった。

Text.Parsecのパーサの型

前回 Text.Parsec の記事を書いてから、ひと月以上あいてしまった。なんか途中で書くモチベーションが下がったりもしたんだけど、今日は時間がとれたので書く。前回良くわからなかった、パーサの型についてだ。
ここ↓が参考になった。

 cf. Parsec3 におけるパーサーの型 – k16’s note

このページによると、

  • パーサの厳密な型シグネチャは ParsecT s u m a
    • s は抽象化された入力の型。この抽象化された入力をストリームという
    • u はパース時に好きな状態を格納しておく容器の型
    • m はモナド変換子にとって基盤となるモナド
    • a は出力の型

モナド変換子というのは、ここでは ParsecT のことで、正直なんだかよくわからない。
前回書いたコードにある wave パーサの場合、入力は文字列(String)、出力は少数点数のリスト([Double])で、m がモナドである必要があるから、次のようになる。

wave :: Monad m => ParsecT String u m [Double]

コード全体を載せると:

実行例:

takatoh@apostrophe $ runhaskell parsewave0.hs data0.dat > result0.txt
takatoh@apostrophe $ head result0.txt
-5.0e-2
-5.0e-2
-5.0e-2
-5.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-7.0e-2

話はさらに続く。
Text.Parsec.String には、次のような定義がある。

type Parsec s u = ParsecT s u Identity
type Parser = Parsec String ()

上は ParsecT のモナドに Identity を使ったもの、下はその Parsec の入力に String、容器に () を使ったものだ。これを使うと、前述の wave パーサの型は次のように簡潔に書ける。

wave :: Parser [Double]

コード全体を載せよう。

実行例:

takatoh@apostrophe $ runhaskell parsewave0a.hs data0.dat > result0a.txt
takatoh@apostrophe $ head result0a.txt
-5.0e-2
-5.0e-2
-5.0e-2
-5.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-7.0e-2

ふぅ、今日はここまで。

Text.Parsecで固定長データをパースする

仕事で地震動波形のファイルを扱うことがある。地震動波形ってのは、地震の加速度を数値化したもので、こんなふうなファイルになっている。

見てのとおりヘッダが2行あって、3行目以降に8桁の固定長データが続いている。
今回はこれを Text.Parsec を使ってパースしてみようってわけ。といっても最初はことを単純にするため、ヘッダを省略してデータの部分だけでやってみる。

Haskell のパーサコンビネータ Parsec には Parsec 2 相当の Text.ParserCombinators.Parsec と Parsec 3 相当の Text.Parsec がある。最近では Parsec 2 ではなく Parsec 3 (つまり Text.Parsec)を使え、ということのようなんだけど、Web で検索しても Text.ParserCombinators.Parsec ばかりで、結構苦労した。特にパーサの型がわからなかった。結局、各パーサの型を書くのをやめて、パースを実行する関数にだけ型を書いたら動いてくれた。書いたコードがこれ。

実行例:

takatoh@apostrophe $ runhaskell parsewave.hs data0.dat > result.txt
takatoh@apostrophe $ head result.txt
-5.0e-2
-5.0e-2
-5.0e-2
-5.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-6.0e-2
-7.0e-2

なんとか、うまく動いてくれた。

ちなみに、ヘッダのついた data1.dat を食わせるとこんなエラーになる。

takatoh@apostrophe $ runhaskell parsewave.hs data1.dat
"(unknown)" (line 1, column 1):
unexpected "E"
expecting digit

Haskellでリフル・シャッフル

こないだのリフル・シャッフルを Haskell でやってみた。

Prelude> concat $ zip [0,2,4,6,8] [1,3,5,7,9]

:2:10:
    Couldn't match type `(a1, b0)' with `[a0]'
    Expected type: [[a0]]
      Actual type: [(a1, b0)]
    In the return type of a call of `zip'
    In the second argument of `($)', namely
      `zip [0, 2, 4, 6, ....] [1, 3, 5, 7, ....]'
    In the expression:
      concat $ zip [0, 2, 4, 6, ....] [1, 3, 5, 7, ....]

あれ。そうか、zip はタプルのリストを返すんだっけ。

Prelude> zip [0,2,4,6,8] [1,3,5,7,9]
[(0,1),(2,3),(4,5),(6,7),(8,9)]

じゃあ、foldr を使ってみようか。

Prelude> foldr (\(x,y) acc -> x:y:acc) [] $ zip [0,2,4,6,8] [1,3,5,7,9]
[0,1,2,3,4,5,6,7,8,9]

うまくいった。
いや、zipWith のほうがいいか?

Prelude> concat $ zipWith (\x y -> x:y:[]) [0,2,4,6,8] [1,3,5,7,9]
[0,1,2,3,4,5,6,7,8,9]

intersperse

Haskell の Data.List モジュールに intersperse という関数がある。リストの要素の間に値を挿入する関数だ。

Prelude> import Data.List
Prelude Data.List> intersperse 0 [1..3]
[1,0,2,0,3]

これを自前で実装するとこうなる。

takatoh@apostrophe $ runhaskell intersperse.hs
[1,0,2,0,3]

素直な再帰関数だ。

Scheme ではどうだろうか。実は Gauche には intersperse が用意されているんだけど、自前で実装してみたらこうなった。

takatoh@apostrophe $ gosh my-intersperse.scm
(1 0 2 0 3)

Haskell のと違って末尾再帰になっているのは、まあ、それが身についていると言ってもいいのかな。

さて、ここまで書いてみて畳み込みが使えそうだと気がついた。

takatoh@apostrophe $ gosh my-intersperse2.scm
(1 0 2 0 3)

同様に Haskell で。

takatoh@apostrophe $ runhaskell intersperse2.hs
[1,0,2,0,3]

Haskell の場合は foldl を使うよりも、単純な再帰のほうが見やすい気がする。それに Haskell は非正格だから、リスト全体をたどる必要(それも2回も)のある前者よりも後者のほうが効率がいいのかも。

文字列間のレーベンシュタイン距離を求める(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