<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">I guess I should refine my comment to
say that *by the time the computer is actually executing the
computation* (i.e. not in the programming stage), the base cases
*must* be eliminated first, or the execution *will* either crash
or enter an infinite loop when it encounters them.<br>
<br>
Certainly your point is correct, that languages like Haskell let
you arrange this differently typologically and "conceptually".
But I stand by my claim that the very reason you are able to do so
is because the pattern is an implicit "if" statement: "If the
input has the pattern a:z@(b:c:_) ... and therefore does not have
any other pattern ... including the pattern of the base cases"!
In testing what something is, you are also testing that it is not
anything else. This may not be important to your thinking as a
programmer, but it's definitely important to the computer. The
first statement *does* eliminate the base cases (among many others
which it eliminates).<br>
<br>
There could be lots of other first lines you could write which
would *not* work, precisely because they don't eliminate the base
cases. (As in the "bad" example you showed for comparison in the
previous response.)<br>
<br>
You're certainly right about the fact that with lazy evaluation
the base cases might never be reached (depending on what
*subsequent* function calls this one). Nevertheless, your first
line still *is* testing for (not) the base cases.<br>
<br>
So Haskell-like languages definitely give you the ability to
"present" the algorithm in ways that are more intuitive for you
(and possibly more efficient, too, as you point out) -- which is
great! That's what high-level languages should do. But it
doesn't give you a way to do so without the first line *somehow*
taking care of the base cases, even if only by temporarily
shunting them aside.<br>
<br>
At heart, the rearrangement really just changes<br>
<br>
If you're looking at the base case<br>
then process the base case<br>
else process the recursive case<br>
<br>
into<br>
<br>
if you're not looking at the base case<br>
then process the recursive case<br>
else process the base case.<br>
<br>
(Leaving out details ... including cases which are neither the
base cases nor the recursive cases.)<br>
<br>
So you actually *did* program testing for the base cases first ...
possibly without even thinking about that fact, because Haskell,
being a very high-level language, did some of the thinking for
you! ;^)<br>
<br>
Perhaps I'm speaking more like a language designer (which I
certainly don't happen to be, btw) than like a language user.<br>
<br>
On 2/21/15 7:50 AM, Joel Neely wrote:<br>
</div>
<blockquote
cite="mid:CAEEzXAj3AuWz0Pe2AqtLGTa49rFncJrWmwpP9Em=6OjdN+4s9Q@mail.gmail.com"
type="cite">
<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>
</blockquote>
<br>
More precisely: "IF the list has a head, THEN here's what to do with
it". Pattern matching is not an assertion, it's a test.<br>
<br>
<blockquote
cite="mid:CAEEzXAj3AuWz0Pe2AqtLGTa49rFncJrWmwpP9Em=6OjdN+4s9Q@mail.gmail.com"
type="cite">
<div dir="ltr">
<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>
</blockquote>
<font face="monospace, monospace"><br>
Yes, this is definitely more elegant. BTW -- notice that here the
first "[n]"</font> also does part of the job that otherwise the
first line would have to do, namely eliminate the bad cases (not
even a list) that the first line would otherwise have to eliminate
in languages without type checking. Once again, Haskell -- maybe
*because* it's a high-level language? -- does not *quite* have a
really clear SOC! (I'm treating "is it safe to do the recursion?"
as *one* concern. But probably the question "are the concerns well
separated?" is rather subjective.)<br>
<br>
<blockquote
cite="mid:CAEEzXAj3AuWz0Pe2AqtLGTa49rFncJrWmwpP9Em=6OjdN+4s9Q@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_default" style=""><font face="georgia, serif">
<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>
</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 moz-do-not-send="true"
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 moz-do-not-send="true"
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
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: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
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: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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org"
target="_blank">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>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>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Beginners mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Beginners@haskell.org">Beginners@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
</body>
</html>