Re: [scala] Re: higher-kinded types

On Wed, Jul 1, 2009 at 12:25 AM, Meredith Gregory <lgreg.meredith@...> wrote:

In English, in a monad C over A we don't want to encounter some other type besides A's. 

Sorry, this does not make sense to me.

Take a look at the Haskell definitions (straight from http://www.haskell.org/all_about_monads/html/class.html#monad)

class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a

instance Monad [] where m >>= f = concatMap f m return x = [x] fail s = []

Surely a list of any type of elements is a Monad!

We see the problem when we insist that A's have some property, like being at least Option'ed.

Your example does not type check because it imposes a bound on the higher-order type parameter of the Monad's type constructor that is stricter than what was originally declared. Our paper on type constructor polymorphism explains how to do this is Scala. By the way, this is impossible in Haskell. You'd need something like abstraction over type class contexts. In pseudo-code:

class Monad C m where -- C is an abstract type class context 

    (>>=)  :: C a => m a -> (a -> m b) -> m b

return :: C a => a -> m a

instance Monad Ord Set where ... -- because Ord a => Set a

Our paper explains how this can already be done in Scala by using an abstract type as a subtype bound.

hth

adriaan