Re: [Haskell-beginners] tower hanoi problem

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 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 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 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@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners >> > > _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@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@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing listBeginners@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing listBeginners@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners