% File:   list.pl
% Author: Dilian Gurov, KTH CSC

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Föreläsning 2: Induktiva datatyper: Listor (inbyggd)
%
% - Listor
% - Strukturell induktion över listor
% - Strängar
%
% Läs boken: Brna, kap. 4, 6

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: listLength(L, N)
% Längden på en lista L, dvs antalet element N i listan. 
% Finns även inbyggd som length(L, N).

listLength([], 0).
listLength([_ | T], N) :- 
  listLength(T, NT), 
  N is NT + 1.

% Queries:
%
% ?- listLength([1, 2, 3], N).
% ?- listLength(L, 3).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: in(X, L) 
% Medlemstest som ska vara sant om och bara om X finns i listan L. 
% Finns även inbyggd som member(X, L).

in(H, [H | _]).
in(X, [_ | T]) :- in(X, T).

% Queries:
%
% ?- in(2, [1, 2, 3]).
% ?- in(4, [1, 2, 3]).
% ?- in(X, [1, 2, 3]).
% ?- in(2, Y).
% ?- in(2, L), in(1, L), in(3, L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: concatenate(X, Y, Z)
% Sant om Z är konkateneringen av listan X med listan Y.
% Finns även inbyggd som append(X, Y, Z).

concatenate([], Y, Y).
concatenate([HX | TX], Y, [HX | TZ]) :-
  concatenate(TX, Y, TZ).

% Queries:
%
% ?- concatenate([a, b], [c, d], X).
% ?- concatenate(X, [c, d], [a, b, c, d]).
% ?- concatenate(X, Y, [a, b, c, d]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: appendEl(X, L, NL)
% Lägg till elementet X till L (dvs i slutet), lägg svaret i NL.
% Strukturella induktionen är över listan L (dvs andra argumentet).

appendEl(X, [], [X]).
appendEl(X, [H | T], [H | Y]) :- 
  appendEl(X, T, Y).

% Queries:
%
% ?- appendEl(4, [1, 2, 3], X).
% ?- appendEl(2, X, [1, 2]).
% ?- appendEl(X, [1, 2], [1, 2, 3]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Exempel: rev(X, Y)
% Vända på en lista, med användning av appendEl.
% Finns även inbyggd som reverse(X, Y).

rev([], []).
rev([H | T], X) :-
  rev(T, RT), 
  appendEl(H, RT, X).

% Queries:
%
% ?- rev([1, 2, 3, 4], X).
% ?- rev(X, [1, 2, 3, 4]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% - Strängar
%
% Inbyggda predikatet atom_codes(X, Y) är sant när Y är strängen/heltalslistan 
% som motsvarar atomen X.
%
% Queries:
%
% ?- atom_codes(nisse, Y).
% ?- atom_codes(X, [110, 105, 115, 115, 101]).
% ?- atom_codes(nisse, Y), rev(Y, R), atom_codes(X, R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% - Sortering

permSort(X, Y) :- 
  permutation(X, Y), 
  sorted(Y).

permutation([], []).
permutation([E | X], Y) :- 
   permutation(X, Y1),
   append(Y2, Y3, Y1),
   append(Y2, [E | Y3], Y).

% Queries:
%
% ?- permutation([2, 3, 1], Y).

sorted([]).
sorted([X]).
sorted([X, Y | L]) :- 
   X =< Y, 
   sorted([Y | L]).

% Queries:
%
% ?- sorted([2, 3, 1]).
% ?- permSort([2, 3, 1], Y).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%