関数型プログラミングで解くリスト構造の初級問題-6問目- (約15分)

　関数型プログラミングによるリスト操作の練習問題の6問目です。問題は、OCaml公式ページのものを使いました。
　内容は、問題と答案です。答案の作成時間は、約15分でした。

問題6.

　所与のリストが回文構造を有するか否かを判断する関数is_palindromeを書け。

答案

基本的な考え方

　関数型プログラミングによるリスト操作の基本的な流れは、以下の1から3になります。
　　1. 引数のリストをheadとtailに分離する
　　2. tailを引数として再帰呼び出すると共に、その返り値とheadを適当に組み合わせる
　　3. 以上を引数のリストが停止条件に達するまで繰り返す

本問の解き方

　プログラムはさておき、まず回文構造を再帰的に定義します。
　・空リストは回文構造を有する
　・要素数nのリストが回文構造を有するとき、その先頭と末尾とから同じ要素を足してできる要素数n+2のリストは、回文構造を有する
　これらの定義だけだと奇数要素のリストが漏れるので、
　・要素数が1のリストは回文構造を有する
をさらに加えます。

停止条件
　以上から停止条件は、リストの要素数が1または0のときになります。

再帰呼び出し
　要素数2以上のリストが引数の場合、まず、リストを先頭の要素と、末尾の要素と、残りの中間部のリストに分割します。
　次に、先頭と末尾の要素が同じであるか判断します。同じでないならば上記の定義から回文構造を有しないのでfalseを返します。
　一方、同じときは、中間部のリストを再帰呼び出しの引数にして、その返り値を返します。

コード

let rec is_palindrome lisuto =
 let rec is_last sentou lisuto =
 match lisuto with
  | [] -> false
  | head::[] -> sentou = head
  | head::tail -> is_last sentou tail in
 let rec body_of lisuto =
 match lisuto with
  | [] | _::[] -> []
  | head::tail -> head::body_of tail in
 match lisuto with
  | [] | _::[] -> true
  | head::tail ->
   if is_last head tail then is_palindrome (body_of tail) else false

　is_lastは、sentouとlisutoを引数にとり、sentouがlisutoの末尾と同じであるか否か判断してブール値を返す関数です。

　body_ofは、リストを引数にとり、そのリストの末尾の要素を除いた残りのリストを返す関数です。
　この関数を引数tailに適用すると元のリスト(head::tail)の中間部が得られます。

---

感想

OCaml

　答案の骨子はすぐに思いつきました。
　しかし、末尾の要素を除いたリストを求める関数に難儀しました。
　はじめは、前回の反転関数revを用いてrev (tail_of (rev list)) （tail_ofはhead::tailのtailを返す関数）としたのですが、例外処理で引っかかりました。

　また、引数を末尾の要素と比較する関数last_ofもはじめは定義していませんでした。単に、末尾要素を返す関数lastを用いてhead = last tailとしたのですが、やはり例外処理で引っかかりました。
　
　これらの例外は、引数が空リストであるときに発生します。
　しかし、答案では、一番外側の関数で空リストを弾いています。
　そのため、上記の関数には空リストは渡らないのですが、コンパイラはそこまで賢くないようです。

　今流行りのAIならば、仕様の壁を越えてこれらの問題を解決するコードを書くのでしょう。AIすごい、信じればなんでも叶えてくれる。

まとめ

　今回は長くなったので、他の言語の答案は作成しませんでした。
　長くなった原因は、末尾要素に関連しています。OCamlは末尾要素の参照が簡単ではありません。
　むしろ、他の言語のほうが、添字による参照で末尾要素も簡単に扱えるので、もっと直感的で素直なコードになると思われます。

　今回は時間切れで力技で解きました、もっとエレガントな解答があるような気がします。負け惜しみではありません。ちょっと葡萄が酸っぱいだけです。

　次回は、第7問です。素麺の写真を見出しにしたいです。