[Haskell-beginners] tower hanoi problem

Wed Feb 18 16:35:20 UTC 2015

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
>>>
>>
>
>