Prolog - List Symmetry

Author

List Symmetry

Chui Tey

2007-09-17, 8:09 am

Day #2 with Prolog. All my code is write-only. I can hardly figure out
what I was doing 10 minutes ago.

Problem statement:

height(martha, 165).
height(ben, 165).
height(mark, 170).
height(sue, 170).
height(britt, 175).
height(herb, 175).

I want to take photos in groups of 5 such that their heights are
symmetrical. e.g.

[
height(martha, 165),
height(mark, 170),
height(britt, 175),
height(sue, 170),
height(ben, 165)
]

Question:

1. How to I frame this constraint in Prolog?
2. Right now I'm using hardcoded variables, like H1, H2, H3. Is there
some kind of array structure I could use?

Regards

Chui

Chui Tey

2007-09-17, 7:09 pm

Regarding Question #1.

The prolog palindrome tutorial gets me 50% of the way there:

http://www2.dcs.hull.ac.uk/NEAT/dnd.../tutorial2.html

But how do I use a different comparator?

Markus Triska

2007-09-17, 10:06 pm

Chui Tey <teyc@cognoware.com> writes:

> I want to take photos in groups of 5 such that their heights are
> symmetrical. e.g.

With SWI-Prolog's library(pairs), you can query for example:

?- findall(N-H, height(N,H), NHs0), permutation(NHs0, NHs1),
length(NHs, 5), append(NHs, _, NHs1), pairs_values(NHs, Hs),
reverse(Hs, Hs).

Yielding:

%@ NHs = [ben-165, sue-170, britt-175, mark-170, martha-165],
%@ NHs = [sue-170, ben-165, britt-175, martha-165, mark-170],
... etc.

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

Chui Tey

2007-09-18, 8:06 am

> ?- findall(N-H, height(N,H), NHs0), permutation(NHs0, NHs1),
> length(NHs, 5), append(NHs, _, NHs1), pairs_values(NHs, Hs),
> reverse(Hs, Hs).
>

Thanks! More questions Markus:

#1:

findall(+Template, +Goal, -Bag)

What's the +Template mean? For a moment, I thought that +Goal meant 1
or more goals. But then seeing +Template has really got me stumped.

#2:

I take it that:

length(NHs, 5), append(NHs, _, NHs1),

is idiomatic prolog for list truncation. It's pretty non-obvious
though.

#3:

Why is it that in SWI-prolog

apropos("pairs_values") doesn't show up anything?

#4:

How is a pair operator '-' different from the list operator '.'?

?- display(key1-value1).
-(key1, value1)

?- display([key1, value1]).
.(key1, .(value1, []))

Jan Wielemaker

2007-09-18, 7:15 pm

On 2007-09-18, Chui Tey <teyc@cognoware.com> wrote:
> #3:
>
> Why is it that in SWI-prolog
>
> apropos("pairs_values") doesn't show up anything?

Because SWI-Prolog is switching its documentation practice. Older
versions used only LaTeX as documentation source. Recent versions
provide PlDoc based on literate programming (documentation in the
source). There is not yet a bridge from PlDoc to the LaTeX source.
PlDoc however does read the LaTeX generated HTML from the manuals,
so you can browse the unified view from

http://gollem.science.uva.nl/SWI-Prolog/pldoc/

This is currently the information source of choice.

--- Jan

Chip Eastham

2007-09-18, 7:15 pm

On Sep 18, 9:48 am, Jan Wielemaker <j...@nospam.ct.xs4all.nl> wrote:
> On 2007-09-18, Chui Tey <t...@cognoware.com> wrote:
>
>
>
>
> Because SWI-Prolog is switching its documentation practice. Older
> versions used only LaTeX as documentation source. Recent versions
> provide PlDoc based on literate programming (documentation in the
> source). There is not yet a bridge from PlDoc to the LaTeX source.
> PlDoc however does read the LaTeX generated HTML from the manuals,
> so you can browse the unified view from
>
> http://gollem.science.uva.nl/SWI-Prolog/pldoc/
>
> This is currently the information source of choice.
>
> --- Jan

Minor fix to the documentation, Jan:

> pairs_values(+Pairs, -Values)
>
> Remove the keys from a list of Key-Value pairs.
> Same as pairs_keys_values(Pairs, Keys, _)

Last sentence should be:

> Same as pairs_keys_values(Pairs, _, Values)

regards, chip

Jan Wielemaker

2007-09-18, 7:15 pm

On 2007-09-18, Chip Eastham <hardmath@gmail.com> wrote:[color=darkred]
> Minor fix to the documentation, Jan:
>
>
> Last sentence should be:
>

Thanks. Fixed in CVS version.

