Re: [Haskell-beginners] tower hanoi problem

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