multisets

On Tue, 4 Mar 2008, bart demoen wrote:
> On Tue, 04 Mar 2008 15:33:58 +0000, Matthew Huntbach wrote:
 

> Have you seen my first solution to the original problem ?

OK, I have now looked at it, and of course it's a fine pure logic
solution.

> Have you understood that the part of my second solution using findall was
> just an interface to something pure, using only lists (and not even
> arithmetic) ?

Yes, the point I'm trying to make is that I think novices are often
led to use these features prematurely, and I think that can often
lead to poor programming style.
 

> Can you please show Prolog code ?

I hadn't written the Prolog code, I was just thinking of how
I'd approach the problem, and writing down my first thoughts
on it. I think that was the point of the original question,
to ask how one goes about solving a problem ike this rather
than just to give a solution. I wanted to make the point
that there is nothing magical about Prolog with a problem like
this, and it's best to think of it in abstract terms rather
than in terms of programming language syntax. I didn't want
just to give Prolog code, since the whole point was to demonstrate
that the problem should be thought about in abstract terms, and
from that comes the Prolog program, almost naturally just putting
what was written in an abstract way into Prolog syntax.

But anyway, turning the points I expressed into Prolog,
and making it backtrack rather than return a list of solutions,
gives:

cardmulti(1,M,N,L) :- oneeach(M,N,L).
cardmulti(C,M,M,L) :- C>1,ctimes(C,M,L).
cardmulti(C,M,N,L) :- C>1,N>M,M1 is M+1,cardmulti(C,M1,N,L).
cardmulti(C,M,N,[M|L]) :- C>1,N>M,
C1 is C-1,cardmulti(C1,M,N,L).

oneeach(M,N,[M]).
oneeach(M,N,L) :- N>M,M1 is M+1,oneeach(M1,N,L).

ctimes(0,M,[]).
ctimes(C,M,[M|L]) :- C>0,C1 is C-1,ctimes(C1,M,L).

I'd actually write it with cuts to remove the > tests, but as I
said "pure logic" I thought I'd better fiddle it to make it cut free.
As I said, this is what I come up with when I'm not thinking
deeply about the problem, there may be a neater but less obvious
solution, I'll look at your first solution in more detail to
see if that's it.
 

> Why ?

Because these days I tend not to use Prolog. I was thinking
about how I'd solve the problem in, say a functional language
where there isn't backtracking, but I knew the same approach would
also give a Prolog solution, and the transformation from something
which ANDs together the solutions to something which ORs them
together isn't a big thing.

Matthew Huntbach

On Wed, 05 Mar 2008 11:40:16 +0000, Matthew Huntbach wrote:


> But anyway, turning the points I expressed into Prolog,
> and making it backtrack rather than return a list of solutions,
> gives:
>
> cardmulti(1,M,N,L) :- oneeach(M,N,L).
> cardmulti(C,M,M,L) :- C>1,ctimes(C,M,L).
> cardmulti(C,M,N,L) :- C>1,N>M,M1 is M+1,cardmulti(C,M1,N,L).
> cardmulti(C,M,N,[M|L]) :- C>1,N>M,
>    C1 is C-1,cardmulti(C1,M,N,L).
>
> oneeach(M,N,[M]).
> oneeach(M,N,L) :- N>M,M1 is M+1,oneeach(M1,N,L).
>
> ctimes(0,M,[]).
> ctimes(C,M,[M|L]) :- C>0,C1 is C-1,ctimes(C1,M,L).

The problem with this code is that it uses 1 as a base case for
the size of the multiset instead of the more natural 0.
The choice of the basis for the induction can be crucial for the elegance
of an inductive program (which includes all non-trivial definite Prolog
programs). In this case, it makes the difference between needing two
auxiliary predicates (oneeach/3 and ctimes/3), and not needing any at all.

If 0 forms the base case, you will arrive at my first program for multiset.

I grant your
> this is what I come up with when I'm not thinking deeply about the
> problem,
but your preaching on how to teach Prolog might come across more credible
when your programs reflect more of the beauty of your teaching principles.

Of course, if you turned into a functional programming adept - which is
fine by me - you might have no true message to comp.lang.prolog ?

Cheers

Bart Demoen

On 5 Mar, 21:11, bart demoen <b...@cs.kuleuven.be> wrote:
> On Wed, 05 Mar 2008 11:40:16 +0000, Matthew Huntbach wrote: 
> 
> 
> 
>
> The problem with this code is that it uses 1 as a base case for
> the size of the multiset instead of the more natural 0.
> The choice of the basis for the induction can be crucial for the elegance
> of an inductive program (which includes all non-trivial definite Prolog
> programs). In this case, it makes the difference between needing two
> auxiliary predicates (oneeach/3 and ctimes/3), and not needing any at all.=[/color
]

