Prolog List Exercises: Solutions & Explanations

Posted on Sep 13, 2024 in Medicine & Health

Prolog List Exercises

1.01 (*): Find the last element of a list

Predicate: my_last(X,L) – X is the last element of the list L.
Arguments: (element,list) (?,?)
Note: last(?Elem, ?List) is predefined

my_last(X,[X]).
my_last(X,[_|L]) :- my_last(X,L).

1.02 (*): Find the last but one element of a list

Predicate: last_but_one(X,L) – X is the last but one element of the list L.
Arguments: (element,list) (?,?)

last_but_one(X,[X,_]).
last_but_one(X,[_,Y|Ys]) :- last_but_one(X,[Y|Ys]).

1.03 (*): Find the K’th element of a list

The first element in the list is number 1.
Predicate: element_at(X,L,K) – X is the K’th element of the list L.
Arguments: (element,list,integer) (?,?,+)
Note: nth1(?Index, ?List, ?Elem) is predefined

element_at(X,[X|_],1).
element_at(X,[_|L],K) :- K > 1, K1 is K - 1, element_at(X,L,K1).

1.04 (*): Find the number of elements of a list

Predicate: my_length(L,N) – the list L contains N elements.
Arguments: (list,integer) (+,?)
Note: length(?List, ?Int) is predefined

my_length([],0).
my_length([_|L],N) :- my_length(L,N1), N is N1 + 1.

1.05 (*): Reverse a list

Predicate: my_reverse(L1,L2) – L2 is the list obtained from L1 by reversing the order of the elements.
Arguments: (list,list) (?,?)
Note: reverse(+List1, -List2) is predefined

my_reverse(L1,L2) :- my_rev(L1,L2,[]).

my_rev([],L2,L2) :- !. my_rev([X|Xs],L2,Acc) :- my_rev(Xs,L2,[X|Acc]).

1.06 (*): Find out whether a list is a palindrome

A palindrome can be read forward or backward; e.g. [x,a,m,a,x].
Predicate: is_palindrome(L) – L is a palindrome list.
Arguments: (list) (?)

is_palindrome(L) :- reverse(L,L).

1.07 (): Flatten a nested list structure

Predicate: my_flatten(L1,L2) – the list L2 is obtained from the list L1 by flattening; i.e., if an element of L1 is a list then it is replaced by its elements, recursively.
Arguments: (list,list) (+,?)
Note: flatten(+List1, -List2) is a predefined predicate

my_flatten(X,[X]) :- + is_list(X).
my_flatten([],[]).
my_flatten([X|Xs],Zs) :- my_flatten(X,Y), my_flatten(Xs,Ys), append(Y,Ys,Zs).

1.08 (): Eliminate consecutive duplicates of list elements

Predicate: compress(L1,L2) – the list L2 is obtained from the list L1 by compressing repeated occurrences of elements into a single copy of the element.
Arguments: (list,list) (+,?)

compress([],[]).
compress([X],[X]).
compress([X,X|Xs],Zs) :- compress([X|Xs],Zs).
compress([X,Y|Ys],[X|Zs]) :- X \= Y, compress([Y|Ys],Zs).

1.09 (**): Pack consecutive duplicates of list elements into sublists

Predicate: pack(L1,L2) – the list L2 is obtained from the list L1 by packing repeated occurrences of elements into separate sublists.
Arguments: (list,list) (+,?)

pack([],[]).
pack([X|Xs],[Z|Zs]) :- transfer(X,Xs,Ys,Z), pack(Ys,Zs).

% transfer(X,Xs,Ys,Z) Ys is the list that remains from the list Xs %    when all leading copies of X are removed and transferred to Z

transfer(X,[],[],[X]). transfer(X,[Y|Ys],[Y|Ys],[X]) :- X \= Y. transfer(X,[X|Xs],Ys,[X|Zs]) :- transfer(X,Xs,Ys,Zs).

1.14 (*): Duplicate the elements of a list

Predicate: dupli(L1,L2) – L2 is obtained from L1 by duplicating all elements.
Arguments: (list,list) (?,?)

dupli([],[]).
dupli([X|Xs],[X,X|Ys]) :- dupli(Xs,Ys).

1.15 (**): Duplicate the elements of a list a given number of times

