Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Haskell implementation of longest path algorithm (Jeremy)
2. Re: tower hanoi problem (Dudley Brooks)
----------------------------------------------------------------------
Message: 1
Date: Thu, 19 Feb 2015 08:56:33 +0000 (UTC)
From: Jeremy <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Haskell implementation of longest path
algorithm
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Compared to the Nim code
[https://github.com/logicchains/LPATHBench/blob/master/nim.nim] for a
longest path algorithm, Haskell
[https://github.com/logicchains/LPATHBench/blob/master/hs.hs] looks
horrendously verbose and ugly, even if you ignore the pragmas and imports.
Is this idiomatic Haskell style? Could it be clearer, but has to be written
that way for performance - although it still takes 3.7x as long as the Nim
version [https://github.com/logicchains/LPATHBench/blob/master/writeup.md]?
------------------------------
Message: 2
Date: Thu, 19 Feb 2015 01:02:43 -0800
From: Dudley Brooks <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"; Format="flowed"
On 2/18/15 5:29 PM, Mike Meyer wrote:
> On Wed, Feb 18, 2015 at 7:16 PM, Dudley Brooks
> <[email protected] <mailto:[email protected]>> 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-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 80, Issue 50
*****************************************
