これはインクリメンタル検索を作りたいのかな?
問題が面白かったので.
完全な問題文は提示されていませんが,推測するに,
検索対象となる文字列 target に対して,検索文字列 search による検索を実装したい.
ここで,search の先頭からなるべく長く部分文字列を切り出して,その部分文字列が target に含まれている,というケースを考える.
という感じなのでしょうかね.
パターンマッチの練習がてら,Mathematica で解いてみました.
IncrementalSearch[target_String, search_String, ifNothing_: ""] := ReplaceList[ {Characters[search], Characters[target]}, {{Longest[x__: ifNothing], ___}, {___, x__: ifNothing, ___}} -> Hold[StringJoin[{x}]] ] // ReleaseHold // First
テスト.
In := IncrementalSearch["aaabbbcbc", "abbbcab"] Out := abbbc In := IncrementalSearch["aaabbbcbc", "xabbbcab"] Out := In := IncrementalSearch["aaabbbcbc", "xabbbcab", "not found"] Out := not found
軽く説明.
マッチング成功時に何が起きているかというと,まず検索文字列 pattern は文字のリストに分解されていて,さらに
{"a", "b", "b", "b", "c", "a", "b"} ^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^ x , ___
というふたつのパターンに分解されています.前者の内容は変数 x に束縛されます (一方向の単一化).
また,文字列 target も文字のリストに分解された上で,
{"a", "a", "a", "b", "b", "b", "c", "b", "c"} ^^^^^^^^ ^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^ ___ , x , ___
というみっつのパターンに分解されています.ここで x は先ほどと同じ内容です.
今回は Longest[x__: ifNothing] という形式を使っているため,
- x の長さが最長になるようにマッチされる (Longest)
- そのような x が見つからなかったときは x に ifNothing が割り当てられる (x__: ifNothing)
という動作をしています.
いかがでしょう.条件分岐やループを駆使して問題を解くのとは違う可能性を感じませんか?
うれしいのは,問題を解くという作業を「条件を書き下すこと」そのものに帰着できることです.C# 3.0 で LINQ を好きになった人なら,このうれしさに共感していただけるのではないかなと.
そして私が F# や Scala に挑戦するモチベーションのひとつが,「こんなパターンマッチングを使いたい/自分で拡張したい」というものです.