Sunday, December 5, 2010

The Type of []

That should be "The Type of []", but it seems that blogger won't let you change the font on the heading. 

Anyway, so the section of Learn You A Haskell where it introduces value constructors says this: "Value constructors are actually functions that ultimately return a value of a data type."  (For example, Just is function that takes an argument of type a and returns a value of type Maybe a).  That seemed pretty straightforward and I think I internalized it well on the first pass.  

The LYAH section on type constructors also mentions the fact that type constructors are functions.  So I kind of knew that fact but didn't really know it until I got unto the Functor section and the explanation that fmap is just a generalization of map.   Because the type of fmap is (Functor f) => (a->b) -> f a -> f b.  My brain began to rewind a bit, trying to figure out how [Int] fit the type signature f a with a bound to Int.  Then it hit me that [] is just syntactic sugar for a type constructor, which is just a function that creates a type. I'm just so used to that class of objects being builtin language keywords that this took more than a bit of adjustment.

In other languages, list<int> myList is just a set of keywords you say to make the compiler give you a list of integers; a compiler feature or even a compiler-level function if you will.  Haskell gives you the list type constructor as an actual function.  EDIT: The function is evaluated at compile time, but it is nonetheless a function. 


  1. > Haskell gives you the list type constructor as an actual runtime function

    An actual compile-time function, you cannot use [] as a runtime function. [] can indeed be seen as a compile-time type-level function from types (e.g: a) to types (e.g: list of a). This is why types and type constructors also have "kinds". A simple type like "Int" has-kind "*". We write it like we do with values: Int :: *. And a type constructor like "[]" (not to be confused with the empty list which is also denoted "[]") has kind: * -> * (that is, a compile-time function from a simple type to a simple type).

  2. Good catch. Of course, it has to be a compile-time function, because the type checking is all done at compile time! It will take me a bit to really think of functional programming without some of the Lisp baggage.