[Haskell-beginners] tower hanoi problem

Wed Feb 18 19:08:18 UTC 2015

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 <r.wobben at home.nl> 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 <r.wobben at home.nl> 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 <r.wobben at home.nl> 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
>>>>>>>> Beginners at haskell.org
>>>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>> _______________________________________________
>>>>>> Beginners mailing list
>>>>>> Beginners at haskell.org
>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>>>
>>>>>>
>>>>>
>>>>
>>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> Beginners at haskell.org
>>> 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 listBeginners at haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>
>
> _______________________________________________
> Beginners mailing listBeginners at haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
>
> _______________________________________________
> Beginners mailing listBeginners at haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> 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/3b921fdb/attachment-0001.html>