<div dir="ltr">Think about the three steps. Isn't it "move the top n-1 disks to temp, move the bottom disk to end, then move the top n-1 disks to the end"? Doesn't look like what your code does.<div><br>BTW, you can replace the singleton list in the middle a call of "hanoi 1 ...". Not necessarily an improvement, but it makes each of the three elements have the same form.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Feb 18, 2015 at 12:44 PM, Roelof Wobben <span dir="ltr"><<a href="mailto:r.wobben@home.nl" target="_blank">r.wobben@home.nl</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>I have now this : <br>
<br>
hanoi 1 start _ end = [ (start, end)]<br>
hanoi n start temp end = hanoi (n-1) start temp end ++ [(start,
temp)] ++ hanoi (n-1) end start temp<br>
<br>
main = print $ hanoi 3 'a' 'b' 'c'<br>
<br>
and see this output :
[('a','c'),('a','b'),('c','b'),('a','b'),('c','b'),('c','a'),('b','a')]
<br>
where I was expected to see this :
[('a','c'),('a','b'),('c','b'),('a','c'),('b','a'),('b','c'),('a','c')]
<br>
<br>
Roelof<br>
<br>
<br>
<br>
Roelof Wobben schreef op 18-2-2015 om 18:20:<br>
</div>
<blockquote type="cite">
<div>Thanks , and after the code that I
have made ?<br>
<br>
Roelof<br>
<br>
<br>
Mike Meyer schreef op 18-2-2015 om 18:18:<br>
</div>
<blockquote type="cite">
<div dir="ltr">I think you've almost got it. Let me suggest
something like:
<div><br>
</div>
<div>main = print $ hanoi 3 'a' 'b' 'c'</div>
<div><br>
</div>
<div>hanoi n start temp end = ...</div>
<div><br>
</div>
<div>for testing.</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Feb 18, 2015 at 11:16 AM,
Roelof Wobben <span dir="ltr"><<a href="mailto:r.wobben@home.nl" target="_blank">r.wobben@home.nl</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>3 is not a special case. <br>
<br>
I want to use the hanoi function with 3 pegs as a
starting point. <br>
<br>
Roelof<br>
<br>
<br>
<br>
Joel Neely schreef op 18-2-2015 om 18:11:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">Why
is 3 a special case?</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Feb 18, 2015 at
10:35 AM, Roelof Wobben <span dir="ltr"><<a href="mailto:r.wobben@home.nl" target="_blank">r.wobben@home.nl</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Oke,<br>
<br>
Im thinking of this way<br>
<br>
hanoi 3 source between end<br>
hanoi 1 source _ end = [ (source, end)]<br>
hanoi n source between end = hanoi (n-1) xxxx<br>
print move somehow.<br>
<br>
<br>
Roelof<br>
<br>
<br>
<br>
<br>
Dudley Brooks schreef op 18-2-2015 om 17:19:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> There are three
*locations*. But there is only one *thing* --
only *one at a time*, that is, namely
whichever one you are moving on any given
move, be it a disc or an entire stack.
<div>
<div><br>
<br>
On 2/17/15 11:10 PM, Roelof Wobben wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> That part
I understand already.<br>
<br>
The only thing I do not see is what the
base case in this exercise is because
you are working with 3 things instead of
1 for example a list.<br>
<br>
As a example reversing a list recursive<br>
<br>
the base case is the not reversed list
is empty.<br>
<br>
<br>
Roelof<br>
<br>
<br>
<br>
Dudley Brooks schreef op 18-2-2015 om
8:04:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> On 2/17/15
10:56 PM, Dudley Brooks wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> On 2/16/15
7:06 PM, Doug McIlroy wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> My way
of working is one problem at the
time.<br>
So first solve the itterate one
and after that I gonna try to
solve the<br>
recursion one.<br>
Otherwise I get confused.<br>
</blockquote>
This is the crux of the matter.
You must strive to think those
thoughts<br>
in the opposite order. Then you
won't get confused.<br>
<br>
Recursion takes a grand
simplifying view: "Are there
smaller problems of<br>
the same kind, from the
solution(s) of which we could
build a solution of<br>
the problem at hand?" If so, let's
just believe we have a solver for
the<br>
smaller problems and build on
them. This is the recursive step.<br>
<br>
Of course this can't be done when
you are faced with the smallest<br>
possible problem. Then you have to
tell directly how to solve<br>
it. This is the base case.<br>
<br>
[In Hanoi, the base case might be
taken as how to move a pile<br>
of one disc to another post. Even
more simply, it might be how<br>
to move a pile of zero
discs--perhaps a curious idea, but
no more<br>
curious than the idea of 0 as a
counting number.]<br>
<br>
A trivial example: how to copy a
list (x:xs) of arbitrary length.<br>
We could do that if we knew how to
copy the smaller list tail, xs.<br>
All we have to do is tack x onto
the head of the copy. Lo, the
recipe<br>
copy (x:xs) = x : copy xs<br>
Final detail: when the list has no
elements, there is no smaller<br>
list to copy. We need another rule
for this base case. A copy<br>
of an empty list is empty:<br>
copy [] = []<br>
<br>
With those two rules, we're done.
No iterative reasoning about<br>
copying all the elements of the
list. We can see that afterward,<br>
but that is not how we got to the
solution.<br>
<br>
[It has been suggested that you
can understand recursion thus<br>
> Do the first step. Then
(to put it very dramatically)<br>
> do *everything else* in
*a single step*!<br>
This point of view works for copy,
and more generally for<br>
"tail recursion", which is
trivially transformable to
iteration.<br>
It doesn't work for Hanoi, which
involves a fancier recursion<br>
pattern. The "smaller problem(s)"
formulation does work.]<br>
</blockquote>
<br>
I simplified it (or over-dramatized
it) to the point of
not-quite-correctness. I was trying
to dramatize the point of how
surprising the idea of recursion is,
when you first encounter it (because
I suspected that the OP had not yet
"grokked" the elegance of recursion)
-- and remembering my own Aha!
moment at recursive definitions and
proofs by induction in high school
algebra, back when the only
"high-level" programming language
was assembly. I see that I gave the
mistaken impression that that's the
*only* kind of recursive structure.
What I should have said, less
dramatically, is<br>
<br>
Do the base case(s)<br>
Then do the recursion --
whatever steps that might involve,
including possibly several recursive
steps and possibly even several
single steps, interweaved in various
possible orders.<br>
<br>
You can't *start* with the
recursion, or you'll get either an
infinite loop or an error.<br>
<br>
I wouldn't quite call the conversion
of tail-recursion to iteration
trivial, exactly ... you still have
to *do* it, after all! And when I
did CS in school (a long time ago),
the equivalence had only fairly
recently been recognized. (By
computer language designers,
anyway. Maybe lambda-calculus
mathematicians knew it long before
that.) Certainly the idea that
compilers could do it automatically
was pretty new. If it were
*completely* trivial, it would have
been recognized long before! ;^)<br>
<br>
If you're younger you probably grew
up when this idea was already
commonplace. Yesterday's brilliant
insight is today's trivia!<br>
</blockquote>
<br>
BTW, since, as you and several others
point out, the recursive solution of
Towers of Hanoi does *not* involve
tail recursion, that's why it's all
the more surprising that there
actually is a very simple iterative
solution, almost as simple to state as
the recursive solution, and certainly
easier to understand and follow by a
novice or non-programmer, who doesn't
think recursively.<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> In many
harder problems a surefire way to
get confused is to<br>
try to think about the sequence of
elementary steps in the final<br>
solution. Hanoi is a good case in
point.<br>
<br>
Eventually you will come to see
recursion as a way to confidently<br>
obtain a solution, even though the
progress of the computation is<br>
too complicated to visualize. It
is not just a succinct way to<br>
express iteration!<br>
<br>
Doug McIlroy<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote>
<br>
</blockquote>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br>
</blockquote>
<br>
</blockquote>
<br>
<br>
</div>
</div>
</blockquote>
<div>
<div> <br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</div>
</div>
</blockquote>
</div>
<br>
<br clear="all">
<span><font color="#888888">
<div><br>
</div>
-- <br>
<div>Beauty of style and harmony and grace and
good rhythm depend on simplicity. - Plato</div>
</font></span></div>
<span><font color="#888888"> <br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
Beginners mailing list
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</font></span></blockquote>
<br>
</div>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
Beginners mailing list
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
Beginners mailing list
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
</div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>