>
> If 0 forms the base case, you will arrive at my first program for multiset=[/color
]
.

Sure, your program is more elegant. I didn't claim mine was the most
elegant, I just claimed it was what first came to my head when given
the problem.

> I grant your> this is what I come up with when I'm not thinking deeply abo=[/color
]
ut the 
>
> but your preaching on how to teach Prolog might come across more credible
> when your programs reflect more of the beauty of your teaching principles.=[/color
]

>
> Of course, if you turned into a functional programming adept - which is
> fine by me - you might have no true message to comp.lang.prolog ?

My point is that the details of what language you use are less
imortant than a basic understanding of recursion. So, yes, the way I
suggested tackling it applies equally if programmed in a functional
language. The program you wrote too has a functional equivalent. The
message to comp.lang.prolog is don't start thinking of using special
Prolog techniques until you've mastered basic recursive thinking. So
many of the times when I glance at this newsgroup, that's the real
problem - it's not specific Prolog problems that novices are having,
but rather they're not yet comfortable with programming in a recursive
style.

Matthew Huntbach

NNTP-Posting-Host: frank.dcs.qmul.ac.uk
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-Trace: qmul 1204795193 16233 138.37.88.242 (6 Mar 2008 09:19:53 GMT)
X-Complaints-To: newsmaster@qmul.ac.uk
NNTP-Posting-Date: Thu, 6 Mar 2008 09:19:53 +0000 (UTC)
In-Reply-To: <pan.2008.03.05.21.11.23.430888@cs.kuleuven.be>
User-Agent: Alpine 1.00 (LRH 882 2007-12-20)
Bytes: 3833
Xref: number1.nntp.dca.giganews.com comp.lang.prolog:34020

On Wed, 5 Mar 2008, bart demoen wrote:
> On Wed, 05 Mar 2008 11:40:16 +0000, Matthew Huntbach wrote:
 

> The problem with this code is that it uses 1 as a base case for
> the size of the multiset instead of the more natural 0.
> The choice of the basis for the induction can be crucial for the elegance
> of an inductive program (which includes all non-trivial definite Prolog
> programs). In this case, it makes the difference between needing two
> auxiliary predicates (oneeach/3 and ctimes/3), and not needing any at all.
>
> If 0 forms the base case, you will arrive at my first program for multiset
.
>
> I grant your 
> but your preaching on how to teach Prolog might come across more credible
> when your programs reflect more of the beauty of your teaching principles.
>
> Of course, if you turned into a functional programming adept - which is
> fine by me - you might have no true message to comp.lang.prolog ?

Looking more closely at your code, the only difference between yours and
mine is that I prematurely put in base cases. I could, and should, have
pushed down the recursion one more level, then I wouldn't have needed the
auxiliary predicates, giving (written in my style):

cardmulti(0,M,N,[]).
cardmulti(C,M,N,L) :- C>0,N>=M,M1 is M+1,cardmulti(C,M1,N,L).
cardmulti(C,M,N,[M|L]) :- C>0,N>=M,
C1 is C-1,cardmulti(C1,M,N,L).

Fine, good point, but this is NOT a logic v. functional programming issue
as you seem to be suggesting. Exactly the same point would have applied
had it been solved functionally. So you have actually proved my point
here - there is not a specific Prolog thing that makes the elegance of
this particular program, rather it's about being able to think recursively.

Matthew Huntbach

On Thu, 06 Mar 2008 09:19:52 +0000, Matthew Huntbach wrote:

> On Wed, 5 Mar 2008, bart demoen wrote: 
[...]
> Looking more closely at your code, the only difference between yours and
> mine is that I prematurely put in base cases. I could, and should, have
> pushed down the recursion one more level, then I wouldn't have needed the
> auxiliary predicates

Really ? You certainly have a way to repeat someone elses argument :-)

>
> Fine, good point, but this is NOT a logic v. functional programming issue
> as you seem to be suggesting.

I haven't brought up the functional issue at all: you did.


> So you have actually proved my point
> here - there is not a specific Prolog thing that makes the elegance of
> this particular program

Where did you actually make that point explicitly ? I must have missed it
completelely, but of course, I would like to know/where when the (or
rather your) point I proved, was stated. You see, I don't particularly
enjoy proving other people's point when I am not even aware of their
point.

Cheers

Bart Demoen

Bart Demoen schrieb:
> Stephan Lukits wrote:
> 
>
>
> [... very interesting remarks about the above demand ...]
>

Hi, sorry because the late reply. I was and still am pretty
busy.  Thanks a lot for your essay.

Best Regards
Stephan