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

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