【LPN】6 More Lists

* 6 More Lists
** 1 Append
 - unificationは構造の構築にも使える。
 - そしてunificationで構造の構築を記述すると、構造
   の分解にも同じ述語を使える。これがすごい。

append([],L,L).
append([H|T],L2,[H|L3]) :-
        append(T,L2,L3).

?- append([a,b],[1,2],X).
X = [a, b, 1, 2].

?- append(X,Y,[a,b,1,2]).
X = [],
Y = [a, b, 1, 2] ;
X = [a],
Y = [b, 1, 2] ;
X = [a, b],
Y = [1, 2] ;
X = [a, b, 1],
Y = [2] ;
X = [a, b, 1, 2],
Y = [] ;
fail.

?- 

** 2 Reversing a List
 - Exercise 6.1.
   
   doubled(L) :- append(X,X,L).

   やっぱ頓知かな。

 - Exercise 6.2.

   parindrome(L) :- rev(L,X), L = X.

   これは簡単。

 - Exercise 6.3.
   
   toptail(I,[H,T]) :- append([H|_],[T],I).

   あ、仕様を読み間違えている。これはtopとtailから
   なるlistをつくる。正しくは、topとtail以外のlist
   をつくるのだから、、、、

   toptail([_|T],O) :- append(O,[_],T).

   頓知。

   具体的な入出力例をいろいろ書き下していみるのは、
   宣言的プログラミングでも効果的。

 - Exercise 6.4.

   lastRev(List,X) :- rev(List,[H|_]), H = X.

   lastRec([Y],X) :- Y = X.
   lastRec([_|T],X) :- lastRec(T,X).

 - Exercise 6.5.

   swapfl([H1|T1],[H2|T2]) :-
          append(X,[H1],T2),
          append(X,[H2],T1).
   
   backtrackするとappendがとまらないが。

   swapflRec([A,B],[B,A]).
   swapflRec([H1,C|T1],[H2,C|T2]) :-
        swapflRec([H1|T1],[H2|T2]).

   再帰は友達。

 - Exercise 6.6.


** Practical Session

 - 1.

  amember(X,L) :- append(_,[X|_],L).

  非効率的だろう。

 - 2.

  まず、こう書いた。

  set(_,[]).
  set(L,[H|T]) :- member(H,L), set(L,T).

  これは述語としては機能するが、構築には使えない。
  構築につかえる書きぶりはより宣言的でなければなら
  ない。

  set(L,S) :- setBuf(L,[],S).
  setBuf([H|T],B,S) :-
          member(H,B), setBuf(T,B,S);
          setBuf(T,[H|B],S).
  setBuf([],B,B).

  こちらは、構築にもつかえるが集合の要素の順番が異
  なるときの判定には対応していない。まあいいや。


 - 3.

  うーん。Common Lispならすぐ書ける。

(defun flatten (tree)
  (cond ((null tree) nil)
        ((atom (car tree)) (cons (car tree)
                                 (flatten (cdr tree))))
        (t (append (flatten (car tree))
                   (flatten (cdr tree))))))

  PrologのProof Searchで解がでるように宣言を考える
  ことにはどういう意味があるんだろう。もしそれに意
  味が無いならば、それはPrologのために考えているだ
  けであり、無意味になってしまうところがこわい。

  Prologが探索型開発に向かないのは、問題の分割がや
  りにくいからかな。

  自分において、その理由を考えてみるとHtDPのデザイ
  ンレシピが適用できないことがある。

  論理プログラミングのデザインレシピってつくれない
  のだろうか。。。

  とりあえず、flatten。

flatten([],[]).                                   /* トリビアルなケース。これ以降ちゃんとしたリストであることが保証される */
flatten([X],F) :- flatten(X,F).                   /* 余分な全体括弧を除去 */
flatten([[H]|T],F) :- flatten([H|T],F).           /* headの余分な括弧を除去 */
flatten([[LHH|LHT]|T],[FH|FT]) :-                 /* headが(意味のある)リストの場合 */
        flatten([LHH|LHT],[FH|XT]),flatten([XT|T],FT).
flatten([FH|LT],[FH|FT]) :- flatten(LT,FT).       /* headがリストではない場合 */

  こつとしては、はじめはrulesのheadはシンプルにし
  てbodyのunificationで分解していく。代入がごとく。
  そして動くものができたところで、unificationをま
  とめていき不要なvariablesを消す。こうすると多少
  探索的に書いていける。

  ただし、宣言的プログラミングはその正しさが判別し
  やすい、というが、上のflattenはとてもそうは思えな
  い。こういうケースもあるのか、私のflattenがいけ
  てないのか。

こんなもんでPons Asinorumを渡れたのかなぁ。。。

ふー。やっと折り返し地点。いくら初めての言語とはい
え、まったくの入門書なんだからもっとスピーディにい
かんもんかなぁ。頭がポンコツすぎる。

たかがポンコツ、されどポンコツ。