On Sat, Feb 14, 2015 at 3:27 PM, Roelof Wobben wrote:

KC schreef op 14-2-2015 om 22:23:

...

Hint:

- think about what you need to do in each recursive step and in the base case

- there is also an interesting way of viewing the problem

Check if I can do another step or check if the end case all disk are on the last peg.

Im very curious what the interesting way is

I suspect it's the iterative version that was already mentioned here. You were close to discovering it when worked through the problem on paper.

On Sat, Feb 14, 2015 at 3:35 PM, Roelof Wobben wrote:

I know.

Eveyone says there is a pattern but I do not see it at the moment.

Maybe I do the wrong first move with more then 2 disk.

You can put the first disk on the second or the thirth peg.

Think about which peg you want the stack to end up on, and what your last move HAS to be based on the rules.

Would you mind show code for only two cases? Just think about two cases. hanoi 2 a b c hanoi 3 a b c 2015. 2. 15. 오전 6:35에 "Roelof Wobben" 님이 작성:

I know.

Eveyone says there is a pattern but I do not see it at the moment.

Maybe I do the wrong first move with more then 2 disk.

You can put the first disk on the second or the thirth peg.

Roelof

Mike Meyer schreef op 14-2-2015 om 22:30:

On Sat, Feb 14, 2015 at 3:27 PM, Roelof Wobben wrote:

...

KC schreef op 14-2-2015 om 22:23:

...

Hint:

- think about what you need to do in each recursive step and in the base case

- there is also an interesting way of viewing the problem

Check if I can do another step or check if the end case all disk are on the last peg.

Im very curious what the interesting way is

I suspect it's the iterative version that was already mentioned here. You were close to discovering it when worked through the problem on paper.

_______________________________________________ Beginners mailing listBeginners@haskell.orghttp://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Do you want to see the list for those two cases? Because in either the recursive or iterative solution, there's only two cases. The 2-disk moves are: [(a, c), (a, b), (c, b)] The 3-disk moves are: [(a, b), (a, c), (b, c), (a, b), (c, a), (c, b), (a, b)] On Sat, Feb 14, 2015 at 3:40 PM, YCH wrote:

Would you mind show code for only two cases? Just think about two cases.

hanoi 2 a b c hanoi 3 a b c 2015. 2. 15. 오전 6:35에 "Roelof Wobben" 님이 작성:

...

I know.

Eveyone says there is a pattern but I do not see it at the moment.

Maybe I do the wrong first move with more then 2 disk.

You can put the first disk on the second or the thirth peg.

Roelof

Mike Meyer schreef op 14-2-2015 om 22:30:

On Sat, Feb 14, 2015 at 3:27 PM, Roelof Wobben wrote:

...

KC schreef op 14-2-2015 om 22:23:

...

Hint:

- think about what you need to do in each recursive step and in the base case

- there is also an interesting way of viewing the problem

Check if I can do another step or check if the end case all disk are on the last peg.

Im very curious what the interesting way is

I suspect it's the iterative version that was already mentioned here. You were close to discovering it when worked through the problem on paper.

_______________________________________________ Beginners mailing listBeginners@haskell.orghttp://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

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" On Sun, Feb 15, 2015 at 5:29 PM, Roelof Wobben wrote:

Roelof Wobben schreef op 15-2-2015 om 9:23:

YCH schreef op 14-2-2015 om 22:53:

...

You can put the first disk on the second or the thirth peg.

Think a, b, c as 'src, target, temp'

So if you have only one disk on src peg, it has to go target peg. But if you have two or more discs, you cannot put first peg on target peg.

