Coding problem

Help!
1

Hello,
I’m trying for a few hours to write a predicate with no success.
My predicate should get a list and an argument for the output parameter.
The final result in ‘Result’ supposed to contain only the items from the List who return true for ‘check_somting(Item)’

My code look like this:

check_somthing(1).
check_somthing(3).

do_somthing([], Result).

do_something([H|T], Result) :- 
    check_somthing(H),
    append(H, Result, Result),
    do_somthing(T, Result).

do_somthing([_|T], Result) :- do_something(T, Result).

Query:

do_somthing([1,2,3,4,5], Result).

Requested result:

Result = [1, 3]

I really appreciate any help.

2

Is this a homework problem?

3

It just mine problem.
I’m learning prolog by my self.

4

Let’s start with something simpler: copy one list to another:

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

This says that:

  1. The base case is: the copy of an empty list [] is an empty list [].
  2. For a non-empty list, the copy has the same head as the original and the copy_list predicate is true for the tails.

Do you understand this so far? You might want to run this with gtrace, e.g.:

?- debug, gtrace, copy_list([1,2,3], Copy).

(debug turns of “last call optimization” so that you can see the full trace)

If you understand this, then I’ll continue with how to modify this to copy only elements that satisfy a predicate.

5

That’s great way for debug :slight_smile:
Thank you.
So far I understand.
What is the next step?

6

Let’s take the 2nd clause of copy_list and modify it so that it only works if check_something(X) succeeds:

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

This will succeed for filter_copy_list([1,1,3,1], Copy), but will simply fail for filter_copy_list([1,4,3,1], Copy). (Try it and see)

So, we need to do something for the case where check_something(X) fails. This is done by adding a 3rd clause to filter_copy_list and it’s going to look something like this:

filter_copy_list([X|Xs], ...) :-
    \+ check_something(X),  % succeeds if check_something(X) fails
    filter_copy_list(Xs, ...).

What should go into the two ... place-holders in the 3rd clause?

For example, you could do the following to substitute '-' for each element that fails check_something, but that’s not quite what your original problem asked:

filter_copy_list([X|Xs], ['-'|Ys]) :-
    \+ check_something(X),  % succeeds if check_something(X) fails
    filter_copy_list(Xs, Ys).
1 Like
7

Very nice of you to help me like that.
I have few more questions :slight_smile:
In the 3rd clause, why do I check again the predicate?
What ‘…’ means?
Is there a way to return true and not fail?
and how eventually can I get only the items who satisfied the predicate without place holders?

A lot of questions…I know

8

I have an elegant solution:

check_something(1).
check_something(3).

filter_copy_list(List, Res) :-
setof(X, (member(X, List), check_something(X)), Res).

It looks fine?

9

Hi!

    	 moraneus

September 9
I have an elegant solution:

check_something(1).
check_something(3).

filter_copy_list(List, Res) :-
setof(X, (member(X, List), check_something(X)), Res).

It looks fine?

You should comprehend the basics first, before using something like
setof/3. It is a very simple recursion:

check_somthing(1).
check_somthing(3).

do_something([], []).

do_something([H|T], Result) :-
    (
        check_somthing(H)
    -> 
        do_something(T, Result1),
        Result = [H|Result1]
    ;
        do_something(T, Result)
    ).

Cheers,
Volker

1 Like
10

Thank you :slight_smile:
I’m only one week with Prolog…I tried to learn it by my self.
Can you explain to me the arrow meaning?
I saw this template, but I didn’t understand

11

It’s an if-then-else. “A -> B ; C” means “If A succeeds, then B else
C”. If A succeeds, variables in A will be bound and are visible in B.
If it doesn’t, they won’t be bound.

Semantically, “A -> B ; C” means the same as “A, B ; not(A), C”.

Technical details can be found here:
https://www.swi-prolog.org/pldoc/doc_for?object=(->)/2

Cheers,
Volker

1 Like
12

debug/0 indeed disables last call optimization, but gtrace/0 implies debug/0. In fact, LCO is controlled using the Prolog flag last_call_optimisation. Possibly we should use that to implement what SICStus calls zip mode: watch for spy points, etc. while running at nearly normal speed.

1 Like
13

Here is a (probably) better version:

do_something([], []).

do_something([H|T], Result) :-
    (
        check_somthing(H)
    -> 
        Result = [H|Result1],
        do_something(T, Result1)
    ;
        do_something(T, Result)
    ).