Predicate: dupli(L1,N,L2) – L2 is obtained from L1 by duplicating all elements N times.
Arguments: (list,integer,list) (?,+,?)

dupli(L1,N,L2) :- dupli(L1,N,L2,N).

% dupli(L1,N,L2,K) :- L2 is obtained from L1 by duplicating its leading %    element K times, all other elements N times. %    (list,integer,list,integer) (?,+,?,+)

dupli([],,[],). dupli([_|Xs],N,Ys,0) :- dupli(Xs,N,Ys,N). dupli([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1, dupli([X|Xs],N,Ys,K1).

1.16 (**): Drop every N’th element from a list

Predicate: drop(L1,N,L2) – L2 is obtained from L1 by dropping every N’th element.
Arguments: (list,integer,list) (?,+,?)

drop(L1,N,L2) :- drop(L1,N,L2,N).

% drop(L1,N,L2,K) :- L2 is obtained from L1 by first copying K-1 elements %    and then dropping an element and, from then on, dropping every %    N'th element. %    (list,integer,list,integer) (?,+,?,+)

drop([],,[],). drop([|Xs],N,Ys,1) :- drop(Xs,N,Ys,N). drop([X|Xs],N,[X|Ys],K) :- K > 1, K1 is K - 1, drop(Xs,N,Ys,K1).

1.18 (**): Extract a slice from a list

Predicate: slice(L1,I,K,L2) – L2 is the list of the elements of L1 between index I and index K (both included).
Arguments: (list,integer,integer,list) (?,+,+,?)

slice([X|],1,1,[X]).
slice([X|Xs],1,K,[X|Ys]) :- K > 1, 
   K1 is K - 1, slice(Xs,1,K1,Ys).
slice([_|Xs],I,K,Ys) :- I > 1, 
   I1 is I - 1, K1 is K - 1, slice(Xs,I1,K1,Ys).

1.19 (**): Rotate a list N places to the left

Predicate: rotate(L1,N,L2) – the list L2 is obtained from the list L1 by rotating the elements of L1 N places to the left.
Examples:
rotate([a,b,c,d,e,f,g,h],3,[d,e,f,g,h,a,b,c])
rotate([a,b,c,d,e,f,g,h],-2,[g,h,a,b,c,d,e,f])
Arguments: (list,integer,list) (+,+,?)

:- ensure_loaded(p1_17).

rotate([],_,[]) :- !. rotate(L1,N,L2) :-    length(L1,NL1), N1 is N mod NL1, split(L1,N1,S1,S2), append(S2,S1,L2).

1.20 (): Remove the K’th element from a list

The first element in the list is number 1.
Predicate: remove_at(X,L,K,R) – X is the K’th element of the list L; R is the list that remains when the K’th element is removed from L.
Arguments: (element,list,integer,list) (?,?,+,?)

remove_at(X,[X|Xs],1,Xs).
remove_at(X,[Y|Xs],K,[Y|Ys]) :- K > 1, 
   K1 is K - 1, remove_at(X,Xs,K1,Ys).

1.21 (): Insert an element at a given position into a list

The first element in the list is number 1.
Predicate: insert_at(X,L,K,R) – X is inserted into the list L such that it occupies position K. The result is the list R.
Arguments: (element,list,integer,list) (?,?,+,?)

:- ensure_loaded(p20).

insert_at(X,L,K,R) :- remove_at(X,R,K,L).

1.22 (*): Create a list containing all integers within a given range

Predicate: range(I,K,L) – I <= K, and L is the list containing all consecutive integers from I to K.
Arguments: (integer,integer,list) (+,+,?)

range(I,I,[I]).
range(I,K,[I|L]) :- I < K, I1 is I + 1, range(I1,K,L).

1.23 (**): Extract a given number of randomly selected elements from a list

Predicate: rnd_select(L,N,R) – the list R contains N randomly selected items taken from the list L.
Arguments: (list,integer,list) (+,+,-)

:- ensure_loaded(p1_20).

rndselect(,0,[]). rnd_select(Xs,N,[X|Zs]) :- N > 0,     length(Xs,L),     I is random(L) + 1,     remove_at(X,Xs,I,Ys),     N1 is N - 1,     rnd_select(Ys,N1,Zs).