Mon Aug 15 10:38:39 CEST 2011
The Haskell Learning Curve
Haskell is a tremendous trip. As I keep telling my fellow C trench
dwellers, it's really different. Even with a couple of years of
Scheme (Racket) to get used to higher order functions, it's still a
different world. The reason of course is types. Here's a list of
things I've learned.
- Existential types. This can be useful for hiding type parameter
when making class instances.
- Phantom types . Used for typed language embedding and encoding
data structure invariants in the type system. I.e. "blessed
- Parametric polymorphism . A basic tool for building generic
functions that operate on data (Algebraic data types) with type
parameters, i.e. list.
- Ad-hoc polymorphism  or overloading, implemented by type classes
which abstract over collections of parameterized types. What is
interesting is the "1-up" that is possible by moving from a set of
operations over a parametric data types, to a set of operation over
a collection of different data types (class instances).
- Common abstractions implemented as classes: Monad, Applicative,
Functor, Eq, Show, Num, ...
- Thinking of monads as computations instead of containers. An early
misconception of mine instilled by one of the many monad tutorials
is that parameteric types need to be data containers. It is quite
possible for a type parameter of a parametric type to refer to the
input and/or output type of a function. Obvious in retrospect, but
a big revelation when I finally got it.
This is used in the Cont (CPS) & State monads. The monad operations
simply chain computations together. The end result is a function
requiring a value (the initial state in State) or a higher order
function requiring a function argument (the final continuation
function in CPS).
- Seeing Monad as a DSL with a custom variable binding structure, the
">>=" operator, which is reflected in the do notation's left arrow.
- Finding out that Haskell has no meaningful object identity. Object
identitiy is not referentially transparent.
- Related to the above, finding out that sharing structure (let) is
not observable from the outside of a function definition. This is
important in abstract interpretation when the intention is to
recover sharing structure. Embedding a DSL where sharing structure
is important (i.e. static single assignment SSA) then needs a
specific binding form. This can be done by ">>=" in a Monad, or by
embedding the language in a type class representing HOAS.