<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">pfff, tomorrow another day,<br>
<br>
Am I on the right track that the first hanoi is where the first
step must be done. <br>
and the last step the move to the end is done ?<br>
<br>
Roelof<br>
<br>
<br>
<br>
Mike Meyer schreef op 18-2-2015 om 20:08:<br>
</div>
<blockquote
cite="mid:CAD=7U2ADi8wD4HpvC6w93g9PVapsxWbAKYNkKS25R1H4vJtByA@mail.gmail.com"
type="cite">
<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 moz-do-not-send="true"
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
moz-do-not-send="true"
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
moz-do-not-send="true"
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
moz-do-not-send="true"
href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a
moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org"
target="_blank">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org"
target="_blank">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org"
target="_blank">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true" href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
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 class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Beginners mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Beginners@haskell.org">Beginners@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
</body>
</html>