list - 再帰および末尾再帰でリストから最後の2つの値を取得する方法は?

Question

last_two(LST,Y,Z) リストの最後の値を Z に代入し、最後から 2 番目の値を Y に代入する述語が必要です。どのように再帰的に行うことができますか? どうすれば末尾再帰でそれを行うことができますか? ありがとう！

これは末尾再帰を含むコードですが、より効率的にすることはできますか?

last2_2([_|[H1|[H2|T]]],Y,Z):-last2_2([H1|[H2|T]],Y,Z).

last2_2([H1,H2],H1,H2).

Answer 1

再帰的なケースを単純化できます。

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

これにより、各再帰ケースが高速になります（パターンマッチングが少なくなります）が、行き過ぎになり、最後の2つの要素を取得するためにバックトラックする必要があります。リストが長くなると（バックトラックの量はリストの長さに依存しないため）、これはおそらくより有益です。

これをさらに一歩進めて、再帰的なケースを次のように置き換えることができます。

last2_2([_,_|T],Y,Z):-last2_2(T,Y,Z).
last2_2([_,A,B],A,B).

ここで、再帰的なケースは一度に2つの要素を取り除き（パターンマッチングをいくらか犠牲にして）、奇数の長さのリストを処理するために2番目のベースケースが必要です。