[Haskell-beginners] tower hanoi problem

[Dudley Brooks]

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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150219/452ab344/attachment.html>