Re: [Haskell-beginners] tower hanoi problem

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

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