[<<][compsci][>>][..]Mon Aug 15 10:38:39 CEST 2011

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 strings". - 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

[Reply][About]

[<<][compsci][>>][..]