[Haskell-cafe] Re: Composing functions with runST

[apfelmus at quantentunnel.de]

Neil Mitchell wrote:
> As for beginner issues with rank-2 types, I've been learning Haskell
> for years now, and have never felt the need for a rank-2 type. If the
> interface for some feature requires rank-2 types I'd call that an
> abstraction leak in most cases. It certainly means that you can't
> properly Hoogle for it, can't compile it with Yhc, can't do full type
> inference etc.

I think that the term "abstraction leak" is too harsh. In some sense,
you may as well call "strong typing" an "abstraction leak" because one
can do the stuff as well in a dynamic typed language and adding strong
typing means that you can't compile it with current compilers, you need
to implement type checking/inference etc. Of course, this analogy has
flaws as higher rank types go to the edge of computability whereas
strong typing can be implemented.

Concerning interfaces, higher rank types offer crucial static checking
that cannot be achieved without them. The prominent example is ST. The
next example is the parsing library "frisby". In both cases, it would be
easy to wrack havoc in case the interface would not use higher rank
types. The same analogy as above applies: one uses strong typing because
one does not want to wreak havoc. I would not call this an "abstraction
leak".

Concerning implementation, higher rank types are even more widespread:
almost everything involving continuations needs them: ReadP, Exceptions
(as opposed to Either), deforestation etc. In fact, it is quite possible
to throw away algebraic data types altogether and build everything you
need with higher rank types. A prominent example is

   [a] ~= (forall b . (a -> b -> b) -> b -> b)
       ~= (forall b . (Maybe (a,b) -> b) -> b)

The denotational semantics do not change, but the time and space
behavior is much different.

Perhaps the above remarks misinterpret your statement and you meant
"abstraction leak" in the sense that, because higher rank types are
available, the interface author used them without thinking whether the
same effect can be achieved in ordinary Haskell. Alas, such problems are
not tied to higher rank types: proper interface design is an art and
does not come for free, not to mention interface documentation[1]. One
could easily berserk: why does this library use String and doesn't
abstract it with a type class? Why does that interface only provide IO,
why isn't this available as a library of pure functions? What do these
obviously crappy semantics mean? In this case, higher rank types are a
symptom, not the problem. If one wants to cure the problem by
disallowing the symptom, then I suggest to also erase the symptom IO.
Thoroughly.

Of course, the drawbacks of higher rank types you mentioned remain. In
the case of "hoogleability", I'm confident that it is possible to
implement them, it's only that someone has to think hard about it.
Implementing higher rank types in YHC is even harder but not impossible.
Sure, type inference is the most difficult thing, and one has to accept
glitches and drawbacks to make it work. Compared to these difficulties,
I think that the remark

> So I can't just tell someone who's just starting to learn Haskell that
> "f $ g y" is equivalent to "f (g y)"; I have to say "those two are
> *almost always* equivalent, but if you use $ and the compiler complains
> about not being able to match the expected and the inferred type and a
> type signature in the error message has the word 'forall', try rewriting
> that expression without the $ and see if it compiles".  Eeeww.

posted in this tread is too harsh. That's life, every language has its
flaws and glitches: parts of the layout rule, pattern guards, I want a
better records system, views, generic programming, etc. But, when code
has to be finished, those glitches or annoying things are best countered
with a shrug: they are not life-threatening. A programming language with
nonexistent type system and ugly semantics is. And much to our joy,
Haskell is far from this.

In that sense, dear reader of this post, just rewrite that expression
without $ and see if it compiles. The complier authors don't want to
annoy you, it's just that the exact reasons why this cannot yet be put
to work are damn hard. You are encouraged to learn about System F to get
a grasp of what is going on, but spending this one $ will be much cheaper.


Regards,
apfelmus

[1] Concerning library documentation, I think that literate Haskell
sources have the drawback that they are either tied to TeX
(\begin{code}..\end{code}) or that every line has to start with a '>'.
I'd suggest to add a <code>..</code> or something else. The point is
that while (La)TeX can be cranked up to a publishing system, it is not
suited for many tasks such as media-dependent processing. TeX is a macro
language, not a structured document type. And for the strongly typed
Haskell programmer used to referential transparency, macros are a nightmare.