[Haskell-beginners] Fwd: tower hanoi problem
Dudley Brooks
dbrooks at runforyourlife.org
Sat Feb 21 19:19:18 UTC 2015
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.
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).
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.)
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.
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.
At heart, the rearrangement really just changes
If you're looking at the base case
then process the base case
else process the recursive case
into
if you're not looking at the base case
then process the recursive case
else process the base case.
(Leaving out details ... including cases which are neither the base
cases nor the recursive cases.)
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! ;^)
Perhaps I'm speaking more like a language designer (which I certainly
don't happen to be, btw) than like a language user.
On 2/21/15 7:50 AM, Joel Neely wrote:
> 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.
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.
> 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
> smooth _ = []
>
Yes, this is definitely more elegant. BTW -- notice that here the first
"[n]" 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.)
> 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' [] = []
> smooth' [_] = []
> smooth' [_,_] = []
> 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 smoothhaving 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 at runforyourlife.org
> <mailto:dbrooks at runforyourlife.org>>
> Date: Thu, Feb 19, 2015 at 9:48 AM
> Subject: Re: [Haskell-beginners] tower hanoi problem
> To: Joel Neely <joel.neely at gmail.com <mailto:joel.neely at 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-
>>
>>
>>
>> On Thu, Feb 19, 2015 at 3:02 AM, Dudley Brooks
>> <dbrooks at runforyourlife.org <mailto:dbrooks at runforyourlife.org>> wrote:
>>
>> On 2/18/15 5:29 PM, Mike Meyer wrote:
>>> On Wed, Feb 18, 2015 at 7:16 PM, Dudley Brooks
>>> <dbrooks at runforyourlife.org <mailto:dbrooks at runforyourlife.org>>
>>> wrote:
>>>
>>> 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).
>>>
>>> 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.
>> 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
>>
>> if condition1
>> then instruction1
>> elseif condition2
>> then instruction2
>>
>> ?
>>
>> But what is condition1? Wouldn't it probably be the base case,
>> and instruction1 the procedure on the base case?
>>
>> 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.
>>
>> 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.
>>
>> 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.
>>
>> 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"!
>>> 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.
>> 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.
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org <mailto:Beginners at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>>
>>
>> --
>> Beauty of style and harmony and grace and good rhythm depend on
>> simplicity. - Plato
>
>
>
>
> --
> Beauty of style and harmony and grace and good rhythm depend on
> simplicity. - Plato
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150221/1a4f9dc6/attachment-0001.html>
More information about the Beginners
mailing list