gmane.comp.lang.haskell.glasgow.user

possible OI extension

Hello, people,

This is about possible extension in treating of  overlapping instances.
Here is a simple example.

------------------------------------------
import qualified Data.Set as Set (empty, member, insert)
import List (nub)

class Nub a where myNub :: a -> a

instance Eq a => Nub [a] where  myNub = nub

instance Ord a => Nub [a] 
  where  
  myNub xs = nub' Set.empty xs
             where
             nub' _   []      = []
             nub' set (x: xs) = if  Set.member x set  then  nub' set xs
                                else     x: (nub' (Set.insert x set) xs)
------------------------------------------

The idea is that it is good to replace  nub  of the Haskell-98 library
with  myNub. 
Because:
for  Eq a,   myNub  costs  O(n^2),
for  Ord a,  myNub  costs  O(n*(log n)),
and it is good to denote this operation with the same name.

Compiling this by GHC under

(Continue reading)

headers

Simon Peyton-Jones | 27 Jun 16:01

RE: possible OI extension

Yes, the idea of some kind of backtracking solution of class constraints (multiple instance
declarations, choose the one whose context is indeed soluble) has often been suggested, and is quite
attractive.  But it raises a bunch of new complications.  And your proposal does so even more, because it
involves a notion of when one context is "stronger" than another.  (What exactly does "stronger" mean.)

Just for example, what's the inferred type of
        f x  = nub (nub [x])
It could be
        f :: Eq a => a -> [a]
or      f :: Ord a => a -> [a]

So far as the implementation is concerned, "improvement" currently happens by in-place unification,
which is hard to undo when you need backtracking, so there's a practical problem there.  That'll be
ameliorated as we move towards type functions.

So I can see the attraction, but I doubt I'll implement it anytime soon.

Simon

| -----Original Message-----
| From: glasgow-haskell-users-bounces <at> haskell.org [mailto:glasgow-haskell-
| users-bounces <at> haskell.org] On Behalf Of Serge D. Mechveliani
| Sent: 27 June 2008 11:56
| To: glasgow-haskell-users <at> haskell.org
| Subject: possible OI extension
|
| Hello, people,
|
| This is about possible extension in treating of  overlapping instances.
| Here is a simple example.

(Continue reading)