差分リストの練習 その４

prolog

split_at_right。Prologで作る数学の世界―Prologそして集合‐位相‐群の第五章の問題の回答でもある。

バックトラックを利用したもので、Nが小さい場合は効率がよい。現時点で一番prologらしいプログラム。

split_at_right(N, List, Left, Right) :-
        right_sub(List, [Left, []], Right, N), !.
split_at_right(_, List, [], List).
split_at_right_sub([Head | Rest],[Left, Tail], Right, N) :-
        [Left, Appender1] = [[Head | Appender1], Appender2],
        split_at_right_sub(Rest, [Appender2, Tail], Right, N).
split_at_right_sub(Rest, [Tail, Tail], Rest, N) :- length(Rest, N).

ところで

バックトラックで戻った回数を記憶する方法はあるんだろうか。それができればlengthで長さを比較する必要がなくなりさらに効率がよくなるのに。あまり考えなくてよいのだろうか？