hanoi 1 1 2 3 = [ (1, 2) ] hanoi 2 1 2 3 = [ ?

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Hanoi 1 a b c - [ (a,b)]

Hanoi 2 123 = [ ( a,b)] = [ (a,c) ] =[ (b,c) ]

solved.

Roelof

Sorry, that one is wrong. Everything is on the 3th now.

Another attempt.

Hanoi 2 a b c = [ (a, c)] = [ (a, b)] = [ (c, b) ]

Roelof

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

On Sun, Feb 15, 2015 at 5:51 PM, 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 -- Compare these three lines to 'hanoi 2 ...'. A -> B -- If you could find pattern here, C -> B -- you can swap these lines to 'hanoi 2 ...'. A -> C B -> A B -> C A -> C

The interesting way is to view the pegs not in a straight line but in another conic section ... -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey On Feb 15, 2015 12:54 PM, "Dudley Brooks" 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 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

That definitely makes the iterative solution easier to see. Not sure if it helps with seeing the recursive solution, but you're right, it *is* the "natural" way to do the Towers. On 2/15/15 7:10 PM, KC wrote:

The interesting way is to view the pegs not in a straight line but in another conic section ...

-- --

Sent from an expensive device which will be obsolete in a few months! :D

Casey

On Feb 15, 2015 12:54 PM, "Dudley Brooks" mailto:dbrooks@runforyourlife.org> 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 Beginners@haskell.org mailto:Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

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

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

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 mailto:dbrooks@runforyourlife.org> 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 Beginners@haskell.org mailto:Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org mailto: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

Regarding your last answer... 3. Only 2 ...let me suggest a different perspective. If we begin with n disks, then: First move everything except the bottom one to the spare peg. ​"everything except the bottom one" refers to ​( n ​ - 1)​ disks Move the bottom one to the goal peg. ​"the bottom one" refers to 1 disk​ Move everything else from the spare peg to the goal peg. ​"everything else" refers to ( n ​ - 1)​ disks So that moves the thought process toward the "fancier recursion pattern" per Doug McIlroy's excellent summary. On Tue, Feb 17, 2015 at 6:23 AM, Roelof Wobben wrote:

Joel Neely schreef op 17-2-2015 om 13:05:

​Let's tweak your answers​ just a bit, calling the three pegs the "source", "goal", and "spare" pegs:

On Tue, Feb 17, 2015 at 5:23 AM, Roelof Wobben wrote:

...

- Where do I move the bottom (largest disk) ?

To the last peg, which do not contain any disk then ​ .

From the source peg to the goal peg, which will /must not contain any disks.​

...

​

- What must happen before I can move the bottom disk ?

I have to move the disk which above that disk.

Move everything else from source to sparel peg.​

...

- What must happen after I move the bottom disk ?

All the other disk must be placed above that disk.

​ Move everything else from spare to goal.​

​So more questions/hints:

1. How do you fill in the blanks? 2. How do you put the three statements in order? 3. How many disks does each statement talk about?

-jn- ​

1. I did already. 2. First move everything except the bottom one to the spare peg. Move the bottom one to the goal peg. Move everything else from the spare peg to the goal peg.

3. Only 2

Roelof

_______________________________________________ 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

On Feb 17, 2015 10:18 AM, "Roelof Wobben" wrote:

This part I understand well.

So you could do something like this:

hanoi n 1 2 3 | n = 0 -> moves the last disk to the goal peg | n != 0 -> moves all the other disk to the spare peg or to the moves

n -1 to the goal peg What does n represent here?

On Feb 17, 2015 10:50 AM, "Roelof Wobben" wrote:

N reprent the number of disk

So how does moving 0 disks happen? That is what your first case deals with.

Roelof

Mike Meyer schreef op 17-2-2015 om 17:47:

...

On Feb 17, 2015 10:18 AM, "Roelof Wobben" wrote:

...

This part I understand well.

So you could do something like this:

hanoi n 1 2 3 | n = 0 -> moves the last disk to the goal peg | n != 0 -> moves all the other disk to the spare peg or to the

moves n -1 to the goal peg

...

What does n represent here?

_______________________________________________ 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

hanoi 1 p1 _ p3 = move 1 disc from p1 to p3 hanoi n p1 p2 p3 = move n discs from p1 to p3 using p2 in between The definition of the first equation is easy. To complete the second equation, you need to use hanoi again recursively. I detailed a way to complete the second equation in my previous mail (which hopefully didn't spoil it). Hope this helps. On 17 February 2015 at 22:39, Roelof Wobben wrote:

Stupid error

Then it must be like this :

hanoi n 1 2 3 | n = 1 -> moves the last disk to the goal peg | n > 1 -> moves all the other disk to the spare peg or to the moves n -1 to the goal peg

Roelof

Mike Meyer schreef op 17-2-2015 om 17:57:

On Feb 17, 2015 10:50 AM, "Roelof Wobben" wrote:

...

N reprent the number of disk

So how does moving 0 disks happen? That is what your first case deals with.

...

Roelof

Mike Meyer schreef op 17-2-2015 om 17:47:

...

On Feb 17, 2015 10:18 AM, "Roelof Wobben" wrote:

...

This part I understand well.

So you could do something like this:

hanoi n 1 2 3 | n = 0 -> moves the last disk to the goal peg | n != 0 -> moves all the other disk to the spare peg or to the

moves n -1 to the goal peg

...

What does n represent here?

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

-- Regards Sumit Sahrawat

Um ... To the other people giving hints: Don't forget that in the sequence *of lines in the program* you have to state the base case(s) *first*, certainly in Haskell, which goes through the lines in order, until it finds a match. That's what I meant when I said "first do the base case(s), then the rest": first *in the program order*, if not necessarily in the conceptual structure. So for the depth-first binary tree which Joel Neely pointed out, *first* you must deal with the base case that the node being looked at is actually a leaf; *only then* can you deal with the fact that in general the algorithm has the structure <process left descendants><process this node><process right descendants>. So if you try <move stack off of bottom><move bottom><place stack on bottom>, the first part will either enter an endless loop or will generate an error, because it doesn't have a base case. (No pun on "base" intended.) On 2/17/15 4:05 AM, Joel Neely wrote:

​Let's tweak your answers​ just a bit, calling the three pegs the "source", "goal", and "spare" pegs:

On Tue, Feb 17, 2015 at 5:23 AM, Roelof Wobben mailto:r.wobben@home.nl> wrote:

- Where do I move the bottom (largest disk) ?

To the last peg, which do not contain any disk then ​ .

From the source peg to the goal peg, which will /must not contain any disks.​

​

- What must happen before I can move the bottom disk ?

I have to move the disk which above that disk.

Move everything else from ____ to ____.​

- What must happen after I move the bottom disk ?

All the other disk must be placed above that disk.

​ Move everything else from ____ to ____.​

​So more questions/hints:

1. How do you fill in the blanks? 2. How do you put the three statements in order? 3. How many disks does each statement talk about?

-jn- ​

-- Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato

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

On 2/18/15 5:34 AM, Joel Neely wrote:

I believe that the assertion that "/in the sequence *of lines in the program* you have to state the base case(s) *first*/" is a bit too strong, although it is certainly correct to say that termination must be assured. For (a very trivial) example:

dupEvens :: [Int] -> [Int] dupEvens (n:ns) | even n = n : n : dupEvens ns | otherwise = n : dupEvens ns dupEvens [] = []

which behaves as:

*Main> dupEvens [3,1,4,1,5,9,2,6] [3,1,4,4,1,5,9,2,2,6,6] *Main> dupEvens [0..5] [0,0,1,2,2,3,4,4,5]

the base case for list recursion (the empty list) is stated last. That is not a problem because the inductive case (non-empty list) contains a pattern that won't match an empty list.

Hmm. Well, I'd say that that's a feature of, specifically, Haskell's pattern-matching strategy and list-description syntax, rather than of recursion in general or the structure of this particular problem. In other languages with recursion you might have no choice except to start with the base case, even for this problem, or else you'd get the same kind of error you mention below (depending on the language). I think it's good when you're *learning* recursion to always start with the base case(s).

So I suggest modifying the beginners' advice to something like:

/When evaluating a function, Haskell considers the parts of the definition in the order they are written, top-to-bottom, and uses the first one that matches. So make sure that your left-hand sides (patterns or guards) are precise enough to select the correct right-hand side is evaluated./

The (trivial *and horrible*) example:

badDupEvens :: [Int] -> [Int] badDupEvens ns | even (head ns) = (head ns) : (head ns) : badDupEvens (tail ns) | otherwise = (head ns) : badDupEvens (tail ns) badDupEvens [] = []

violates that advice, and gets its just desserts:

*Main> badDupEvens [0..5] [0,0,1,2,2,3,4,4,5*** Exception: Prelude.head: empty list

And, (again for us beginners) a good tip to help avoid such things is to place:

{-# OPTIONS_GHC -Wall #-}

at the beginning of each source file. This allows the compiler to complain at me:

trivialdemo.hs:12:1: Warning: Pattern match(es) are overlapped In an equation for ‘badDupEvens’: badDupEvens [] = ...

which (if I'm paying attention) makes me think about my patterns a bit more.

For what it's worth, I tend to try to make my patterns and guards precise enough that they can prevent divergence without too much reliance on lexical ordering. I picked up that habit almost 40 years ago, thanks to Dijkstra's "guarded command" notation in /A Discipline of Programming/.

Always nice to hear the "pioneers" mentioned!

I don't know to what extent that is (or isn't) idiomatic in the Haskell community.

On Tue, Feb 17, 2015 at 1:42 PM, Dudley Brooks mailto:dbrooks@runforyourlife.org> wrote:

Um ... To the other people giving hints: Don't forget that in the sequence *of lines in the program* you have to state the base case(s) *first*, certainly in Haskell, which goes through the lines in order, until it finds a match.

That's what I meant when I said "first do the base case(s), then the rest": first *in the program order*, if not necessarily in the conceptual structure. So for the depth-first binary tree which Joel Neely pointed out, *first* you must deal with the base case that the node being looked at is actually a leaf; *only then* can you deal with the fact that in general the algorithm has the structure <process left descendants><process this node><process right descendants>.

So if you try <move stack off of bottom><move bottom><place stack on bottom>, the first part will either enter an endless loop or will generate an error, because it doesn't have a base case. (No pun on "base" intended.)

On 2/17/15 4:05 AM, Joel Neely wrote:

...

​ Let's tweak your answers​ just a bit, calling the three pegs the "source", "goal", and "spare" pegs:

On Tue, Feb 17, 2015 at 5:23 AM, Roelof Wobben mailto:r.wobben@home.nl> wrote:

- Where do I move the bottom (largest disk) ?

To the last peg, which do not contain any disk then ​ .

From the source peg to the goal peg, which will /must not contain any disks.​

​

- What must happen before I can move the bottom disk ?

I have to move the disk which above that disk.

Move everything else from ____ to ____.​

- What must happen after I move the bottom disk ?

All the other disk must be placed above that disk.

​ Move everything else from ____ to ____.​

​ So more questions/hints:

1. How do you fill in the blanks? 2. How do you put the three statements in order? 3. How many disks does each statement talk about?

-jn- ​

-- Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato

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

_______________________________________________ Beginners mailing list Beginners@haskell.org mailto: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

Just to clarify the point of my earlier comment... I suggest that the "separation of concerns" (SOC) principle has many applications. A common use shows up in the advice to represent each distinct concept exactly one place in the code, and to do so in a way that supports orthogonality (the freedom to mix-and-match). In this case, I used it to separate the thought process of designing the code from the lexical layout of the code. I have no business legislating the order in which someone else thinks about the cases (sometimes more than two!) encountered in decomposing a problem. However, in my experience, the order in which I think about parts of the code, and the order in which they are laid out in the source file, are separate concerns. And I have often found it useful to consider them separately. For example, in some problems (and language implementations) it may help performance to ensure that the most frequent case is considered first, especially when there are multiple cases to consider or when the distinguishing conditions are costly to evaluate. I find that making my guards (conditions) explicit allows me the freedom to order the alternatives in whatever way I find useful, without having to worry about introducing a defect in the code. Incidentally, I also find it interesting to see the subtle effects that our terminology has on the way we approach problems. Thinking of a list as "it may be empty or not" takes my thoughts in a different direction than if I think "it may have a head or not". By all means, think about your recursive functions any way you wish! Just please don't tell me that I must place them is a specific order in my code. Regards, -jn- On Thu, Feb 19, 2015 at 3:02 AM, Dudley Brooks wrote:

On 2/18/15 5:29 PM, Mike Meyer wrote:

On Wed, Feb 18, 2015 at 7:16 PM, Dudley Brooks < dbrooks@runforyourlife.org> wrote:

...

Hmm. Well, I'd say that that's a feature of, specifically, Haskell's pattern-matching strategy and list-description syntax, rather than of recursion in general or the structure of this particular problem. In other languages with recursion you might have no choice except to start with the base case, even for this problem, or else you'd get the same kind of error you mention below (depending on the language). I think it's good when you're *learning* recursion to always start with the base case(s).

I disagree that this is a Haskell-specific feature. Any else-if like structure will have this property, no matter what language it's in. That Haskell provides a syntax as part of the function declaration is special, but that doesn't let you avoid the else-if construct when the problem requires it.

I don't understand. I don't believe I said anything about avoiding else-if, or about not avoiding it. But I'm not quite sure what you mean. Are you referring to

if condition1 then instruction1 elseif condition2 then instruction2

?

But what is condition1? Wouldn't it probably be the base case, and instruction1 the procedure on the base case?

Is there something special about "elseif" that guarantees that instruction1 *before* it won't crash if condition1 isn't the base case??? I'm probably totally missing your intention here.

But anyway, isn't it actually just Haskell's syntax "x:xs" that lets the pattern be tested and bypassed without crashing on an empty list, so that it *can* fall through to the base case at the end? If Haskell only had the syntax "(head xs), then that *would* crash on the empty list if the empty list had not previously been taken care of as a base case, as Joel Neely pointed out.

I didn't mean that *no* other language might have such a syntactical construction. (I didn't mean "specifically Haskell", I meant "specifically the pattern matching". Sorry about the ambiguity.) So if some other language has such a construction, then it's still the *syntax* that lets you cheat on the base case; it's not the structure of the problem itself nor the basic underlying notion of recursion.

I would also argue that in Mr Neely's first example, while the *explicit* base case [] is at the end, nevertheless the first line still *implicitly* refers to the base case: pattern matching on "x:xs" says "*if* the data has the structure x:xs", i.e. "if it is not a bunch of other stuff ... including *not the empty list*!)". Certainly you couldn't merely do the recursive step first without a condition like this particular one. The reason this syntax *seems* to let you avoid thinking about the base case first is because secretly it says "only try this step if we're not looking at the base case"!

It may be my fondness for proof by induction, but I think doing the base case first is a good idea for another reason. The code for the recursive cases assumes that you can correctly handle all the "smaller" cases. If that's wrong because some assumption about the base case turns out to be false when you actually write it, then you have to rewrite the recursive cases for the correct base case. So it's better to make sure your base case is going to work before you start writing the code that's going to use it.

I was a math major, not a CS major, so I'm also prejudiced in favor of base case first. And, as stated above, I think we *are* actually *considering* the base case first! (We're merely putting off telling what to *do* with that base case.) I think that the "syntactic sugar" of some languages obscures (intentionally, for purposes of convenience) what's really happening mathematically.

_______________________________________________ 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

And to clarify my point, I would say that mathematically you do always have to "take care of" (worry about) the base case first ... and you did! And in the code, not just in your thinking: Using "x:xs", rather than "(head xs)", in the first line acknowledges the base case by making sure to eliminate it first -- "x:xs" works precisely because it doesn't separate the *concerns*; it contains an implicit "if this is not the base case". What it does (why it's useful syntactic sugar) is let you separate (and reorder) the *actions*. A guard using "x:xs" does not actually have the very clean SOC which you recommend, with the result that the concept "base case" is actually represented in *two* places in your code. Question: Could you write it without the first line using "x:xs" or some other construction which has an implicit "if this is not the base case"? Probably yes ... probably some kind of "where" clause might put it typographically at the end. But that would be because Haskell's interpreter/compiler executes the test in the "where" clause first. Checking whether we're looking at the base case would still be the first major execution step. I suspect that there's no way to escape that ... the most that can be done is to "look like" you're escaping it. On 2/19/15 4:47 AM, Joel Neely wrote:

Just to clarify the point of my earlier comment...

I suggest that the "separation of concerns" (SOC) principle has many applications. A common use shows up in the advice to represent each distinct concept exactly one place in the code, and to do so in a way that supports orthogonality (the freedom to mix-and-match).

In this case, I used it to separate the thought process of designing the code from the lexical layout of the code.

I have no business legislating the order in which someone else thinks about the cases (sometimes more than two!) encountered in decomposing a problem. However, in my experience, the order in which I think about parts of the code, and the order in which they are laid out in the source file, are separate concerns. And I have often found it useful to consider them separately.

For example, in some problems (and language implementations) it may help performance to ensure that the most frequent case is considered first, especially when there are multiple cases to consider or when the distinguishing conditions are costly to evaluate.

I find that making my guards (conditions) explicit allows me the freedom to order the alternatives in whatever way I find useful, without having to worry about introducing a defect in the code.

Incidentally, I also find it interesting to see the subtle effects that our terminology has on the way we approach problems. Thinking of a list as "it may be empty or not" takes my thoughts in a different direction than if I think "it may have a head or not".

By all means, think about your recursive functions any way you wish! Just please don't tell me that I must place them is a specific order in my code.

Regards, -jn-

On Thu, Feb 19, 2015 at 3:02 AM, Dudley Brooks mailto:dbrooks@runforyourlife.org> wrote:

On 2/18/15 5:29 PM, Mike Meyer wrote:

...

On Wed, Feb 18, 2015 at 7:16 PM, Dudley Brooks mailto:dbrooks@runforyourlife.org> wrote:

Hmm. Well, I'd say that that's a feature of, specifically, Haskell's pattern-matching strategy and list-description syntax, rather than of recursion in general or the structure of this particular problem. In other languages with recursion you might have no choice except to start with the base case, even for this problem, or else you'd get the same kind of error you mention below (depending on the language). I think it's good when you're *learning* recursion to always start with the base case(s).

I disagree that this is a Haskell-specific feature. Any else-if like structure will have this property, no matter what language it's in. That Haskell provides a syntax as part of the function declaration is special, but that doesn't let you avoid the else-if construct when the problem requires it.

I don't understand. I don't believe I said anything about avoiding else-if, or about not avoiding it. But I'm not quite sure what you mean. Are you referring to

if condition1 then instruction1 elseif condition2 then instruction2

?

But what is condition1? Wouldn't it probably be the base case, and instruction1 the procedure on the base case?

Is there something special about "elseif" that guarantees that instruction1 *before* it won't crash if condition1 isn't the base case??? I'm probably totally missing your intention here.

But anyway, isn't it actually just Haskell's syntax "x:xs" that lets the pattern be tested and bypassed without crashing on an empty list, so that it *can* fall through to the base case at the end? If Haskell only had the syntax "(head xs), then that *would* crash on the empty list if the empty list had not previously been taken care of as a base case, as Joel Neely pointed out.

I didn't mean that *no* other language might have such a syntactical construction. (I didn't mean "specifically Haskell", I meant "specifically the pattern matching". Sorry about the ambiguity.) So if some other language has such a construction, then it's still the *syntax* that lets you cheat on the base case; it's not the structure of the problem itself nor the basic underlying notion of recursion.

