<div dir="ltr"><div class="gmail_default" style="font-family:georgia,serif;font-size:small">I believe that the assertion that "<span style="font-size:12.8000001907349px;font-family:arial,sans-serif"><i>in the sequence *of lines in the program* you have to state the base case(s) *first*</i></span>" is a bit too strong, although it is certainly correct to say that termination must be assured. For (a very trivial) example:</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div class="gmail_default" style><div class="gmail_default" style><font face="monospace, monospace">dupEvens :: [Int] -> [Int]</font></div></div><div class="gmail_default" style><div class="gmail_default" style><font face="monospace, monospace">dupEvens (n:ns)</font></div></div><div class="gmail_default" style><div class="gmail_default" style><font face="monospace, monospace"> | even n = n : n : dupEvens ns</font></div></div><div class="gmail_default" style><div class="gmail_default" style><font face="monospace, monospace"> | otherwise = n : dupEvens ns</font></div></div><div class="gmail_default" style><div class="gmail_default" style><font face="monospace, monospace">dupEvens [] = []</font></div></div></blockquote><div class="gmail_default" style><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">which behaves as:</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">*Main> dupEvens [3,1,4,1,5,9,2,6]</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">[3,1,4,4,1,5,9,2,2,6,6]</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">*Main> dupEvens [0..5]</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">[0,0,1,2,2,3,4,4,5]</font></div></div></blockquote><div class="gmail_default" style="font-size:small"><div style="font-family:georgia,serif"><br></div></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">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.</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">So I suggest modifying the beginners' advice to something like:</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><i>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.</i></div></blockquote><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">The (trivial <b>and horrible</b>) example:</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">badDupEvens :: [Int] -> [Int]</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">badDupEvens ns</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace"> | even (head ns) = (head ns) : (head ns) : badDupEvens (tail ns)</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace"> | otherwise = (head ns) : badDupEvens (tail ns)</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">badDupEvens [] = []</font></div></div></blockquote><div class="gmail_default" style="font-size:small"><div style="font-family:georgia,serif"><br></div></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">violates that advice, and gets its just desserts:</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">*Main> badDupEvens [0..5]</font></div></div><div class="gmail_default" style="font-size:small"><div class="gmail_default"><font face="monospace, monospace">[0,0,1,2,2,3,4,4,5*** Exception: Prelude.head: empty list</font></div></div></blockquote><div class="gmail_default" style="font-size:small"><div style="font-family:georgia,serif"><br></div></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">And, (again for us beginners) a good tip to help avoid such things is to place:</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_default" style><div class="gmail_default" style="font-size:small"><span style="font-family:georgia,serif">{</span><font face="monospace, monospace">-# OPTIONS_GHC -Wall #-}</font></div></div></blockquote><div class="gmail_default" style><div style="font-family:georgia,serif;font-size:small"><br></div><div style="font-family:georgia,serif;font-size:small">at the beginning of each source file. This allows the compiler to complain at me:</div><div style="font-family:georgia,serif;font-size:small"><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_default" style><div style><div style><font face="monospace, monospace">trivialdemo.hs:12:1: Warning:</font></div></div></div><div class="gmail_default" style><div style><div style><font face="monospace, monospace"> Pattern match(es) are overlapped</font></div></div></div><div class="gmail_default" style><div style><div style><font face="monospace, monospace"> In an equation for ‘badDupEvens’: badDupEvens [] = ...</font></div></div></div></blockquote><div class="gmail_default" style><div style="font-family:georgia,serif;font-size:small"><br></div><div style="font-size:small"><span style="font-family:georgia,serif">which (if I'm paying attention) makes me think about my patterns a bit more.</span></div><div style="font-family:georgia,serif;font-size:small"><br></div><div style="font-family:georgia,serif;font-size:small">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 <i>A Discipline of Programming</i>.</div></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">I don't know to what extent that is (or isn't) idiomatic in the Haskell community.</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Feb 17, 2015 at 1:42 PM, Dudley Brooks <span dir="ltr"><<a href="mailto:dbrooks@runforyourlife.org" target="_blank">dbrooks@runforyourlife.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>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.<br>
<br>
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>.<br>
<br>
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.)<div><div class="h5"><br>
<br>
On 2/17/15 4:05 AM, Joel Neely wrote:<br>
</div></div></div>
<blockquote type="cite"><div><div class="h5">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">Let's
tweak your answers just a bit, calling the three pegs the
"source", "goal", and "spare" pegs:</div>
<br>
<div class="gmail_quote">On Tue, Feb 17, 2015 at 5:23 AM,
Roelof Wobben <span dir="ltr"><<a href="mailto:r.wobben@home.nl" target="_blank">r.wobben@home.nl</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">- Where do I move
the bottom (largest disk) ? <br>
<br>
To the last peg, which do not contain any disk then
<div class="gmail_default" style="font-family:georgia,serif;font-size:small;display:inline">
.</div>
</div>
</blockquote>
<div><br>
</div>
<div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small;display:inline">From
the source peg to the goal peg, which will</div>
<span style="font-family:georgia,serif">/must</span>
<div class="gmail_default" style="font-family:georgia,serif;display:inline"> not
contain any disks.</div>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div class="gmail_default" style="font-family:georgia,serif;font-size:small;display:inline"></div>
<br>
<br>
- What must happen before I can move the bottom disk ? <br>
<br>
I have to move the disk which above that disk. <br>
</div>
</blockquote>
<div><br>
</div>
<div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small;display:inline">Move
everything else from ____ to ____.</div>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
- What must happen after I move the bottom disk ?<br>
<br>
All the other disk must be placed above that disk. <br>
</div>
</blockquote>
<div><br>
</div>
<div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small;display:inline">
Move everything else from ____ to ____.</div>
</div>
</div>
<br>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">So more
questions/hints:</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">
<ol>
<li>How do you fill in the blanks?<br>
</li>
<li>How do you put the three statements in order?<br>
</li>
<li>How many disks does each statement talk about?<br>
</li>
</ol>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">-jn-</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"></div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
<div>Beauty of style and harmony and
grace and good rhythm depend on simplicity. - Plato</div>
</div>
</div>
<br>
<fieldset></fieldset>
<br>
</div></div><span class=""><pre>_______________________________________________
Beginners mailing list
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</span></blockquote>
<br>
</div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato</div>
</div>