<div dir="ltr"><div class="gmail_default" style="font-family:georgia,serif;font-size:small">I personally find the assertion more confusing than helpful. Interpreting a pattern of "x:xs" as "acknowledging the base case" by eliminating it first reads to me as a double negative: "if it is not the case that this list does not have a first element" or some such.</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 simply prefer to read it as a positive assertion: the list has a head, and here's what to do with it.</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">To my eye, this also scales nicely when there are multiple terminal cases. Here's a tiny example.</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">Given a list of fractional numbers, produce a smoothed list, where each value is averaged with its immediate neighbors (except the first and last, which fail to have both neighbors), as shown below.</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 face="monospace, monospace">[0.0,4.0,2.0,6.0,1.0,2.0]</font></div><div class="gmail_default" style><font face="monospace, monospace">[ 2.0,4.0,3.0,3.0 ]</font></div></blockquote><div class="gmail_default" style><font face="georgia, serif"><br></font></div><div class="gmail_default" style><font face="georgia, serif">It seems natural to my eye to express this as, "A list with at least three elements contributes a value to the result", as in:</font></div><div class="gmail_default" style><font face="georgia, serif"><br></font></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth :: Fractional n => [n] -> [n]</font></div></div><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth (a:z@(b:c:_)) = (a + b + c) / 3 : smooth z</font></div></div><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth _ = []</font></div></div></blockquote><div class="gmail_default" style><font face="georgia, serif"><div><br></div></font></div><div class="gmail_default" style><font face="georgia, serif">I prefer this to the alternatives (at least the ones that I came up with) that either explicitly compute the length to compare it to 3, or that explicitly fret over the (multiple!) cases that terminate the recursion.</font></div><div class="gmail_default" style><font face="georgia, serif"><br></font></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth' :: Fractional n => [n] -> [n]</font></div></div><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth' [] = []</font></div></div><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth' [_] = []</font></div></div><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth' [_,_] = []</font></div></div><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">smooth' (a:z@(b:c:_)) = (a + b + c) / 3 : smooth' z</font></div></div></blockquote><div class="gmail_default" style><div style="font-family:georgia,serif"><br></div></div><div class="gmail_default" style><font face="georgia, serif">I don't care for having to wade through three terminal cases to get to the one that interests me, for multiple reasons:</font></div><div class="gmail_default" style><ul><li><span style="font-family:georgia,serif">It strikes my eye as visual noise that offers no useful information compared to the first (shorter) solution.</span><br></li><li><span style="font-family:georgia,serif">Depending on the intelligence of the compiler, it may waste run time by testing for cases that will only be true near the end of a long argument list.</span><br></li><li><font face="georgia, serif">I can argue termination by observing that the recursive evaluation (</font><font face="monospace, monospace">smooth z</font><font face="georgia, serif">) is made on a shorter argument.</font><br></li><li><span style="font-family:georgia,serif">In a lazy language, termination may not be an issue!</span><br></li></ul></div><div class="gmail_default" style><span style="font-family:georgia,serif">Evaluating</span><br></div><div class="gmail_default" style><font face="georgia, serif"><br></font></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">*Main> take 10 $ smooth [0,1..]</font></div></div><div class="gmail_default" style><div class="gmail_default"><font face="monospace, monospace">[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0]</font></div></div></blockquote><div class="gmail_default" style><div style="font-family:georgia,serif"><br></div></div><div class="gmail_default" style><font face="georgia, serif">works just fine without </font><font face="monospace, monospace">smooth</font><font face="georgia, serif"> having to arrive at the end of its argument.</font></div><div class="gmail_default" style><font face="georgia, serif"><br></font></div><div class="gmail_default" style><font face="georgia, serif">Again, tastes may vary.</font></div><div class="gmail_default" style><font face="georgia, serif"><br></font></div><div class="gmail_default" style><font face="georgia, serif">I haven't thought of a way to do this with a fold or comprehension that seems as clear to me. I would be interested in seeing such a solution if someone else sees a way to do it.</font></div><div class="gmail_default" style><font face="georgia, serif"><br></font></div><div class="gmail_default" style><font face="georgia, serif">-jn-</font></div><div class="gmail_default" style><font face="georgia, serif"><br></font></div><div class="gmail_quote"><br></div><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Dudley Brooks</b> <span dir="ltr"><<a href="mailto:dbrooks@runforyourlife.org">dbrooks@runforyourlife.org</a>></span><br>Date: Thu, Feb 19, 2015 at 9:48 AM<br>Subject: Re: [Haskell-beginners] tower hanoi problem<br>To: Joel Neely <<a href="mailto:joel.neely@gmail.com">joel.neely@gmail.com</a>><br><br><br>
<div bgcolor="#FFFFFF" text="#000000">
<div>And to clarify my point, I would say
that mathematically you do always have to "take care of" (worry
about) the base case first ... and you did! And in the code, not
just in your thinking: Using "x:xs", rather than "(head xs)", in
the first line acknowledges the base case by making sure to
eliminate it first -- "x:xs" works precisely because it doesn't
separate the *concerns*; it contains an implicit "if this is not
the base case". What it does (why it's useful syntactic sugar) is
let you separate (and reorder) the *actions*. A guard using
"x:xs" does not actually have the very clean SOC which you
recommend, with the result that the concept "base case" is
actually represented in *two* places in your code.<br>
<br>
Question: Could you write it without the first line using "x:xs"
or some other construction which has an implicit "if this is not
the base case"? Probably yes ... probably some kind of "where"
clause might put it typographically at the end. But that would be
because Haskell's interpreter/compiler executes the test in the
"where" clause first. Checking whether we're looking at the base
case would still be the first major execution step. I suspect
that there's no way to escape that ... the most that can be done
is to "look like" you're escaping it.<div><div class="h5"><br>
<br>
On 2/19/15 4:47 AM, Joel Neely wrote:<br>
</div></div></div><div><div class="h5">
<blockquote type="cite">
<div dir="ltr">
<div style="font-family:georgia,serif;font-size:small">Just to
clarify the point of my earlier comment...</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">I suggest
that the "separation of concerns" (SOC) principle has many
applications. A common use shows up in the advice to represent
each distinct concept exactly one place in the code, and to do
so in a way that supports orthogonality (the freedom to
mix-and-match).</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">In this
case, I used it to separate the thought process of designing
the code from the lexical layout of the code.</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">I have no
business legislating the order in which someone else thinks
about the cases (sometimes more than two!) encountered in
decomposing a problem. However, in my experience, the order in
which I think about parts of the code, and the order in which
they are laid out in the source file, are separate concerns.
And I have often found it useful to consider them separately.</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">For example,
in some problems (and language implementations) it may help
performance to ensure that the most frequent case is
considered first, especially when there are multiple cases to
consider or when the distinguishing conditions are costly to
evaluate.</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">I find that
making my guards (conditions) explicit allows me the freedom
to order the alternatives in whatever way I find useful,
without having to worry about introducing a defect in the
code.</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">Incidentally,
I also find it interesting to see the subtle effects that our
terminology has on the way we approach problems. Thinking of a
list as "it may be empty or not" takes my thoughts in a
different direction than if I think "it may have a head or
not".</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">By all
means, think about your recursive functions any way you wish!
Just please don't tell me that I must place them is a specific
order in my code.</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small">Regards,</div>
<div style="font-family:georgia,serif;font-size:small">-jn-</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
<div style="font-family:georgia,serif;font-size:small"><br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, Feb 19, 2015 at 3:02 AM, 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: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"><span>
<div>On 2/18/15 5:29 PM, Mike Meyer wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">On Wed, Feb 18, 2015 at
7:16 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: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>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>
</div>
</div>
</blockquote>
</div>
</div>
<div class="gmail_extra">I disagree that this is a
Haskell-specific feature. Any else-if like
structure will have this property, no matter what
language it's in. That Haskell provides a syntax
as part of the function declaration is special,
but that doesn't let you avoid the else-if
construct when the problem requires it.</div>
</div>
</blockquote>
</span> I don't understand. I don't believe I said
anything about avoiding else-if, or about not avoiding
it. But I'm not quite sure what you mean. Are you
referring to<br>
<br>
if condition1<br>
then instruction1<br>
elseif condition2<br>
then instruction2<br>
<br>
?<br>
<br>
But what is condition1? Wouldn't it probably be the base
case, and instruction1 the procedure on the base case?<br>
<br>
Is there something special about "elseif" that guarantees
that instruction1 *before* it won't crash if condition1
isn't the base case??? I'm probably totally missing your
intention here.<br>
<br>
But anyway, isn't it actually just Haskell's syntax "x:xs"
that lets the pattern be tested and bypassed without
crashing on an empty list, so that it *can* fall through
to the base case at the end? If Haskell only had the
syntax "(head xs), then that *would* crash on the empty
list if the empty list had not previously been taken care
of as a base case, as Joel Neely pointed out.<br>
<br>
I didn't mean that *no* other language might have such a
syntactical construction. (I didn't mean "specifically
Haskell", I meant "specifically the pattern matching".
Sorry about the ambiguity.) So if some other language has
such a construction, then it's still the *syntax* that
lets you cheat on the base case; it's not the structure of
the problem itself nor the basic underlying notion of
recursion.<br>
<br>
I would also argue that in Mr Neely's first example, while
the *explicit* base case [] is at the end, nevertheless
the first line still *implicitly* refers to the base
case: pattern matching on "x:xs" says "*if* the data has
the structure x:xs", i.e. "if it is not a bunch of other
stuff ... including *not the empty list*!)". Certainly
you couldn't merely do the recursive step first without a
condition like this particular one. The reason this
syntax *seems* to let you avoid thinking about the base
case first is because secretly it says "only try this step
if we're not looking at the base case"!<span><br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">It may be my fondness for
proof by induction, but I think doing the base
case first is a good idea for another reason. The
code for the recursive cases assumes that you can
correctly handle all the "smaller" cases. If
that's wrong because some assumption about the
base case turns out to be false when you actually
write it, then you have to rewrite the recursive
cases for the correct base case. So it's better to
make sure your base case is going to work before
you start writing the code that's going to use it.</div>
</div>
</blockquote>
</span> I was a math major, not a CS major, so I'm also
prejudiced in favor of base case first. And, as stated
above, I think we *are* actually *considering* the base
case first! (We're merely putting off telling what to
*do* with that base case.) I think that the "syntactic
sugar" of some languages obscures (intentionally, for
purposes of convenience) what's really happening
mathematically.<br>
<br>
</div>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">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>Beauty of style and harmony and
grace and good rhythm depend on simplicity. - Plato</div>
</div>
</blockquote>
<br>
</div></div></div>
</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>