読者です 読者をやめる 読者になる 読者になる

これはインクリメンタル検索を作りたいのかな?

.NET

問題が面白かったので.

完全な問題文は提示されていませんが,推測するに,

検索対象となる文字列 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 に挑戦するモチベーションのひとつが,「こんなパターンマッチングを使いたい/自分で拡張したい」というものです.