The two lines “Result = [H|Result1]” and “do_something(T, Result1)” are
interchanged in the new version. This (should) allow for tail recursion
optimization. But maybe SWI-Prolog is smart enough to do the
transposition by itself.

Cheers
Volker

1 Like
14

In library(apply) there are two predicates that basically do exactly that: include/3 and exclude/3. You can checkout out the implementation here:

1 Like
15

Yes, that’s clear tail recursion. I thought, mine was one, too. The two
branches of the is-then-else are both at the end of the predicate,
aren’t they? Here again:

do_something([], []).

do_something([H|T], Result) :-
    (
        check_somthing(H)
    -> 
        Result = [H|Result1],
        do_something(T, Result1)
    ;
        do_something(T, Result)
    ).

Is this recognized as a (or rather two) tail recursion(s), or is it
necessary to do it as you’ve pointed out?

Cheers,
Volker

1 Like
16

I guess the end result is the about the same. I shared the implementation from the standard library because re-implementing existing code is not a rewarding activity in some situations. Sometimes we do it on purpose but sometimes we just don’t know what is already out there; so I wanted to add a reference to what is already out there.

17

That’s right! :grinning: You often just don’t know what’s already there.

In my case, however, it’s meant as an example for moraneus, who is learning Prolog.

Cheers,
Volker

18

It’s not clear to me that this solves your problem, but your specification is ambiguous: “The final result in ‘Result’ supposed to contain only the items from the List who return true for ‘check_somting(Item)’”

If you mean that the resulting list should contain the items in the same order as in the original list, then it doesn’t do what you asked. You can fix that by changing setof to bagof. But even that won’t work for an empty list ([]). So, you should change the setof (or bagof) to findall.

However, there are subtleties about using findall rather than setof or bagof. At this stage of your study of Prolog, it’s difficult to discuss those issues: but just remember that findall can introduce subtle bugs into your code if not used properly.

Finally, while “elegant”, your solution is much less efficient than the classic solutions that don’t use setof/bagof/findall. Perhaps this isn’t important to you, but also consider that include(check_something, List, Res) is simpler and clearer.

(BTW, even though include/3 is in the library, it can be worth reimplementing it as a learning exercise.)

1 Like
19

Thank you for your detailed answer.
efficiency is also importent.
So if I understand you right, simple recursion (classic soluton) is better then my solution?

20

You can have things in the “database”, for example defined as facts or as multiple solutions for a rule. Those are generated one after the other upon backtracking. So for example, you can have a table of facts:

a(1).
a(2).
a(3).

This will have three solutions, if you query:

?- a(X).
X = 1 ;
X = 2 ;
X = 3.

You can also get the same without explicitly defining a table of facts:

?- between(1, 3, X).
X = 1 ;
X = 2 ;
X = 3.

Those two are the same as to how you get your “things” out of it: by backtracking.

Then, you can have a list of things, as in: [1, 2, 3]. This is now a compound term, a data structure.

(I am getting to it, don’t give up).

There are ways to move the things between the two representations. If you want to go from a simple data structure as the list to a sequence of solutions upon backtracking, you use member/2, like this:

?- member(X, [1, 2, 3]).

To go from solutions to a list, you use findall/3 or bagof/3 (or setof/3):

?- bagof(X, a(X), L).

I am guessing that @peter.ludemann was trying to say that there is no need to switch between the two representations in your case. In particular, this is a severe code smell:

?- findall(X, member(X, List), Xs).

(It can be bagof/3 or setof/3 instead of findall/3)

There might be valid reasons to do this, but this in most cases, you are just doing busywork without achieving anything of value. As a matter of fact:

setof(X, member(X, List), Xs).

is the same as:

findall(X, member(X, List), Xs0), sort(Xs0, X)

And if you have this:

setof(X, ( member(X, List), foo(X) ), Xs)

then this is going to give you the same result in less memory and almost certainly faster:

include(foo, List, Xs0), sort(Xs0, Xs)

or alternatively:

sort(List, Xs0), include(foo, Xs0, Xs)

PS: something to keep in mind. First, it is perfectly fine to use findall/3 and bagof/3 and setof/3 when you need them. I will not go into the gory detail of when you need them and how to use them correctly, this post was not supposed to be an article :slight_smile: Then, it is perfectly fine to use them as in the “severe code smell” example I gave above, especially if you know that you are dealing with a known, limited number of things. And finally, you will see online quite a bit of one-liners that use findall and bagof and setof like this. Again, this is fine. It becomes problematic when you have a lot of things, at that point your code will become slow, you will be running out of memory and so on.

4 Likes