Proposal: RankedInstances

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

Proposal: RankedInstances

The main power of Haskell is on instances.
But Haskell instances system work fine with lower number of instances (rare instances).
But we want hight density of instances!
If we wish to have more selective instances we use `OverlappingInstances` (which are desined in a poor way)  and if we still have too many instances we use `IncoherentInstances`.

~~`RankedInstances` extension ~~

I suggest simple `RankedInstances` extension.
We use it (!)before OverlappingInstances (it must include `RankedInstances`), and in many cases instead of.

This extension is easy to implement and it give us a lot of new possibilities and instruments.

Now the system of instances is flat, and compiler takes all of them and check if only 1 match. If it is not(less or more than) - compiler trow an error.

I suggest to add rankings, so compiler
* compiler set N=0
* took all N-ranked instances and
 ** try to find only one match instance.
 *** If it found 1 - this is RESULT: needed instance,
 *** If it found many instances - still throw an error
 ******* (then we use `OverlappingInstances` to resolve this)
 *** If compiler found NO instances, compiler set N=N+1 and repeat
* If N=MaxRank and still no matches compiler throw an error

~~How to add a rank~~
I suggest next grammar:

  {-# LANGUAGE RankedInstances #-}

  instance rank 1. C a => D a where ...

  instance           C2 a => E a where ...  
  instance rank 0. C2 a => E a where ...

So, all written instances(without ranking) are 0-ranked instances.

Backward compatibility => without -XRankedInstances all instances with rank n, where n >0 - are not exported

  instance rank 1. C Int a     where ...   -- (A)
  instance           C a   Bool  where ...   -- (B) rank 0
  instance rank 1. C Int a     where ...   -- (A)
  instance rank 1. C a   Bool  where ...   -- (B)  
  instance           C Int Bool  where ...   -- (C) rank 0
  instance rank 1. C Int [a]  where ...  -- (C)
  instance         C Int [Int]  where ...  -- (D)

As we see, all instances are unambiguous!

~~ Rank Scale~~

It is for discussion, I see this like:
0           - default
1 ..9      - user free (without fear to overlap with devs instances)
10 .. 14  - Generic
15 ..      - superclass' instances

~~ Higher Rank instances~~
We don't need to use `default` inside of class:

  instance rank 10. (Generic a, GToJSON (Rep a)) => ToJSON a where
    toJSON = genericToJSON defaultOptions

We could add superclass' instances now, something like these:

  instance rank 15. Monad m => Applicative m where
    pure  = return
    (<*>) = ap
  instance rank 16. Monad m => Functor m where
    fmap = liftM  
  instance rank 17. Applicative m => Functor m where
    fmap f x = pure f <*> x

~~Inherit mechanism~~

What do if we want to use any proposed instance, not in the rank order ?
For example we have data, which is Monad and Applicative, but not a Functor.
We'll use automatically "instance rank 16. Monad m => Functor m", but not "instance rank 17. Applicative m => Functor m" .
But we wish to use the last one. We need to create a new instance and inherit the behavior of needed instance

  data D a ....

  instance Monad D where ...
  instance Applicative D where ...

  instance rank 1. Functor D inherit (D ~ m)
        instance Applicative m => Functor m

  foo = ... fmap

So, in this case we'll use `fmap` as Applicative Functor.

Inherit mechanism defaulting :

   instance  C a => D a where ...
   instance  C a => D a inherit (a ~ b) class D b where

~~ "As" pattern in RankedInstances~~

Now we add "as" pattern and rewrite both of our instances:

  instance rank 17. Applicative m => ApFunctor@Functor m where
    fmap f x = pure f <*> x
  instance ApFunctor D         --by the way 0-ranked

Wow!!! It is simple, safe and looks nicer!

~~Partly Applied Instances~~

We describe a situation when we write a child class and want automatically get access to parent's classes.
But sometimes we need to use already defined parent classes to describe children classes

We CANNOT do next:

  instance rank 20. (Functor m, Applicative m) => Monad m where
    ma >> mb = (fmap (const id) ma) `apply` mb

  instance rank 21. Applicative m => Monad m where
    ma >> mb = (pure (const id) <*> ma) `apply` mb

Because if we define

  data D a ...

  instance Functor D ...
  instance Applicative D ...

  D a >>= D b  -- this will compiler, but we have no full applied MonadInstance

How to resolve this?

I suggest to add one reserved world "newclass" (as an analog of newtype)

--instance (Functor m, Applicative m) => FAMonad@Monad m where
newclass (Functor m, Applicative m) => FAMonad@Monad m where
    ma >> mb = (fmap (const id) ma) `apply` mb

--instance Applicative m => AMonad@Monad m where
newclass (Applicative m) => AMonad@Monad m where
    ma >> mb = (pure (const id) <*> ma) `apply` mb

The "newclass" is just an instance, but guarded - compiler did count it when it try to match
So, now next throw an error: D a >>= D b

And we have an ability to write more precisely

  instance AMonad H where

  instance FAMonad K where

~~~BIG Example~~~~

Let try to divide "class (Eq a)=>Ord a" to both:

  class  (Eq a) => Ord a  where
    compare              :: a -> a -> Ordering

    compare x y = if x == y then EQ
                  else if x <= y then LT
                  else GT

Proposed one (it is just an example, not a "real" proposal):

class  Ord' a  where
    compare x y = if x < y then LT
                  else if x > y then GT
                  else EQ             -- without Eq it is a last choice

newclass  (Eq a) => Ord@Ord' a  where
    compare x y = if x == y then EQ
                  else if x <= y then LT
                  else GT

So now we have both Ord' a for nonEQ data and for Eq data.
And this has a backward compatibility!