--- Jan

Markus Triska

2007-09-18, 7:15 pm

Chui Tey <teyc@cognoware.com> writes:

> length(NHs, 5), append(NHs, _, NHs1),
>
> is idiomatic prolog for list truncation. It's pretty non-obvious

It's pretty obvious if you read it exactly as written: NHs is a list
of length 5, and it is a prefix of NHs1.

If you need this kind of operation frequently, look for better ways to
represent your data. For example, check out the "rope" data type:

http://stud4.tuwien.ac.at/~e0225855...cfp2007/rope.pl

In your example, one can do much better with plain lists too:

photo(Ns) :-
findall(N-H, height(N,H), NHs0),
length(Ns, 5),
group(Ns, Hs, NHs0),
reverse(Hs, Hs).

group([], [], _).
group([N|Ns], [H|Hs], NHs0) :-
select(N-H, NHs0, NHs1),
group(Ns, Hs, NHs1).

%?- photo(Ps).
%@ Ps = [martha, mark, ben, sue, mary] ;
%@ Ps = [martha, mark, britt, sue, ben] ;
%@ Ps = [martha, mark, britt, sue, mary] a
%@ ... etc.

Try a query like ?- time((photo(_),fail))). and analogously for the
other query to see that this solution is much faster (find out why!).
There is still a lot of room for improvement of course (improve it!).

> How is a pair operator '-' different from the list operator '.'?

To start with, '.' is no operator at all in SWI:

?- current_op(P, T, .).
%@ No

whereas '-' is both a unary prefix and binary infix operator:

?- current_op(P, T, -).
%@ P = 200,
%@ T = fy ;
%@ P = 500,
%@ T = yfx ;
%@ No

You can use both as functors to represent your data as Prolog terms.
For example, you could represent a group of 2 people as a term like:

?- Group = -(mary, -(martha, -)).
%@ Group = mary- (martha- (-))

ar as

?- Group = -(mary, -(martha, end_of_group)).
%@ Group = mary- (martha-end_of_group)

In your case, a group always has 5 members, so you could use:

?- Group = -(mary, martha, herb, britt, ben).
%@ Group = -(mary, martha, herb, britt, ben)

i.e., a single term with functor '-' and arity 5.

I used lists to represent groups since several operations used in the
query are already provided as built-ins *for lists*. Using a different
representation would entail rolling your own versions of them.

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

Chip Eastham

2007-09-18, 7:15 pm

On Sep 18, 8:59 am, Chui Tey <t...@cognoware.com> wrote:

> #1:
>
> findall(+Template, +Goal, -Bag)
>
> What's the +Template mean? For a moment, I thought that +Goal meant 1
> or more goals. But then seeing +Template has really got me stumped.

The SWI-Prolog Predicates documentation uses + to prefix arguments
required to be instantiated/bound for "input". Likewise - denotes
an argument that is supposed to be free/unbound for "output" when
calling the predicate.

http://gollem.science.uva.nl/SWI-Pr...l/preddesc.html

In many cases the implementation is more polymorphic than
such a strict designation can accomodate, so there are
a few additional prefixes used in the documentation.

regards, chip

Chui Tey

2007-09-19, 4:26 am

> Try a query like ?- time((photo(_),fail))). and analogously for the
> other query to see that this solution is much faster (find out why!).
> There is still a lot of room for improvement of course (improve it!).
>

Great! I haven't had this much fun since uni days.

running against a slightly larger set of data gives ...

Original:
298,405 inferences, 0.16 CPU in 0.16 seconds (100% CPU, 1912853 Lips)

Groups:
26,000 inferences, 0.02 CPU in 0.02 seconds (100% CPU, 1625000 Lips)

However:
The number of results aren't the same. One return 144, the other 72

?- findall(L, photos1b(L), Bag), length(Bag, Len).

Bag = [[ben-165, mark-170, mary-168, sue-170, martha-165]
, ben-165, mary-168, martha-165, sue-170], [martha-165, m
168, ... -...|...], [sue-170, martha-165, ... -...|...],
Len = 144 ;

?- findall(L, photos2(L), Bag), length(Bag, Len).

