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 (Mike Meyer)
----------------------------------------------------------------------
Message: 1
Date: Wed, 18 Feb 2015 14:03:51 -0600
From: Mike Meyer <[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:
<CAD=7u2cneppyvo+ez2qn6vlkffbcg_zmwgyrwkx7sezq+kx...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Yes, you're on the right track. You've got the parts put together properly,
you just need to make the recursive calls and the middle move match the
description you gave earlier.
On Wed, Feb 18, 2015 at 2:02 PM, Roelof Wobben <[email protected]> wrote:
> pfff, tomorrow another day,
>
> Am I on the right track that the first hanoi is where the first step must
> be done.
> and the last step the move to the end is done ?
>
> Roelof
>
>
>
> Mike Meyer schreef op 18-2-2015 om 20:08:
>
> 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.
>
> 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.
>
> On Wed, Feb 18, 2015 at 12:44 PM, Roelof Wobben <[email protected]> wrote:
>
>> I have now this :
>>
>> hanoi 1 start _ end = [ (start, end)]
>> hanoi n start temp end = hanoi (n-1) start temp end ++ [(start, temp)] ++
>> hanoi (n-1) end start temp
>>
>> main = print $ hanoi 3 'a' 'b' 'c'
>>
>> and see this output :
>> [('a','c'),('a','b'),('c','b'),('a','b'),('c','b'),('c','a'),('b','a')]
>> where I was expected to see this :
>> [('a','c'),('a','b'),('c','b'),('a','c'),('b','a'),('b','c'),('a','c')]
>>
>> Roelof
>>
>>
>>
>> Roelof Wobben schreef op 18-2-2015 om 18:20:
>>
>> Thanks , and after the code that I have made ?
>>
>> Roelof
>>
>>
>> Mike Meyer schreef op 18-2-2015 om 18:18:
>>
>> I think you've almost got it. Let me suggest something like:
>>
>> main = print $ hanoi 3 'a' 'b' 'c'
>>
>> hanoi n start temp end = ...
>>
>> for testing.
>>
>> On Wed, Feb 18, 2015 at 11:16 AM, Roelof Wobben <[email protected]> wrote:
>>
>>> 3 is not a special case.
>>>
>>> I want to use the hanoi function with 3 pegs as a starting point.
>>>
>>> Roelof
>>>
>>>
>>>
>>> Joel Neely schreef op 18-2-2015 om 18:11:
>>>
>>> Why is 3 a special case?
>>>
>>> On Wed, Feb 18, 2015 at 10:35 AM, Roelof Wobben <[email protected]>
>>> wrote:
>>>
>>>> Oke,
>>>>
>>>> Im thinking of this way
>>>>
>>>> hanoi 3 source between end
>>>> hanoi 1 source _ end = [ (source, end)]
>>>> hanoi n source between end = hanoi (n-1) xxxx
>>>> print move
>>>> somehow.
>>>>
>>>>
>>>> Roelof
>>>>
>>>>
>>>>
>>>>
>>>> Dudley Brooks schreef op 18-2-2015 om 17:19:
>>>>
>>>>> 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.
>>>>>
>>>>>
>>>>> On 2/17/15 11:10 PM, Roelof Wobben wrote:
>>>>>
>>>>>> That part I understand already.
>>>>>>
>>>>>> 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.
>>>>>>
>>>>>> As a example reversing a list recursive
>>>>>>
>>>>>> the base case is the not reversed list is empty.
>>>>>>
>>>>>>
>>>>>> Roelof
>>>>>>
>>>>>>
>>>>>>
>>>>>> Dudley Brooks schreef op 18-2-2015 om 8:04:
>>>>>>
>>>>>>> On 2/17/15 10:56 PM, Dudley Brooks wrote:
>>>>>>>
>>>>>>>> On 2/16/15 7:06 PM, Doug McIlroy wrote:
>>>>>>>>
>>>>>>>>> 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.]
>>>>>>>>>
>>>>>>>>
>>>>>>>> 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
>>>>>>>>
>>>>>>>> Do the base case(s)
>>>>>>>> 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.
>>>>>>>>
>>>>>>>> You can't *start* with the recursion, or you'll get either an
>>>>>>>> infinite loop or an error.
>>>>>>>>
>>>>>>>> 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! ;^)
>>>>>>>>
>>>>>>>> If you're younger you probably grew up when this idea was already
>>>>>>>> commonplace. Yesterday's brilliant insight is today's trivia!
>>>>>>>>
>>>>>>>
>>>>>>> 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.
>>>>>>>
>>>>>>>>
>>>>>>>> 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
>>>>>>>>> _______________________________________________
>>>>>>>>> Beginners mailing list
>>>>>>>>> [email protected]
>>>>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Beginners mailing list
>>>>>>> [email protected]
>>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> [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
>>> [email protected]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>>
>>
>>
>> _______________________________________________
>> Beginners mailing
>> [email protected]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>>
>>
>> _______________________________________________
>> Beginners mailing
>> [email protected]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>
>
> _______________________________________________
> Beginners mailing
> [email protected]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> 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/20150218/cb92d502/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 46
*****************************************
