Home > Archive > Prolog > February 2006 > removing items from a nested list.
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
removing items from a nested list.
|
|
|
| I am translating the Little Schemer into Prolog as a means of learning
the language.
rember*/3 produces a list with all occurrences of the 1st term removed
from the nested list provided in the 2nd tem.
rember*(Item,[],[]).
rember*(Item,[[Head]|Tail], Result) :-
rember*(Item,Head,Result),
rember*(Item,Tail,Result).
rember*(Item, [Item|Tail], Result) :-
rember*(Item,Tail,Result).
rember*(Item,[Head|Tail], Result) :-
rember*(Item,Tail,Result).
Now run with
rember*(cup,[[coffee],cup,[[tea],cup],[a
nd,[hick]], cup],Result).
I get
Result = [[coffee], [[tea], cup], [and, [hick]]]
I am running SWI Prolog.
Of course cup should not appear in the final result.
Can anyone help.
| |
| Nick Wedd 2006-02-08, 9:29 am |
| In message <1139139891.894853.140720@g44g2000cwa.googlegroups.com>,
wooks <wookiz@hotmail.com> writes
>I am translating the Little Schemer into Prolog as a means of learning
>the language.
>
>rember*/3 produces a list with all occurrences of the 1st term removed
>from the nested list provided in the 2nd tem.
>
>rember*(Item,[],[]).
>rember*(Item,[[Head]|Tail], Result) :-
> rember*(Item,Head,Result),
> rember*(Item,Tail,Result).
>rember*(Item, [Item|Tail], Result) :-
> rember*(Item,Tail,Result).
>rember*(Item,[Head|Tail], Result) :-
> rember*(Item,Tail,Result).
>
>Now run with
>
> rember*(cup,[[coffee],cup,[[tea],cup],[a
nd,[hick]], cup],Result).
>
>I get
>
>Result = [[coffee], [[tea], cup], [and, [hick]]]
>
>I am running SWI Prolog.
>
>Of course cup should not appear in the final result.
I haven't examined your code in detail. But
rember*(Item,[[Head]|Tail], Result) :-
rember*(Item,Head,Result),
rember*(Item,Tail,Result).
looks wrong. The two Results won't be the same, will they?
Nick
--
Nick Wedd nick@maproom.co.uk
| |
| Bart Demoen 2006-02-08, 9:29 am |
| wooks wrote:
> I am translating the Little Schemer into Prolog as a means of learning
> the language.
>
> rember*/3 produces a list with all occurrences of the 1st term removed
> from the nested list provided in the 2nd tem.
>
> rember*(Item,[],[]).
> rember*(Item,[[Head]|Tail], Result) :-
> rember*(Item,Head,Result),
> rember*(Item,Tail,Result).
> rember*(Item, [Item|Tail], Result) :-
> rember*(Item,Tail,Result).
> rember*(Item,[Head|Tail], Result) :-
> rember*(Item,Tail,Result).
Others will help you with semantics, let me say something about syntax:
rember*(Item,[],[]).
is syntactically the same to Prolog as
*(rember, (Item,[],[])).
so the predicate you are really defining here is */2; it is allowed, but
perhaps not what you want. You can check this by the query (and result):
?- *(X,Y).
X = rember
Y = _G245, [], []
It might be good to write
'rember*'(Item,[],[]).
or get rid of the * completely.
Cheers
Bart Demoen
| |
|
|
Bart Demoen wrote:
> wooks wrote:
>
> Others will help you with semantics, let me say something about syntax:
>
> rember*(Item,[],[]).
>
> is syntactically the same to Prolog as
>
> *(rember, (Item,[],[])).
>
> so the predicate you are really defining here is */2; it is allowed, but
> perhaps not what you want. You can check this by the query (and result):
>
> ?- *(X,Y).
>
> X = rember
> Y = _G245, [], []
>
> It might be good to write
>
> 'rember*'(Item,[],[]).
>
> or get rid of the * completely.
>
>
> Cheers
>
> Bart Demoen
I have got rid of the * . Have also experimented wit the 2nd rule. Same
result.
| |
| Bart Demoen 2006-02-08, 9:29 am |
| wooks wrote:
>
> I have got rid of the * . Have also experimented wit the 2nd rule. Same
> result.
>
The * would not have influenced the other issue.
Here some reading aloud of what your clauses say:
Clause 1:
removing all occurrences of Item from an empty list, gives the
empty list
That sounds fine :-)
Clause 2:
if Result comes from removing Item from Head AND also
Result comes from removing Item from Tail
then
Result comes from removing Item from [[Head]|Tail]
That can't be right: why would these two results (in the if part) be
equal ? Take for instance:
?- rember(7,[[8]|[9]],Result).
The two recursive calls would be:
rember(7,[8],Result),
rember(7,[9],Result).
clearly wrong.
About clause 3 and 4: you meant perhaps to make clause 4 to apply only
when Item \== Head ? Why didn't you make that intention clear in your
code ?
Cheers
Bart Demoen
| |
|
| This is where I am up to now.
rember(Item,[],[]).
rember(Item,[[Head]|Tail], [[HeadResult]|[TailResult]]) :-
rember(Item,Head,HeadResult),
rember(Item,Tail,TailResult).
rember(Item, [Item|Tail], Result) :-
rember(Item,Tail,Result).
rember(Item,[Head|Tail], Result) :-
rember(Item,Tail,Result).
I still get the same result.
>
> Here some reading aloud of what your clauses say:
>
>
> Clause 2:
>
> if Result comes from removing Item from Head AND also
> Result comes from removing Item from Tail
> then
> Result comes from removing Item from [[Head]|Tail]
>
So now I hope I am saying
If NewResult comes from removing Item from Head AND also
TailResult comes from removing Item from Tail
then
Result comes from the concatenation of [HeadResult] and
[TailResult]
>
> That can't be right: why would these two results (in the if part) be
> equal ? Take for instance:
>
> ?- rember(7,[[8]|[9]],Result).
>
> The two recursive calls would be:
>
> rember(7,[8],Result),
> rember(7,[9],Result).
>
> clearly wrong.
>
>
>
> About clause 3 and 4: you meant perhaps to make clause 4 to apply only
> when Item \== Head ? Why didn't you make that intention clear in your
> code ?
>
I didn't think I needed to. Do I.
> Cheers
>
> Bart Demoen
| |
|
| oops I meant.
rember(Item,[],[]).
rember(Item,[[Head]|Tail], [[HeadResult]|[TailResult]]) :-
rember(Item,Head,HeadResult),
rember(Item,Tail,TailResult).
rember(Item, [Item|Tail], Result) :-
rember(Item,Tail,Result).
rember(Item,[Head|Tail], [Head|Result]) :-
rember(Item,Tail,Result).
wooks wrote:[color=darkred]
> This is where I am up to now.
>
> rember(Item,[],[]).
> rember(Item,[[Head]|Tail], [[HeadResult]|[TailResult]]) :-
> rember(Item,Head,HeadResult),
> rember(Item,Tail,TailResult).
> rember(Item, [Item|Tail], Result) :-
> rember(Item,Tail,Result).
> rember(Item,[Head|Tail], Result) :-
> rember(Item,Tail,Result).
>
> I still get the same result.
>
>
> So now I hope I am saying
>
> If NewResult comes from removing Item from Head AND also
> TailResult comes from removing Item from Tail
> then
> Result comes from the concatenation of [HeadResult] and
> [TailResult]
>
>
>
>
> I didn't think I needed to. Do I.
>
| |
|
|
Solved..... with a little bit of help.
wooks wrote:
> oops I meant.
>
>
> rember(Item,[],[]).
> rember(Item,[[Head]|Tail], [[HeadResult]|[TailResult]]) :-
this was the culprit. It only works for a nested list of length 1
So .... this works
remberD(Item,[],[]).
remberD(Item,[[Head|Rest]|Tail], [[HeadResult]|[TailResult]]) :-
remberD(Item,[Head|Rest],HeadResult),
remberD(Item,Tail,TailResult).
remberD(Item, [Item|Tail], Result) :-
remberD(Item,Tail,Result).
remberD(Item,[Head|Tail], [Head|Result]) :-
remberD(Item,Tail,Result).
and I get [[coffee], [[tea]], [and, [hick]]] except that it seems to
loop if I request further solutions with semi colons.
BUT
if I replace Rest in clause 2 with the anonymous variable like so
remberD(Item,[[Head|_]|Tail], [[HeadResult]|[TailResult]]) :-
remberD(Item,[Head|_],HeadResult),
remberD(Item,Tail,TailResult).
I get [[coffee], [[tea]], [and]]
Worse still if I request further solutions after 2 cycles I get an out
of stack error.
So it seems that Prolog wants a cut, but I can't think why.
Any clues.
| |
| Markus Triska 2006-02-08, 9:29 am |
| Hi!
wooks wrote:
> remberD(Item,[[Head|Rest]|Tail], [[HeadResult]|[TailResult]]) :-...
> remberD(Item, [Item|Tail], Result) :-...
> remberD(Item,[Head|Tail], [Head|Result]) :-...
There are cases where more than one of these heads match (and
independently, there is a problem with the nesting level of the Result
in the first head). I take it that you want the last of your clauses
only to apply if Head \== Item, and if Head is not a list. You should
require this in the body or use a case distinction as in the following:
rember([], _, []).
rember([Elem|Es], Item, Result) :-
( Elem = [_|_] ->
rember(Elem, Item, RElem),
Result = [RElem|Rest],
rember(Es, Item, Rest)
;
( Elem == Item ->
rember(Es, Item, Result)
;
Result = [Elem|Rest],
rember(Es, Item, Rest)
)
).
I also flipped the positions of the first two arguments to allow for
first argument indexing, and made Item an anonymous variable in the
first clause.
All the best,
Markus.
| |
| Walter 2006-02-08, 9:29 am |
| Clue 1: Prolog does't "want" a cut -- It is perfectly happy to do what you
tell it to do. With recursive data structures, programs are generally
recursive, and if you recurse with annonymous variables in the wrong spot,
you are likely to stray into code that tries to construct infinite data
structures. It is rare that in programs as simple as this that you will need
annonymous variables.
clue 2: write down in simple declarative sentences what you think the
relationship you are trying to express, the way Bart did in one of his
previous posings.
clue 3: put together a few simple test cases that test the limits.
Walter
"wooks" <wookiz@hotmail.com> wrote in message
news:1139236899.962028.308200@g47g2000cwa.googlegroups.com...
>
.. . .
> So it seems that Prolog wants a cut, but I can't think why.
>
> Any clues.
>
| |
|
|
wooks wrote:
> Solved..... with a little bit of help.
>
> wooks wrote:
>
> this was the culprit. It only works for a nested list of length 1
>
> So .... this works
> remberD(Item,[],[]).
> remberD(Item,[[Head|Rest]|Tail], [[HeadResult]|[TailResult]]) :-
> remberD(Item,[Head|Rest],HeadResult),
> remberD(Item,Tail,TailResult).
> remberD(Item, [Item|Tail], Result) :-
> remberD(Item,Tail,Result).
> remberD(Item,[Head|Tail], [Head|Result]) :-
> remberD(Item,Tail,Result).
>
> and I get [[coffee], [[tea]], [and, [hick]]] except that it seems to
> loop if I request further solutions with semi colons.
>
> BUT
>
> if I replace Rest in clause 2 with the anonymous variable like so
>
> remberD(Item,[[Head|_]|Tail], [[HeadResult]|[TailResult]]) :-
> remberD(Item,[Head|_],HeadResult),
> remberD(Item,Tail,TailResult).
>
> I get [[coffee], [[tea]], [and]]
>
> Worse still if I request further solutions after 2 cycles I get an out
> of stack error.
>
> So it seems that Prolog wants a cut, but I can't think why.
>
> Any clues.
This seems to be a shorter solution.
remberD(Item, [Head|Tail], [HeadResult|TailResult]) :-
remberD(Item, Head, HeadResult),
remberD(Item,Tail,TailResult),
!.
remberD(Item,[],[]).
remberD(Item, Item, []).
remberD(Item, Head, Head).
Problem is instead of Item dissappearing it gets replaced by the empty
list because of
remberD(Item,Item,[]).
whereas I really wamt to return null or an empty string.
How do I do this.
|
|
|
|
|