<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 2/18/15 5:34 AM, Joel Neely wrote:<br>
</div>
<blockquote
cite="mid:CAEEzXAj6jkngpbW4cZVhNRgv9N7SP85AMxWgQ5wEoPxRHxpwkA@mail.gmail.com"
type="cite">
<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>
</blockquote>
<br>
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).<br>
<br>
<blockquote
cite="mid:CAEEzXAj6jkngpbW4cZVhNRgv9N7SP85AMxWgQ5wEoPxRHxpwkA@mail.gmail.com"
type="cite">
<div dir="ltr">
<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>
</blockquote>
<br>
Always nice to hear the "pioneers" mentioned!<br>
<br>
<blockquote
cite="mid:CAEEzXAj6jkngpbW4cZVhNRgv9N7SP85AMxWgQ5wEoPxRHxpwkA@mail.gmail.com"
type="cite">
<div dir="ltr">
<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 moz-do-not-send="true"
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
moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
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>
</blockquote>
<br>
</body>
</html>