[Haskell-beginners] tower hanoi problem

[Joel Neely]

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 <dbrooks at 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 <r.wobben at 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 listBeginners at haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150218/9d50caf4/attachment.html>