[Haskell] generalized newtype deriving breaks type class invariants. that is bad.

[John Meacham]

On Mon, Mar 08, 2010 at 11:32:16PM +0100, Wolfgang Jeltsch wrote:
> Generalized newtype deriving doesn’t just allow otherwise undefinable functions
> to be defined. It probably also allows for faster function implementations. For
> example, with the above conv method, you could probably convert a list of some
> type [t] into a list of type [Wrapped t] in O(1) time. If you would code this
> conversion by hand, it would take O(n) time, of course.

So you can!

wrapList :: [a] -> [Wrapped a]
wrapList xs = conv xs

> wrapList "Hello"
[Wrap 'H',Wrap 'e',Wrap 'l',Wrap 'l',Wrap 'o']

This is quite interesting. And perhaps very, very  bad.

Take this example:

> newtype Down a = Down a deriving (Iso a, Show, Eq) 
>
> instance Ord a => Ord (Down a) where 
>     compare (Down x) (Down y) = compare y x

> downSet :: Set.Set a -> Set.Set (Down a)
> downSet ss = conv ss

> xs = "abcdef"


> sxs1 = downSet (Set.fromList xs)
> sxs2 = Set.fromList (map Down xs)

Set.toAscList sxs1
 [Down 'a',Down 'b',Down 'c',Down 'd',Down 'e',Down 'f']
Set.toAscList sxs2
 [Down 'f',Down 'e',Down 'd',Down 'c',Down 'b',Down 'a']

We have been able to break the invarients of 'Set' using newtype
deriving of a completely unrelated class 'Iso'.

It seems that generalized newtype deriving may break type classes in a
big way.

        John


-- 
John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/