% length(L, N).
% Succeeds when N is the length of the list L. Examples:
% - length([A, B], N) unifies N with 2.
% - length(L, 3) unifies L with [_, _, _].

length([], 0).
length([H | T], N) :-
   length(T, M),  
   N = M + 1.

% nth(N, L, X).
% Succeeds when X is the Nth element of L (counting from 1).
% - nth(2, [A, B, C], X) unifies X with B.
% - nth(N, [7, 8, 9], 9) unifies N with 3.

nth(1, [H | _T], H).
nth(N, [_H | T], X) :-
    nth(M, T, X),
    N = M + 1.

% between(A, X, B).
% Succeeds when X is greater than or equal to A and lesser than or equal to B.
% - between(1, X, 4) unifies X with 1, then with 2, then with 3, then with 4.
% - between(2, X, 0) fails.
  
between(A, X, B) :-
   A <= B, (X = A ; between(A + 1, X, B)).

% reverse(L0, L1).
% Succeeds if L0 and L1 are two lists of the same length whose elements are in reverse order.
% - reverse(L0, [A, B, C]) unifies L0 with [C, B, A].
% - reverse([A, B, C], [E, F, G]) unifies C with E, B with F and A with G.

reverse(L0, L1) :-
   revappend(L0, [], L1).

% revappend(L0, L1, L2).
% Succeeds if L2 is the concatenation of the reverse of the list L0 and the list L1.

revappend([], L, L).
revappend([H | T], L0, L1) :-
   revappend(T, [H | L0], L1).

% append(L0, L1, L2).
% Succeeds if L2 is the concatenation of the lists L0 and L1.

append([], L, L).
append([H | T], L0, [H | L1]) :-
   append(T, L0, L1).

% select(X, L, T).
% Succeeds if X belongs to L and T is the list containing all the other elements of L but X.

select(X, [X | T], T).
select(X, [H | T0], [H | T1]) :-
   select(X, T0, T1).

% findall(X, G, L).
% Succeeds if L is the list of all the values of X that are obtained by enumerating all the
% successes of the goal G.

findall(X, G, L) :-
   g_assign(findall_accu, []),
   \+ (
      G,
      \+ (
         g_read(findall_accu, Accu),
         g_assign(findall_accu, [X | Accu])
      )
   ),
   dummy(G), % Hack to put vars(G) in the continuation for successes not to collapse 
   g_read(findall_accu, Accu),
   reverse(Accu, L).
  
dummy(_).