[Haskell-cafe] Tutorial: Haskell for the Evil Genius

[Alex Stangl]

On Fri, Sep 14, 2012 at 05:18:24PM -0400, Andrew Pennebaker wrote:
> A summary of the changes I've included so far:
> > Under Declarative, you aren't creating a "named expression, 2 + 2", really.
> > You are redefining (+).
> Noted and reflected in the new version.

It may not be obvious to readers when you are putting (+) or fib in the
let clause, that you are shadowing the function in the outer scope, so
for example, a reader might be surprised at the results of trying
let 2 + 2 = 5 in 1 + 1
(or similar experiments with your "memoized" fib)

It's not clear whether you believe you are only overriding behavior for
the specific case of 2 + 2, or if you realize that you've completely
redefined (+).


> Noted and reflected in the new version. After several comments to this
> effect, I do not want to misrepresent memoization in the tutorial.
> Sometimes it is useful to be slightly inaccurate in a tutorial in order to
> help bridge the gap between someone with no experience in a something vs
> the wealth of knowledge and complexity in the thing itself. This is not one
> of those times, and fortunately, fixing the misrepresentation in my
> tutorial is as easy as removing the hardcoded call.
> 
> One thing I want to double check is that Haskell does, in fact,
> automatically memoize all pure function calls. Is this true?

Generally you store the memoized results in some structure list a list
or array defined at the top level. You don't get "automatic"
memoization, nor would it be desirable since it would quickly fill
memory with memoized results of every function call, unless it could
intelligently gauge which ones to keep around. Check out the memoization
section of the Haskell wiki for more info.


> I would still like to provide a performance comparison of the Fibonacci
> code with and without memoization, for readers who enjoy numerical
> evidence, using the Unix "time" command, but I don't know how to turn
> memoization off. I guess I would have to reimplement the algorithm in a way
> that can't make use of memoization. Any suggestions?

See above. Off is default -- you need to add an array to get the
memoization. The array can be initialized with the lazy list of fibs,
which in turn rely upon the array itself to retrieve memoized values.
Downside to this approach is you need to define your array bounds
upfront. Alternately, you could memoize more simply (and w/o bounds)
by putting the values into a top-level list, however the values get
more expensive to access, the deeper they are in the list.


> Under Infinite, you should use "sieve (n:ns)" pattern matching instead of
> > calling head.
> Thank you! I try to make use of Haskell pattern matching wherever I can.
> Since I needed to refer to the whole list, as well as the head and tail, I
> originally used "head" instead of pattern matching. Noted and reflected in
> the new version.

Are you aware you can use an "as pattern" (e.g., nl@(n:ns)) so you can
refer to the whole list as nl when you like, but still have destructured
as well?


> > Under Type-Safe
> > Subtle distinction, but returning () is not the same as returning nothing
> > at all.
> True. Noted and reflected in the new version. What's the Haskell name for
> () again? I fear explaining the exact type information of IO () may be too
> much for a brief introduction to Haskell to cover.

() is called unit.


> > You've got an unusual indentation scheme. Consider adopting a more standard
> > one for your tutorial.
> I'm in the camp of hard tabs rather than soft tabs, and that preference is
> probably responsible for much of the difference in indentation scheme.
> Unfortunately, HTML is terrible at representing hard tabs in <PRE> code
> with a custom width preference; they all come out looking like some idiot
> pressed space bar eight times. I could use JavaScript to remedy this, but
> for now, I like to directly copy and paste my working code from .HS files
> into <PRE> tags just in case.
> 
> If tabs are *not* the issue, then maybe I'm not indenting far enough to the
> right for some tastes? Or maybe it's my tendency to put "where" on its own
> line, something a Perl obfuscater would detest. I dunno. If someone would
> suggest a more idiomatic indentation scheme for my code so that I know
> exactly what is different, I can take a look.

Unless the lines get too long, you'd usually see something like:
     do args <- getArgs
        fcontents <- readFile (head args)
        ...
        putStrLn results


By the way, your fib.hs (extended) is still in poor form, showing up to
fib 30 hardwired. Generally you would just hardwire your first one or two
values to "seed" your computation, like the first two Fibonacci numbers,
or first prime, etc., and then any memoization is accomplished as
described above, using some array or other structure to hold previously
computed values.


> Incidentally, when will Nat be available in Haskell?

Don't know, sorry.


> The Fibonacci
> algorithm is designed to work only over natural numbers, and the best way
> to express this in the type system is with Nat. But this type doesn't seem
> available out-of-the-box for Haskell users.

It's not unusual for a function to be partially defined this way. You
could equally well express the Fibonacci (or any) sequence as an
infinite list. You can only use non-negative values for your list
lookup, so if you view this as a deficiency, then the ubiquitous list
shares the same deficiency.


> Noted and reflected... I'm trying to convey to an audience largely composed
> of Java and C++ fanatics how Haskell records are much better than OOP, how
> GADTs are more intuitive, robust, ... OOP doesn't even compare! That's what
> I'm trying to get across in that bit. And it's hard to do this in just a
> few sentences, especially when the reader isn't even familiar with GADTs in
> the first place.

I meant to also mention in my previous email, your section on Records
doesn't actually deal with what the Haskell community considers
records (e.g., algebraic datatype with labelled fields.) You're just
using a simple algebraic datatype, so it'd be better not to call it a
record, as that's bound to lead to confusion.


> Now, besides the code and the description of the code, I know we're not
> English majors, but what do you think of the overall tone, pacing, etc.? Is
> it entertaining? Is it humorous? Is it boring? Is it offensive? Is it too
> brief or too laborious?

Very subjective, but the "evil genius" thing doesn't work for me. I like
the "launch missiles" analogy when discussing side-effects, but I don't
care for it as the entire basis to wind a tutorial around. It is
humorous, not boring. I find the pacing OK, but it's hard for me to put
myself into the mindset of somebody encountering the material for the
first time. Putting an appropriate quote under headings is a nice
touch.

Alex