I would also argue that in Mr Neely's first example, while the *explicit* base case [] is at the end, nevertheless the first line still *implicitly* refers to the base case: pattern matching on "x:xs" says "*if* the data has the structure x:xs", i.e. "if it is not a bunch of other stuff ... including *not the empty list*!)". Certainly you couldn't merely do the recursive step first without a condition like this particular one. The reason this syntax *seems* to let you avoid thinking about the base case first is because secretly it says "only try this step if we're not looking at the base case"!

...

It may be my fondness for proof by induction, but I think doing the base case first is a good idea for another reason. The code for the recursive cases assumes that you can correctly handle all the "smaller" cases. If that's wrong because some assumption about the base case turns out to be false when you actually write it, then you have to rewrite the recursive cases for the correct base case. So it's better to make sure your base case is going to work before you start writing the code that's going to use it.

I was a math major, not a CS major, so I'm also prejudiced in favor of base case first. And, as stated above, I think we *are* actually *considering* the base case first! (We're merely putting off telling what to *do* with that base case.) I think that the "syntactic sugar" of some languages obscures (intentionally, for purposes of convenience) what's really happening mathematically.

_______________________________________________ Beginners mailing list Beginners@haskell.org mailto: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

(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 mailto:dbrooks@runforyourlife.org> 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 Beginners@haskell.org mailto:Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

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