Bag = [[martha, mark, mary, sue, ben], [martha, m
ry, mark, ben], [martha, sue, britt, mark|...], [
..],
Len = 72 ;

I suppose it's mirror image at work here... didn't check.

Incidentally, reordering the original query gave marginally faster
results

photos1c(ListP):-
%
% NH1 = [N-H for N-H in height(N, H)]
findall(N-H, height(N, H), NH1),
%
% truncate it to 5 elements
length(NH3, 5),
append(NH3, _ , NH2),
%
% fetch one of the possible permutation
permutation(NH1, NH2),
%
% require heights are palindromes
pairs_values(NH3, H3),
reverse(H3, H3),
%
ListP = NH3.

111,925 inferences, 0.06 CPU in 0.06 seconds (100% CPU, 1776587 Lips)

> There is still a lot of room for improvement of course (improve it!).

Ouch, profile/1 is not supported on Windows.

I tried different tweaks (like passing the length 5 into group(), but
it just got worse.
Perhaps I need a tail-recursive version of group().
What do I need to know to understand profiling?

Markus Triska

2007-09-19, 4:26 am

Chui Tey <teyc@cognoware.com> writes:

> I suppose it's mirror image at work here... didn't check.

It's much "worse": The original query can yield the exact same
solution several times in a row (that's not wrong, only unnecessary).

> Perhaps I need a tail-recursive version of group().

group/1 is already tail recursive. Tail recursion only helps if your
predicate is deterministic; with enumeration tasks, it can even slow
you down. To see this, try the query with this alternative definition:

photo(Ns-Hs) :-
findall(N-H, height(N,H), NHs0),
length(Ns, 5),
group(Ns, Hs, NHs0, _),
reverse(Hs, Hs).

group([], [], NHs, NHs).
group([N|Ns], [H|Hs], NHs0, NHs) :-
group(Ns, Hs, NHs0, NHs1),
select(N-H, NHs1, NHs).

You can also write group/4 using DCGs, which frees you from explicitly
threading the state information and helps you focus on the essence:

group([], []) --> [].
group([N|Ns], [H|Hs]) --> group(Ns, Hs), select(N-H).

To further improve efficiency, *fail early*. You can detect much
sooner when a partial solution cannot be completed to a palindrome!

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

Jan Wielemaker

2007-09-19, 4:26 am

On 2007-09-19, Chui Tey <teyc@cognoware.com> wrote:
> Ouch, profile/1 is not supported on Windows.

SWI-Prolog profile/1 runs on Windows for quite a while. As you appear to
have bounds.pl, your copy is recent enough.

--- Jan

Chui Tey

2007-09-19, 8:06 am

On Sep 19, 5:36 pm, Jan Wielemaker <j...@nospam.ct.xs4all.nl> wrote:
> On 2007-09-19, Chui Tey <t...@cognoware.com> wrote:
>
>
> SWI-Prolog profile/1 runs on Windows for quite a while. As you appear to
> have bounds.pl, your copy is recent enough.
>
> --- Jan

Thanks Jan. I had been running the cygwin version, which was built
without profiler support. I've got the Windows version up and running
now. Yes, profile/1 runs!

> group([], [], NHs, NHs).
> group([N|Ns], [H|Hs], NHs0, NHs) :-
> group(Ns, Hs, NHs0, NHs1),
> select(N-H, NHs1, NHs).

Ouch. My head hurts. All the years doing imperative programming is no
help for figuring this out.
It reads like a web of assignments. It look a lot of staring before it
made sense!

Another question:

What's the idiomatic way to run some unit tests? I only know of one
way to test predicates - and that is in the toplevel. Is there some
way to test predicates in a file instead?

Chip Eastham

2007-09-19, 7:10 pm

On Sep 19, 8:42 am, Chui Tey <t...@cognoware.com> wrote:

> Another question:
>
> What's the idiomatic way to run some unit tests? I only know of one
> way to test predicates - and that is in the toplevel. Is there some
> way to test predicates in a file instead?

Here's a page on development tools for SWI-Prolog generally:

http://www.swi-prolog.org/IDE.html

As a simple means to your end, you can use the SWI-Prolog
engine to execute a script. See the note here:

http://gollem.science.uva.nl/SWI-Pr...04/q2/0503.html

regards, chip

Chip Eastham

2007-09-19, 7:10 pm

On Sep 19, 5:43 pm, Chip Eastham <hardm...@gmail.com> wrote:
> On Sep 19, 8:42 am, Chui Tey <t...@cognoware.com> wrote:
>
>
>
> Here's a page on development tools for SWI-Prolog generally:
>
> http://www.swi-prolog.org/IDE.html
>
> As a simple means to your end, you can use the SWI-Prolog
> engine to execute a script. See the note here:
>
> http://gollem.science.uva.nl/SWI-Pr...ve/2004/q2/0...
>
> regards, chip

Some explanation of how the script-style treatment of
command line options/arguments is dealt with on Windows
vs. Linux to maximize cross-platform compatibility is
given here (right below first brief section):

http://gollem.science.uva.nl/SWI-Pr...ompilation.html

--c

Sponsored Links