Are there "type-level combinators"? Will they exist in some future?

17
votes

Much of what makes haskell really nice to use in my opinion are combinators such as (.), flip, $ <*> and etc. It feels almost like I can create new syntax when I need to.

Some time ago I was doing something where it would be tremendously convenient if I could "flip" a type constructor. Suppose I have some type constructor:

m  :: * -> * -> *

and that I have a class MyClass that needs a type with a type constructor with kind * -> *. Naturally I would choose to code the type in such a way that I can do:

instance MyClass (m a)

But suppose I can't change that code, and suppose that what really fits into MyClass is something like 

type w b = m b a 

instance MyClass w where 
    ...

and then I'd have to activate XTypeSynonymInstances. Is there some way to create a "type level combinator" Flip such that I can just do:

instance MyClass (Flip m a)  where 
   ...

?? Or other type level generalisations of common operators we use in haskell? Is this even useful or am I just rambling?

Edit:

I could do something like:

newtype Flip m a b = Flip (m b a)

newtype Dot m w a  = Dot m (w a)

...

But then I'd have to use the data constructors Flip, Dot, ... around for pattern matching and etc. Is it worth it?

3
haskelltypescombinatorstype-level-computation
You may want to see hackage.haskell.org/cgi-bin/hackage-scripts/package/TypeCompose as well. - Alexey Romanov
"will they exist in the future?" Well GHC is open source...go for it. :) That or you can throw large sums of money at PhD programs and tell them to do it for you. - Dan Burton
@DanBurton haha, you're right. I should have phrased it as: "are there any current projects aiming to include something like this in GHC?". - Rafael S. Calsaverini
I asked a similar question: stackoverflow.com/questions/8005372/… . Some of the responses may also help you. - David Miani

3 Answers

11
votes

Your question makes sense, but the answer is: no, it's not currently possible.

The problem is that (in GHC Haskell's type system) you can't have lambdas at the type level. For anything you might try that looks like it could emulate or achieve the effect of a type level lambda, you will discover that it doesn't work. (I know, because I did.)

What you can do is declare your Flip newtypes, and then write instances of the classes you want for them, painfully with the wrapping and the unwrapping (by the way: use record syntax), and then clients of the classes can use the newtypes in type signatures and not have to worry about the details.

I'm not a type theorist and I don't know the details of why exactly we can't have type level lambdas. I think it was something to do with type inference becoming impossible, but again, I don't really know.

3
votes

You can do the following, but I don't think its actually very useful, since you still can't really partially apply it:

{-# LANGUAGE TypeFamilies, FlexibleInstances #-}
module Main where

class TFlip a where
    type FlipT a

instance TFlip (f a b) where
    type FlipT (f a b) = f b a 

-- *Main> :t (undefined :: FlipT (Either String Int))
-- (undefined :: FlipT (Either String Int)) :: Either Int [Char]

Also see this previous discussion: Lambda for type expressions in Haskell?

2
votes

I'm writing answer here just for clarifying things and to tell about achievements in the last years. There're a lot of features in Haskell and now you can write some operators in type. Using $ you can write something like this:

foo :: Int -> Either String $ Maybe $ Maybe Int

to avoid parenthesis instead of good old

foo :: Int -> Either String (Maybe (Maybe Int))