99 Prolog Problems (http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/) as solved and explained by Daniel Dušek

99 Prolog Problems with explanation.pl

% #1
% Get last element from the list
% Explanation:
% Last element of list containing one element is the element
% Recursively call my_last on TAIL of the list, in rule head notice the underscore
% sign. We put it there because our rule body does not need to contain named 
% reference to the list head - in other words, we don't care about it.
my_last(X, [X]).             
my_last(X, [_|T]) :- my_last(X, T).


% #2
% Find the last but one element of the list
% Explanation:
% For the list of two elements, it is always the former one
% For the list of multiple elements, we decompose the list to "something, Y,
% and the rest", then recursively call my_last_but_one with newly created list
% of something 'infront' of the tail 'concatenated' with the tail.
% When reaching the last iteration, the last but one-th element is unified to X
% For underscore usage, same rules as for #1 apply
my_last_but_one(X, [X,_]).
my_last_but_one(X, [_,Y|T]) :- my_last_but_one(X, [Y|T]).


% #3
% Find the K'th element of a list, first element is 1st
% Explanation:
% When K=1, k-th element is always the list head
% When K>1, create new variable which value is instantiated to K-1 and another
% kth_element iteration is called on the tail of list
% For underscore usage, same rules as for #1 apply
kth_element(X, [Y|_], 1) :- X = Y.
kth_element(X, [_|T], K) :- K1 is K-1, kth_element(X, T, K1).


% #4
% Find the number of elements in list (standard length function)
% Explanation: 
% List containing 1 element has length of 1
% For longer lists, my_lnegth/2 is called recursively, each time on the tail of
% the list, where variable Temp stores current list lenght. It 'bubbles-down' to
% the base case of list containing one element and is instantiated to value 1, as
% it 'bubbles-up', it is increased in each iteration as 'X is Temp+1' is evaluated.
% For underscore usage, same rules as for #1 apply
my_length(1, [_]).
my_length(X, [_|T]) :- my_length(Temp, T), X is Temp+1. 


% #5
% Reverse a list, first argument is reversed list, second the list to be reversed
% Explanation:
% Here comes the new concept of accumulators, some reading on the subject here:
% http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25
% We create predicate my_reverse that takes two arguments, list that will contain
% reversed list and the list to be reversed. 
% We then create other predicate my_rev_acc/3 that takes care of reversing the  
% list using accumulator. This predicate takes three parameters (as the 
% previous one), but the middle parameter is so called accumulator. 
% Accumulator is initialized with empty list and then we proceed to tear up the
% list to be reversed - we put its head to the head of the accumulator, and put
% original accumulator as new tail of the accumulator - we (a)cumulate. Then
% we recursively call my_rev_acc/3 on the tail of the list to be reversed. Upon
% reaching the point where list to be reversed is empty, Accumulator and output
% list are unified and there we go, L1 contains reversed list.
% For underscore usage, same rules as for #1 apply
my_reverse(List1, List2) :- my_rev_acc(List1, [], List2).
my_rev_acc(List1, Acc, [H2|T2]) :- my_rev_acc(List1, [H2|Acc], T2).
my_rev_acc(Acc, Acc, []).


% #6
% Find out whether a list is a palindrom
% Explanation:
% "A palindrom is a list which reads the same backwards, so you can revese the 
% list to check whether it yields the same list".
% This is also kind of a new concept (from what we have seen so far), you have 
% to realize how Prolog really works. So far you probably only tried calling 
% predicates like my_reverse(X, [1,2,3]) and Prolog unified X for you, so you
% could see the reversed list. What you need to know is that Prolog unifies the
% X variable so that the clause is True. That means, that if we force unify value
% to wrong value, clause will fail and therefore we can easily check whether list
% is a palindrom by calling my_reverse/2 (or reverse/2) predicate and forcing it
% both parameters to be the list we want to check on being a palindrom.
palindrome(List) :- my_reverse(List, List).  % we could use built-in reverse/2


% #7
% Flatten a nested list structure
% Explanation:
% TODO: Fill the empty spot
my_flatten(ListOut, ListIn) :- my_flatten(ListOut, ListIn, []).
my_flatten([], Res, Res) :- !.
my_flatten([Head|Tail], Res, Cont) :-   !,
                                        my_flatten(Head, Res, Cont1),
                                        my_flatten(Tail, Cont1, Cont).
my_flatten(Term, [Term|Cont], Cont).