double a list
Markus Westphal
i have to write a predicate double(Ls,Ms), so that every element of the list
Ls appears two times in the list Ms.
an example
double([1,2,3],Ms).
should produce:
Ms = [1,1,2,2,3,3].
can anyone help me? (all i achieved so far is Ms = [3,2,1,1,2,3])
thanks in advance and greetings
markus westphal
Remko Troncon
: Ls appears two times in the list Ms.
The solution is pretty obvious, so telling you wouldn't help you very much in
understanding Prolog. Maybe you can post what you have so far, and we can
help you find your errors ?
Remko
Markus Westphal
"Remko Troncon" <remko....@cs.kuleuven.ac.be> schrieb im Newsbeitrag
news:98537568...@seven.kulnet.kuleuven.ac.be...
>
> The solution is pretty obvious, so telling you wouldn't help you very much
in
> understanding Prolog. Maybe you can post what you have so far, and we can
> help you find your errors ?
>
> Remko
hello,
first i've to say that i'm a complete newbie with prolog and haven't really
got to like it yet - so please be lenient towards my certainly ridiculous
solution :-)
------------------------------------
double_help([],Ls,Ls).
double_help([Head|Tail],Ls,Rs) :- double_help(Tail,[Head|Ls],Rs).
double(Ls,Rs) :- double_help(Ls,Ls,Rs).
------------------------------------
awful - isn't it?
thanks
markus
Geoff Summerhayes
"Markus Westphal" <mar...@romanum.de> wrote in message news:99gdm6$44i$01$1...@news.t-online.com...
>
> hello,
>
> first i've to say that i'm a complete newbie with prolog and haven't really
> got to like it yet - so please be lenient towards my certainly ridiculous
> solution :-)
>
> ------------------------------------
> double_help([],Ls,Ls).
> double_help([Head|Tail],Ls,Rs) :- double_help(Tail,[Head|Ls],Rs).
> double(Ls,Rs) :- double_help(Ls,Ls,Rs).
> ------------------------------------
>
> awful - isn't it?
>
Not really, but what you have written is what I would call palindrome/2.
double/2 doesn't need to be this fancy, it doesn't require a helper
function either. hint: [X|[X2|L]] is equivalent to [X,X2|L], you can
put as many variables in the head section of a list form as you need.
Think about it this way, you are building your list on the way down,
what you need to be doing is building it on the way up instead, as it
returns from the base case so that the first argument is the last one
added on the head of the new list. Phew! That's about a much as I can
say without actually giving you the solution, it's only 2 lines!
Geoff
Markus Westphal
news:tbnfuc7...@corp.supernews.com...
>
> Not really, but what you have written is what I would call palindrome/2.
> double/2 doesn't need to be this fancy, it doesn't require a helper
> function either. hint: [X|[X2|L]] is equivalent to [X,X2|L], you can
> put as many variables in the head section of a list form as you need.
> Think about it this way, you are building your list on the way down,
> what you need to be doing is building it on the way up instead, as it
> returns from the base case so that the first argument is the last one
> added on the head of the new list. Phew! That's about a much as I can
> say without actually giving you the solution, it's only 2 lines!
>
> Geoff
hello,
thanks a lot for your advice!
now i wrote what follows:
double([],[]).
double([X|Tail],[X,X|ResultList]) :- double(Tail,ResultList).
- and it works, which of course is fine. but to say the truth, i don't
exactly know why it works. could you please be so kind and explain this to
me in a few centences (did i already mention that i'm a absolute newbie?).
markus
www.lambda-systems.com
double([],[]):-!.
double([L1|L],[L1,L1|L2]):-double(L,L2).
and tht's it !
Juan Miguel LECONTE
16 years old ;-)
"Markus Westphal" <mar...@romanum.de> a écrit dans le message news:
99fvpn$ei1$01$1...@news.t-online.com...
www.lambda-systems.com
"www.lambda-systems.com" <webm...@lambda-systems.com> a écrit dans le
message news: 99git0$7r8$1...@wanadoo.fr...
Joseph A. Knapka
>
> hello,
>
> thanks a lot for your advice!
>
> now i wrote what follows:
>
> double([],[]).
> double([X|Tail],[X,X|ResultList]) :- double(Tail,ResultList).
>
> - and it works, which of course is fine. but to say the truth, i don't
> exactly know why it works. could you please be so kind and explain this to
> me in a few centences (did i already mention that i'm a absolute newbie?).
Probably you should "trace" it in your interpreter and see exactly
how the variables get instantiated at each call.
<maybe_you_already_know_this_so_shoot_me>
The best way to think about Prolog is declaratively:
double([],[]).
means, "An empty list's doubling is just an empty list", and
double([X|Tail],[X,X|DoubledTail]) :- double(Tail,DoubledTail).
means, "The list [X|Tail]'s doubling is the list ([X,X|DoubleTail])
whose first two elements are X, if its tail DoubleTail is the
doubling of Tail." You don't have to know anything about how the
code actually gets executed to understand that explanation, which is
obviously correct.
If you can formulate your problem in declarative terms,
most of the time the correct Prolog code just flows right
out. It's kind of a Zen thing :-) Sometimes Prolog's
execution model inteferes with a straightforward declarative
approach, so you need to understand how the inference
engine works, but that's secondary - start with a
good declarative understanding of your problem.
I hope this helps more than it confuses :-P
-- Joe Knapka
"It was just a maddened crocodile hidden in a flower bed. It could
have happened to anyone." -- Pratchett
// Linux MM Documentation in progress:
// http://home.earthlink.net/~jknapka/linux-mm/vmoutline.html
* Evolution is an "unproven theory" in the same sense that gravity is. *
Geoffrey Summerhayes
>
> hello,
>
> thanks a lot for your advice!
>
> now i wrote what follows:
>
> double([],[]).
> double([X|Tail],[X,X|ResultList]) :- double(Tail,ResultList).
>
> - and it works, which of course is fine. but to say the truth, i don't
> exactly know why it works. could you please be so kind and explain this to
> me in a few centences (did i already mention that i'm a absolute newbie?).
>
Oops! You said `a few', didn't you?
Let's start with a trace:
(this you can get with `trace(double).')
Prolog starts trying to prove double([1,2,3],X).
hits double([],[]) and fails, [1,2,3] doesn't unify with []
hits double([X|Tail],[X,X|ResultList]), looks good so far
unifies Xa with 1, Taila with [2,3] ResultLista with ???
(I subscript because they are distinct on each level)
what do I need to prove this?
double([2,3],ResultLista) don't know what ResultLista is.
and again,
hits double([],[]) and fails
hits double([X|Tail],[X,X|ResultList]), looks good so far
unifies Xb with 2, Tailb with [3] ResultListb with ???
what do I need to prove this?
double([3],ResultListb) don't know what ResultListb is.
and again,
hits double([],[]) and fails
hits double([X|Tail],[X,X|ResultList]), looks good so far
unifies Xc with 3, Tailc with [], ResultListc with ???
what do I need to prove this?
double([],ResultListc) don't know what ResultListc is.
But...
hits double([],[]) and succeeds!
I know what ResultListc is, it's [].
So, the ResultListb in the previous which was
[Xc,Xc,|ResultListc] must be [3,3|[]] which is [3,3]
So, the ResultLista in the previous is [2,2|[3,3]] or [2,2,3,3]
So, the ResultList at the top is [1,1|[2,2,3,3]] or [1,1,2,2,3,3]
Now for the fun stuff, what you wrote was a predicate that checks
the first element of a list against the first pair in the second
list and, if they are all equal, does the same comparison on what's
left. We'll take the empty list as granted. So ...
double([],[]). gives yes
double([1,2,3],[1,1,2,2,3,3]). gives yes
double([1,2,3],[1,1,2,2,3,4]). gives no
double([1,2,3],[1,1,2,2,3]). gives no
double([1,2],[1,1,2,2,3,3]). gives no
and so on ...
Cool, that works, but Prolog is trying to prove this, so it
will search to find something that makes the predicate true when
it doesn't have enough to say yes or no.
double([1,2,3],X) gives X=[1,1,2,2,3,3]
hitting `;' gives no because it's a unique answer
double(X,[1,1,2,2,3,3]) gives X=[1,2,3] `;' gives no
double(X,[1,1,2,2,3]) gives no
or weird cases,
double([1,X,3],[1,1,2,2,3,3]). gives X=2
double([1,2,3],[1,X,Y,2,3,3]). gives X=1 Y=2
double([X,2,3],[1,1,Y,Y,3,3]). gives X=1 Y=2
double([X,2,3],[1,1,X,X,3,3]). gives no
For me, this is an almost ideal predicate, it handles almost
every case and backtracks beautifully.
There are cases it doesn't handle, what are they?
Hint:
some_pred(X,Y) :-
member(X,[1,2,3]),
member(Y,[1,2,3,4]),
X \= Y.
is an example of an ideal predicate, by my definition ;-)
Hope this helps, sorry about the length,
Geoff
Markus Westphal
markus
Katiuscia
Hi,
I have done it in this way:
double([],[]).
doouble([H|L],[H,H|L1]):-
double(L,L1).
bye-bye katty.
Matthew M. Huntbach
>i have to write a predicate double(Ls,Ms), so that every element of the list
>Ls appears two times in the list Ms.
>an example
>double([1,2,3],Ms).
>should produce:
>Ms = [1,1,2,2,3,3].
>can anyone help me? (all i achieved so far is Ms = [3,2,1,1,2,3])
The double of the empty list is the empty list - that is obvious, surely?
The double of the list whose head is X is the list whose first element
is X, whose second element is X, and the rest is the double of the tail
of the list. Is that obvious, or isn't it?
So the Prolog program is obvious.
Why are so many people having so much trouble with things that are so
obvious?
Matthew Huntbach
Katiuscia
Katiuscia
Katiuscia
Markus Westphal
>
> The double of the list whose head is X is the list whose first element
> is X, whose second element is X, and the rest is the double of the tail
> of the list. Is that obvious, or isn't it?
>
> So the Prolog program is obvious.
>
> Why are so many people having so much trouble with things that are so
> obvious?
>
> Matthew Huntbach
maybe because their 'first contact' with prolog took place just the day
before?!
and to me it seems obvious that someone who has been using only languages
like java, turbopascal etc before, will first have certain problems :-)
markus
Matthew M. Huntbach
> > Why are so many people having so much trouble with things that are so
> > obvious?
> maybe because their 'first contact' with prolog took place just the day
> before?!
Surely then they should think a little more about their problem and look
through a few examples before going to the worldwide news group on the
language and saying they can't do it. Do these people have no shame?
I wouldn't dream of starting to program in an entirely new language one
day and immediately posting to the worldwide newsgroup asking for the
answer to a simple question the next.
Matthew Huntbach