Prolog - Using difference lists to split a list

Author

Using difference lists to split a list

guygu3

2006-12-22, 8:04 am

Hi all,
I have been asked to write a pridicate using a difference list which
takes a list L and split it to the middle which in first half goes to
list L1 and the second goes to L2.
I have an idea how to do it with regular lists, but the slitest idea
about making it with difference lists.
Help!!!

guygu3

2007-01-06, 7:19 pm

guygu3 wrote:
> Hi all,
> I have been asked to write a pridicate using a difference list which
> takes a list L and split it to the middle which in first half goes to
> list L1 and the second goes to L2.
> I have an idea how to do it with regular lists, but the slitest idea
> about making it with difference lists.
> Help!!!

Ok guys,
Help me please.
the split I wrote is:

split(L-X,N-V,L-X,0).
split([X|Xs]-B,L1-A2,A3-C,N):-!,
N>0,
N1 is N-1,
split(Xs-B,[X|L1]-L1,A3-C,N1).

And this is the trace:

[trace] 72 ?- split([a,b,c,d|T]-T,L1-[],L2-[],2).
Call: (7) split([a, b, c, d|_G588]-_G588, _G593-[], _G596-[], 2) ?
creep
^ Call: (8) 2>0 ? creep
^ Exit: (8) 2>0 ? creep
^ Call: (8) _L177 is 2-1 ? creep
^ Exit: (8) 1 is 2-1 ? creep
Call: (8) split([b, c, d|_G588]-_G588, [a|_G593]-_G593, _G596-[], 1)
? creep
^ Call: (9) 1>0 ? creep
^ Exit: (9) 1>0 ? creep
^ Call: (9) _L203 is 1-1 ? creep
^ Exit: (9) 0 is 1-1 ? creep
Call: (9) split([c, d|_G588]-_G588, [b, a|_G593]-[a|_G593],
_G596-[], 0) ? creep
Exit: (9) split([c, d]-[], [b, a|_G593]-[a|_G593], [c, d]-[], 0) ?
creep
Exit: (8) split([b, c, d]-[], [a|_G593]-_G593, [c, d]-[], 1) ? creep
Exit: (7) split([a, b, c, d]-[], _G593-[], [c, d]-[], 2) ? creep

T = []
L2 = [c, d] ;
Redo: (9) split([c, d|_G588]-_G588, [b, a|_G593]-[a|_G593],
_G596-[], 0) ? creep
^ Call: (10) 0>0 ? creep
^ Fail: (10) 0>0 ? creep
Fail: (8) split([b, c, d|_G588]-_G588, [a|_G593]-_G593, _G596-[], 1)
? creep
Fail: (7) split([a, b, c, d|_G588]-_G588, _G593-[], _G596-[], 2) ?
creep

No.

Thnks.

Richard Szopa

2007-01-06, 7:19 pm

"guygu3" <guygu3@walla.co.il> writes:

>
> Ok guys,
> Help me please.
> the split I wrote is:
>
> split(L-X,N-V,L-X,0).
> split([X|Xs]-B,L1-A2,A3-C,N):-!,
> N>0,
> N1 is N-1,
> split(Xs-B,[X|L1]-L1,A3-C,N1).

You can do it in one step, and without the auxiliary variable. Think
about how should look the “first halve” and the “second halve”.

The first halve is just like the original list, but something has been
cut of its end. In terms of difference lists, this means adding
something at the beginning of the subtrahend (the second list in the
pair) and leaving the minuend (the first list of the pair) as it was.

The second halve is just like the original list, but something has
been cut off at its beginning. In terms of difference lists, this
means leaving the subtrahend as it was, and cutting something at the
beginning of the minuend.

You can easily determine how much should you cut using length and some
arithmetic functions.

I hope that my hints will help you.

Best regards,

-- Richard

guygu3

2007-01-06, 7:19 pm

Richard Szopa wrote:
> "guygu3" <guygu3@walla.co.il> writes:
>
>
> You can do it in one step, and without the auxiliary variable. Think
> about how should look the "first halve" and the "second halve".
>
> The first halve is just like the original list, but something has been
> cut of its end. In terms of difference lists, this means adding
> something at the beginning of the subtrahend (the second list in the
> pair) and leaving the minuend (the first list of the pair) as it was.
>
> The second halve is just like the original list, but something has
> been cut off at its beginning. In terms of difference lists, this
> means leaving the subtrahend as it was, and cutting something at the
> beginning of the minuend.
>
> You can easily determine how much should you cut using length and some
> arithmetic functions.
>
> I hope that my hints will help you.
>
> Best regards,
>
> -- Richard

Thanks, I'll try to think of it Richard.

Sponsored Links