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)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||