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.
I simply prefer to read it as a positive assertion: the list has a head, and here's what to do with it.
To my eye, this also scales nicely when there are multiple terminal cases. Here's a tiny example.
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.
[0.0,4.0,2.0,6.0,1.0,2.0]
[ 2.0,4.0,3.0,3.0 ]
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:
smooth :: Fractional n => [n] -> [n]
smooth (a:z@(b:c:_)) = (a + b + c) / 3 : smooth z
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.
smooth' :: Fractional n => [n] -> [n]
smooth' (a:z@(b:c:_)) = (a + b + c) / 3 : smooth' z
I don't care for having to wade through three terminal cases to get to the one that interests me, for multiple reasons:
- It strikes my eye as visual noise that offers no useful information compared to the first (shorter) solution.
- 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.
- I can argue termination by observing that the recursive evaluation (smooth z) is made on a shorter argument.
- In a lazy language, termination may not be an issue!
Evaluating
*Main> take 10 $ smooth [0,1..]
[1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0]
works just fine without smooth having to arrive at the end of its argument.
Again, tastes may vary.
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.
-jn-
---------- Forwarded message ----------
From:
Dudley Brooks <dbrooks@runforyourlife.org>Date: Thu, Feb 19, 2015 at 9:48 AM
Subject: Re: [Haskell-beginners] tower hanoi problem
To: Joel Neely <
joel.neely@gmail.com>
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.
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.
On 2/19/15 4:47 AM, Joel Neely wrote:
Just to
clarify the point of my earlier comment...
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).
In this
case, I used it to separate the thought process of designing
the code from the lexical layout of the code.
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.
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.
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.
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".
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.
Regards,
-jn-
--
Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato