Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: tower hanoi problem (Dudley Brooks)
2. Re: tower hanoi problem (Doug McIlroy)
3. Re: tower hanoi problem (Roelof Wobben)
----------------------------------------------------------------------
Message: 1
Date: Mon, 16 Feb 2015 15:55:23 -0800
From: Dudley Brooks <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID: <[email protected]>
Content-Type: text/plain; charset="windows-1252"; Format="flowed"
(I hope that no one will think that this is too much of a hint.)
There are three restrictions on how you can move:
(1) You can only move one disc at a time.
(2) You can only move the top disc of a stack.
(3) You can't put a larger disc on a smaller one.
What if (1) weren't true? What if you could move a whole bunch of discs
at the same time? (Which would kind of mean that (2) wasn't true
either.) What if, after you had removed a certain number of discs (I
won't say how many, but think small!) from the top of a stack, you could
simply pick up the entire remaining stack and move it?
On 2/16/15 10:45 AM, Roelof Wobben wrote:
> And Im still confused.
>
> Roelof
>
>
>
> Dudley Brooks schreef op 16-2-2015 om 19:41:
>> Plus I should say that the "first" (or whichever) step might also
>> really be more than one step. The crucial idea is that there are
>> individual step(s) versus "lumped" step(s), where the individual
>> step(s) are the base case(s) and the "lumped" step(s) are the
>> recursive invocation(s).
>>
>> On 2/16/15 10:31 AM, Dudley Brooks wrote:
>>> You're right, of course. I guess the more precise way to say what I
>>> meant is that you *separate* a single step from everything else,
>>> dealing with everything else as a lump ... or two lumps ... or three
>>> lumps ... or ...
>>>
>>> I did at least say that "a 'single step' might have more than one
>>> step." ;^) My mistake was the use of the word "first".
>>>
>>> On 2/16/15 5:07 AM, Joel Neely wrote:
>>>> I'm sorry, but I must disagree with the generalization.
>>>>
>>>> You described "the very nature" of a typical recursion over a list:
>>>> (1) deal with the head, then
>>>> (2) deal with everything else.
>>>>
>>>> But lists are not the only recursive structure. Infix-order
>>>> processing of a tree, for example, is more naturally described as:
>>>> (1) deal with the left sub-tree (the first "everything else"),
>>>> (2) deal with the parent (analogous to the head of a list),
>>>> (3) deal with the right sub-tree (the second "everything else").
>>>>
>>>> At the risk of a spoiler...
>>>>
>>>> .
>>>>
>>>> .
>>>>
>>>> .
>>>>
>>>> .
>>>>
>>>> One approach to the Towers of Hanoi problem emerges nicely from
>>>> thinking of the moves as a tree.
>>>>
>>>> -jn-
>>>>
>>>> On Sun, Feb 15, 2015 at 2:54 PM, Dudley Brooks
>>>> <[email protected] <mailto:[email protected]>> wrote:
>>>>
>>>> In my opinion, advising Mr Wobben to watch the pattern of moves
>>>> will *not* lead him to the recursive solution, since the
>>>> pattern of moves is really iterative.
>>>>
>>>> My hint would be to remember the very nature of recursion
>>>> itself (for *any* problem): Do the first step. Then (to put
>>>> it very dramatically) do *everything else* in *a single step*!
>>>> (Realizing that "everything else" is really the same problem,
>>>> just made slightly smaller.)
>>>>
>>>> Note: "A single step" might itself have more than one step.
>>>> My point is that recursion consists of (to put it humorously):
>>>> To do ABCDEFGHIJKLMNOPQRSTUVWXYZ, first you do A, then you do
>>>> BCDEFGHIJKLMNOPQRSTUVWXYZ. And, of course, "first" might
>>>> actually be "last"! And remembering the story of the Gordian
>>>> Knot might help too. (I apologize that trying not to be too
>>>> explicit in the hint possibly makes it even more obscure.)
>>>>
>>>> Here's another hint that's useful for all kinds of programming
>>>> problems, not just recursion: Most problems consist of not
>>>> only what you're trying to solve, but also what the
>>>> restrictions are on what you're allowed to do to solve it.
>>>> Often some good insights come from imagining how you could
>>>> solve the problem if you could ignore one or more of the
>>>> restrictions (that's what I meant by the Gordian Knot
>>>> reference). So for the Towers of Hanoi, think about what the
>>>> restrictions are on what kind of moves you're allowed to make.
>>>> Remove one of those restrictions.
>>>>
>>>> (Speaking of the iterative solution, the fun thing about
>>>> actually physically doing the Towers of Hanoi is that, even
>>>> though you're doing it by remembering the steps of the
>>>> iterative pattern, as you watch the towers grow and shrink you
>>>> can kind of "see" the recursion.)
>>>>
>>>>
>>>> On 2/15/15 12:51 AM, Roelof Wobben wrote:
>>>>
>>>> YCH schreef op 15-2-2015 om 9:45:
>>>>
>>>> How about if I say "Actually target was c not b and
>>>> here is one more
>>>> disc. I put it on a. Now you should move all to c"
>>>>
>>>>
>>>>
>>>> Hanoi 1 a b c
>>>>
>>>> A -> C
>>>>
>>>> Hanoi 2 a b c
>>>>
>>>> A -> B
>>>> A -> C
>>>> B -> C
>>>>
>>>> Hanoi 3 a b c
>>>>
>>>> A -> C
>>>> A -> B
>>>> C -> B
>>>> A -> C
>>>> B -> A
>>>> B -> C
>>>> A -> C
>>>>
>>>>
>>>> Roelof
>>>>
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> [email protected] <mailto:[email protected]>
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> [email protected] <mailto:[email protected]>
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Beauty of style and harmony and grace and good rhythm depend on
>>>> simplicity. - Plato
>>>
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150216/4e9d5694/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 16 Feb 2015 22:06:57 -0500
From: Doug McIlroy <[email protected]>
To: [email protected]
Cc: [email protected]
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
> My way of working is one problem at the time.
> So first solve the itterate one and after that I gonna try to solve the
> recursion one.
> Otherwise I get confused.
This is the crux of the matter. You must strive to think those thoughts
in the opposite order. Then you won't get confused.
Recursion takes a grand simplifying view: "Are there smaller problems of
the same kind, from the solution(s) of which we could build a solution of
the problem at hand?" If so, let's just believe we have a solver for the
smaller problems and build on them. This is the recursive step.
Of course this can't be done when you are faced with the smallest
possible problem. Then you have to tell directly how to solve
it. This is the base case.
[In Hanoi, the base case might be taken as how to move a pile
of one disc to another post. Even more simply, it might be how
to move a pile of zero discs--perhaps a curious idea, but no more
curious than the idea of 0 as a counting number.]
A trivial example: how to copy a list (x:xs) of arbitrary length.
We could do that if we knew how to copy the smaller list tail, xs.
All we have to do is tack x onto the head of the copy. Lo, the recipe
copy (x:xs) = x : copy xs
Final detail: when the list has no elements, there is no smaller
list to copy. We need another rule for this base case. A copy
of an empty list is empty:
copy [] = []
With those two rules, we're done. No iterative reasoning about
copying all the elements of the list. We can see that afterward,
but that is not how we got to the solution.
[It has been suggested that you can understand recursion thus
> Do the first step. Then (to put it very dramatically)
> do *everything else* in *a single step*!
This point of view works for copy, and more generally for
"tail recursion", which is trivially transformable to iteration.
It doesn't work for Hanoi, which involves a fancier recursion
pattern. The "smaller problem(s)" formulation does work.]
In many harder problems a surefire way to get confused is to
try to think about the sequence of elementary steps in the final
solution. Hanoi is a good case in point.
Eventually you will come to see recursion as a way to confidently
obtain a solution, even though the progress of the computation is
too complicated to visualize. It is not just a succinct way to
express iteration!
Doug McIlroy
------------------------------
Message: 3
Date: Tue, 17 Feb 2015 12:23:52 +0100
From: Roelof Wobben <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150217/6b4bf125/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 80, Issue 35
*****************************************
