lists of functions 1

[hep84]

hey guys, I am currently a noob to swi-prolog. I've been trying to figure out bunch of things and I was working on some questions in the beginner book I bought... I got stuck on some of them. I hope to get some help in here since this is one of the best ones I found.

remove_duplicates(+List, -NewList)
Succeeds with NewList equal to List with all the duplicates in List removed, leaving just a single copy of each distinct element in List (the order in which the elements appear in NewList does not matter). If List is not a list, it fails.

delete_first(+X, +List, -NewList)
Succeeds with NewList equal to List, with the first occurrence of X in List deleted. If X does not occur in the list List, succeeds with NewList equal to List. If List is not a list, it fails.

I appreciate the help... Thanks

 

[joel76]

remove_duplicates(+List, -NewList)

Remember that in Prolog (as in Lisp) à list is accessible via car and cdr ==> if L = [1, 2, 3], in Prolog you write L = [H | T] and H is unified with 1 and T with [2,3].
Now, to remove duplicates, you have to travel through List, element by element, and test if the element is in NewList or not.
If it is in NewList, you ignore it and carry on with Tail of List, if it is not, you add it to Newlist and carry on with Tail of the List and the new newList !

 

[hep84]

I got that basically I know but what I mean is that I couldn't figure out how to do this basically.

 

[joel76]

Typically, to work with a list your predicate should have 3 args
arg1 : the list to work with
arg2 : current result with the work on the list
arg3 : final result when the entire list had been travelled.

% first you must explain what you do when the list is empty
work([], CL, FL) :-
  <stuf with current list and final list>.

% Here, you use the current first element of the list
work([H | T], CL, FL) :-
   % what do you do with the current element
   stuf(H, CL, NCL),
   % now we work with he rest of the list
   work(T, NCL, FL).

 

[hep84]

is there a way for u to do it? I am clueless still. :/

 

[kahleen]

delete_first(Item, [Item | Rest], Rest) :- !.
delete_first(Item, [Head | Rest], [Head | NewRest]) :-
delete_first(Item, Rest, NewRest).



remove_duplicates(List, Result):-
remove_duplicates(List, [], Result).

remove_duplicates([], Result, Result).
remove_duplicates([Item | Rest], Current, NewRest) :-
member(Item, Current),!,
remove_duplicates(Rest, Current, NewRest).
remove_duplicates([Item | Rest], Current, NewRest) :-
append(Current, [Item], NewCurrent),
remove_duplicates(Rest, NewCurrent, NewRest).

 

[hep84]

ty haleen for help but can u explain a little bit for me please if thats not a problem.

 

[hep84]

sum(+List, -Sum)
Succeeds with Sum equal to the sum of all the entries on list. The empty list has sum 0, and if List is not a list of numeric values, sum fails or results in an error.

It is nearly close but I got this so far...

sum([], 0) :- !.

sum(N, N) :- number(N), !.

sum([H|T], N) :-
sum(H, N1),
sum(T, N2),
N is N1 + N2.

 

[kahleen]

sum([], 0) :- !.

sum(N, N) :- number(N), !.

sum([H|T], N) :-
sum(H, N1),
sum(T, N2),
N is N1 + N2.

It seems to be done! It does the job. The first and second clauses don't seem to be from the same family ... The first sum clause deals with lists (the empty list) while the second sum clause deals with numbers. It's not wrong, but i prefer to make predicates of the same kind deal with the same kind of objects (same semantic). In your case, that would be:

sum([], 0).
sum([H | T], N) :-
sum(T, N1),
N is H + N1.

Now for explaining the other code:

% if List = [Item | Rest] and we want to delete Item, the
% result is Rest

delete_first(Item, [Item | Rest], Rest) :- !.

% otherwise, the Head of the list should make it in the
% result (we don't remove it), but instead we perform
% deletion in the rest of the list
% so if List = [Head | Rest], then Result = [Head | NewRest]
% we don't delete Head but preserve it for the result

delete_first(Item, [Head | Rest], [Head | NewRest]) :-
delete_first(Item, Rest, NewRest).




% remove_duplicates with 2 arguments calls remove_duplicates
% with 3 arguments ... the second argument represents the
% current result, so we start with an empty list and
% populate it with items

remove_duplicates(List, Result):-
remove_duplicates(List, [], Result).








% if Item is in Current (the current result), then we don't
% want to put it again (we don't want duplicates)
% so Item must be skipped, so the recursive call
% will use Rest, the same Current list and the final result
remove_duplicates([Item | Rest], Current, NewRest) :-
member(Item, Current),!,
remove_duplicates(Rest, Current, NewRest).


% if Item is not in Current (the current result), then we
% want to put it there since it is the first occurence
% of Item
% the Current list is appended [Item] at the end and the
% recursive call will take Rest, Current + [Item] and
% the final result
remove_duplicates([Item | Rest], Current, NewRest) :-
append(Current, [Item], NewCurrent),
remove_duplicates(Rest, NewCurrent, NewRest).

% if the list becomes empty (we've made it through the end)
% then the value of the second parameter will be the same
% with the value of the third parameter, which is the
% desired result
remove_duplicates([], Result, Result).



% for example: remove_duplicates([1,2,3,1], [], Result)

-> will call remove_duplicates([2,3,1], [1], Result)
-> will call remove_duplicates([3,1], [1,2], Result)
-> will call remove_duplicates([1], [1,2,3], Result)
-> will call remove_duplicates([], [1,2,3], Result) -> the second list does not grow since 1 is already a member there

now since the first list is empty, the second list becomes the Result.

so Result = [1,2,3] ([1,2,3,1] without duplicates)

 

[hep84]

Thank you so much dude. I understand it way better now. It makes more sense than ever. I appreciate your time.

 

[hep84]

umm I got another one for ya man...

last_element(+List, -LastElement)
Succeeds with LastElement equal to the last element of List. If List is not a list or is empty, it fails.

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

any suggestions? :/

 

[kahleen]

% last_element is only defined for lists with one element or % more (not empty lists)


% if the list has one element (X), that is the last element
% of the list:

last_element([X], X).


% if the last element of a list T is X, then the last
% element of [_|T] is also X ... any element put in front
% of T will not modify the last element of T

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