CODEWITHSUNDEEP
haskelllambda
gspr
gspr

Reputation: 11227

Lambda for type expressions in Haskell?

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

?

Upvotes: 30

Views: 7965

Answers (7)

Quelklef
Quelklef

Reputation: 2147

Depending on the situation, you could replace your original type definition with a "flipped" version, and then make a type synonym for the "correct" version.

From

data X a b = Y a b

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

to

data XFlip b a = Y a b  -- Use me for instance decalarations
type X a b = XFlip b a  -- Use me for everything else

instance Functor XFlip where ...

Upvotes: 1

Robin Green
Robin Green

Reputation: 33033

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!

Upvotes: 6

C. A. McCann
C. A. McCann

Reputation: 77374

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 functional dependencies do; they allow functions on types to be defined in a manner that looks much closer to regular value-level functions. The usual restrictions still apply, however.

Other extensions relax some of the restrictions mentioned, or provide partial workarounds (see also: Oleg's type hackery). However, pretty much the one thing you can't do anywhere in any way is exactly what you were asking about, namely introduce new a binding scope with an anonymous function abstraction.

Upvotes: 27

none
none

Reputation: 19

Yeah, what Gabe said, which is somewhat answered by type families:

http://www.haskell.org/haskellwiki/GHC/Type_families

Upvotes: 1

gspr
gspr

Reputation: 11227

I don't like the idea of answering my own question, but apparently, according to several people on #haskell on Freenode, Haskell doesn't have type-level lambdas.

Upvotes: 7

sclv
sclv

Reputation: 38893

From TypeCompose:

newtype Flip (~>) b a = Flip { unFlip :: a ~> b }

http://hackage.haskell.org/packages/archive/TypeCompose/0.6.3/doc/html/Control-Compose.html#t:Flip

Also, if something is a Functor in two arguments, you can make it a bifunctor:

http://hackage.haskell.org/packages/archive/category-extras/0.44.4/doc/html/Control-Bifunctor.html

(or, in a later category-extras, a more general version: http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor.html#t:Bifunctor)

Upvotes: 20

Chris Smith
Chris Smith

Reputation: 5454

The closest I know of to get a type lambda is by defining a type synonym. In your example,

data Foo a b = Foo a b

type FooR a b = Foo b a

instance Functor (FooR Int) where
...

But even with -XTypeSynonymInstances -XFlexibleInstances this doesn't work; GHC expects the type syn to be fully applied in the instance head. There may be some way to arrange it with type families.

Upvotes: 2

Related Questions