人気ブログランキング | 話題のタグを見る

おさらい その2

Haskell で文字の並べ替えをやってみた。

a, b, c という3つの文字がある時その並べ方を全て調べるにはどうしたら良いだろうか。とりあえずは、先頭に置く文字を選ぶだろう。

先頭の文字 -> a

次に a に続く文字を選ぶことになるが、a は使ってしまったので次に使えるのは b と c だ、この時 b を選んだとすると、

2番目までの文字列 -> ab

となる。次に3番目の文字を選ぶわけだが、これば c だけしかないので結局文字の並べ方の一つは、

3文字の並べ方のひとつ -> abc

となる。先頭の文字が a の場合について更に考えると、2番目が c の場合もある。その場合は3番目が b に決定するので、

3文字の並べ方のもう一つの候補 -> acb

となる。

先頭が a の場合の並べ方はこの2つだけだが先頭の文字が b の場合もある。

先頭の文字が b の場合 -> bac, bca

同じように先頭の文字が c の場合は

先頭の文字が c の場合 -> cab, cba

結局考えられる並べ方は、abc, acb, bac, bca, cab, cba の6通りになる。

これをこのままの考え方で Haskell にやらせてみようというのが目論見だ。

先ず文字の集合だが、これは ['a', 'b', 'c', 'd'] というリストにする。

Prelude> let charSet = ['a', 'b', 'c', 'd']

この文字のセットから一文字を取り出す方法は、Haskell の内包的定義を使うと次のようになる。

Prelude> [x| x <- charSet]
"abcd"

"abcd" は Haskell では ['a', 'b', 'c', 'd'] と同じことだ。これは charSet のなかから一文字を選ぶ方法を全て試してリストにしたことになる。このリストは charSet と同じになってしまうので、"abcd" の文字列のうち先頭の文字を除外したもののリストを作ってみる。リストから特定の要素を除外する関数は Data.List モジュール の delete だ。

Prelude> :m +Data.List
Prelude Data.List> delete 'a' "abcd"
"bcd"

このdelete を利用すれば ['a', 'b', 'c', 'd'] の中から一文字を取り去った文字セットは次のようにして列挙することができる。

Prelude Data.List> [delete x charSet| x <- charSet]
["bcd","acd","abd","abc"]

そうすると、['a', 'b', 'c', 'd'] から一文字を取って、その後ろに残りの文字を並べたものは次のようにして得ることができる。

Prelude Data.List> [x : (delete x charSet)| x <- charSet]
["abcd","bacd","cabd","dabc"]

そこで、これまでのことを踏まえて、文字列 xs を並べ替える関数 perm の the recursive case (再帰的定義) を考えると次のようになる。

perm xs = concat [map (x:) perm (delete x xs) | x <- xs]

たとえば、

perm "abc"
= concat [(map ('a':) perm "bc"]), (map ('b':) perm "ac"), (map ('c':) perm "ab")]
= concat [["abc", "acb"], ["bac", "bca"], [ "cab", "cba"]]
= ["abc", "acb", "bac", "bca", "cab", "cba"]

となる。'a', 'b', 'c' それぞれについて文字列のリストがあるので、最後に concat を使って、リストのリストを単なるリストに変換しておく。

the base case がないと再帰的定義は働かないので、

perm [] = [[]]

とする。perm の値は ["abc", "acb", .. ] のようなリストのリストになるはずなので、[[]] で型の整合性をとっておく必要がある。

Prelude Data.List> let perm [] = [[]]; perm xs = concat [map (x:) (perm (delete x xs))| x <- xs]
Prelude Data.List> perm "abcd"
["abcd","abdc","acbd","acdb","adbc","adcb","bacd","badc","bcad","bcda",
"bdac","bdca","cabd","cadb","cbad","cbda","cdab","cdba","dabc","dacb",
"dbac","dbca","dcab","dcba"]

再帰的定義の時に concat を使ったり perm [] の値を [[]] にするなどの細かい調整は必要だが、ほとんど抽象的な考察をそのままプログラムにすることができるのがわかる。

このプログラムの場合、「"abcd" の文字セットからひとつ文字を取り出す方法を列挙する」という抽象的な考察は、

[x| x <- "abcd"]

という内包的定義に置き換えることができる。

プログラムを作るときの抽象的な考察はある程度パターン化しているので、この抽象的パターンと Haskell のプログラムとの対応を知っていると、抽象的な議論を逐語的に Haskell のプログラムにすることができる。
by tnomura9 | 2012-06-02 01:10 | Haskell | Comments(0)
<< RWH の読み方(49) 第6章 おさらい >>