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[1].  This can be useful for hiding type parameter
  when making class instances[6].

- Phantom types [2].  Used for typed language embedding and encoding
  data structure invariants in the type system.  I.e. "blessed

- Parametric polymorphism [3].  A basic tool for building generic
  functions that operate on data (Algebraic data types) with type
  parameters, i.e. list.

- Ad-hoc polymorphism [4] 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)[9].

- 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[7][10].

- 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[8].

[1] http://www.haskell.org/haskellwiki/Existential_type
[2] http://www.haskell.org/haskellwiki/Phantom_type
[3] http://www.haskell.org/haskellwiki/Parametric_polymorphism
[4] http://www.haskell.org/haskellwiki/Ad-hoc_polymorphism
[5] http://www.haskell.org/haskellwiki/Algebraic_data_type
[6] entry://20110814-212921
[7] http://en.wikipedia.org/wiki/Identity_(object-oriented_programming)
[8] http://www.cs.rutgers.edu/~ccshan/tagless/aplas.pdf
[9] entry://20110723-141330
[10] entry://20110710-144829