[Haskell-beginners] tower hanoi problem
Dudley Brooks
dbrooks at runforyourlife.org
Thu Feb 19 01:16:18 UTC 2015
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
> <dbrooks at runforyourlife.org <mailto: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
>> <mailto: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 list
>> Beginners at haskell.org <mailto:Beginners at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org <mailto: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/ab75f873/attachment-0001.html>
More information about the Beginners
mailing list