Alex Rivera | Logout

Lambda for type expressions in Haskell?

Asked 2010-11-01T14:37:49.330
30

Does Haskell, or a specific compiler, have anything like type-level lambdas (if that's even a term)?

To elaborate, say I have a parametrized type Foo a b and want Foo _ b to be an instance of, say, Functor. Is there any mechanism that would let me do something akin to

instance Functor (\a -> Foo a b) where
...

?

Edit
Report

2 Answers

27

While sclv answered your direct question, I'll add as an aside that there's more than one possible meaning for "type-level lambda". Haskell has a variety of type operators but none really behave as proper lambdas:

  • Type constructors: Abstract type operators that introduce new types. Given a type A and a type constructor F, the function application F A is also a type but carries no further (type level) information than "this is F applied to A".
  • Polymorphic types: A type like a -> b -> a implicitly means forall a b. a -> b -> a. The forall binds the type variables within its scope, thus behaving somewhat like a lambda. If memory serves me this is roughly the "capital lambda" in System F.
  • Type synonyms: A limited form of type operators that must be fully applied, and can produce only base types and type constructors.
  • Type classes: Essentially functions from types/type constructors to values, with the ability to inspect the type argument (i.e., by pattern matching on type constructors in roughly the same way that regular functions pattern match on data constructors) and serving to define a membership predicate on types. These behave more like a regular function in some ways, but are very limited: type classes aren't first-class entities that can be manipulated, and they operate on types only as input (not output) and values only as output (definitely not input).
  • Functional dependencies: Along with some other extensions, these allow type classes to implicitly produce types as results as well, which can then be used as the parameters to other type classes. Still very limited, e.g. by being unable to take other type classes as arguments.
  • Type families: An alternate approach to what function
answered 2010-11-01T17:33:40.313
6

EHC (and perhaps also its successor, UHC) has type-level lambdas, but they are undocumented and not as powerful as in a dependently-typed language. I recommend you use a dependently-typed language such as Agda (similar to Haskell) or Coq (different, but still pure functional at its core, and can be interpreted and compiled either lazily or strictly!) But I'm biased towards such languages, and this is probably 100x overkill for what you are asking for here!

answered 2010-11-03T11:27:19.590

Your Answer