[Haskell-cafe] I hate Haskell's typeclasses

[Jonathan Cast]

On 21 Apr 2008, at 12:50 AM, Ryan Ingram wrote:
> On Fri, Apr 18, 2008 at 10:01 PM, Jonathan Cast
> <jonathanccast at fastmail.fm> wrote:
>>  {-# GHC_OPTIONS -foverlapping-instances -fundecidable-instances  
>> #-} :)
>>  What you want to work is precisely what this allows.
>
> Of course, I bring that point up.  And overlapping instances has the
> problem that it doesn't really do what you want; you always eventually
> end up with this problem:
>
> oops :: Eq a => a -> a -> Property
> oops x y = x ~= y
>
>     Overlapping instances for EqTestable a
>       arising from a use of `~='
>     Matching instances:
>       instance [overlap ok] (Eq a) => EqTestable a
>       instance [overlap ok] (Show a, Arbitrary a, EqTestable b) =>
>                             EqTestable (a -> b)
>     (The choice depends on the instantiation of `a'
>      To pick the first instance above, use -fallow-incoherent- 
> instances
>      when compiling the other instance declarations)
>     In the expression: x ~= y
>     In the definition of `oops': oops x y = x ~= y

OK, right.  But I think what this shows is that sometimes you need to  
name and manipulate instances (instances are designed to be anonymous  
and transparent, which made sense when the alternative was thought to  
be the anonymous and transparent overloading of traditional  
languages, but has started to slip as time goes on).  I think the  
traditional solution here is newtype; I think that using type  
signatures to try to choose an instance, in cases like this, is an  
abuse of the original insight behind type classes.

>>  I call.  Name a language that is
>>
>>  a) Completely statically typed (no type errors at runtime),
>>  b) Has an ad-hoc overloading mechanism powerful enough to encode  
>> Num and
>> Monad, and
>>  c) Is substantially better than Haskell + extensions for your  
>> examples.
>
> No fair!  I'm on haskell-cafe for a reason: every language sucks,
> Haskell just sucks less :)

Amen to that.

> But I can give a couple of thoughts that almost meet your criteria:
> 1) Ruby.  Totally misses (a) but absolutely nails (b) and (c).

I must have failed to communicate well.  To me, the point of giving a  
class a name is that then you can write a program that is parametric  
over the elements of that class.  Knowing that I can implement monads  
in Ruby doesn't impress me nearly as much as knowing that I can  
implement mapM does.  Haskell has me addicted to code reuse (mapM)  
the way the rest of the programming world is addicted to design  
patterns (monads).  What I mean by `encoding Num and Monad' is that  
you can do something like this:

sum = foldr (+) 0
sequence = foldr (liftM2 (:)) (return [])

I don't know of any language that is dynamically typed and also can  
encode `return' or `0' in a way that lets those examples work.   
Statically typed languages where it works are rare, even.  Haskell  
gives up a fair amount of control by making these things implicit,  
which is what I think you're running up against --- but I think it  
gets something useful and non-trivial to acheive in return.

> 2) C++: Fine on (a) as long as you don't write stupid stuff.

C++ would be a decent successor to C if it had HM typing and GC and  
dropped the whole silly OO business.  Sum in C++ (I forget how to do  
higher-order templates):

template<type T, type Iter, type Fun>
foldr(Fun f, T z, Iter begin, Iter end)
{
     if (begin < end) {
         return f(*begin, foldr(f, z, begin + 1, end));
     } else {
         return z;
     }
}

template<type T>
struct plus
{
     plus() { }
     operator()(T t0, T t1) { return t0 + t1; }
};

template<type T, type Iter>
sum(Iter begin, Iter end)
{
     return foldr(plus(), T::zero, begin, end);
}

Not bad for a language as determined to join the 1980s as C++.

> Template meta-programming involves pattern-matching on types and I  
> believe is
> strong enough for (b).  But it's really verbose; from an elegance
> point of view it probably misses (c).

> 3) Scala?  I don't know enough about it to say for sure but what I
> have seen looks promising.

Scala indeed looks promising.  I was secretly hoping you'd know  
something I didn't.  But I'm still not sure it knows how to encode mapM.

>> On 18 Apr 2008, at 9:29 PM, Ryan Ingram wrote:
>>> 1) You can't make sensible default implementations.  For example,  
>>> it'd
>>> be nice to make all my Monads be Applicatives and Functors without
>>> resorting to Template Haskell or infinite boilerplate.  Why can't I
>>> just write this?
>>>
>>> instance Monad m => Applicative m where
>>>    pure = return
>>>    (<*>) = ap
>>>
>>> Sure, I get that there might be ambiguity of which instance to  
>>> choose.
>>>  But why not warn me about that ambiguity, or let me choose  
>>> somehow on
>>> a case-by-case basis when it happens?
>>>
>>
>>  You can already choose on a case-by-case basis.
>
> That's true, but if the authors of Applicative could, I am sure they
> would have chosen to make it (and Functor) a superclass of Monad with
> the proper default implementation; after all (1) Applicative is damn
> useful, and (2) it's the common case.

Sure.  And sometimes they'd get complaints (or engender flamewars)  
when the default instance wasn't what someone wanted.

>>  More generally, specifying what you want is really not hard.  Do  
>> you really
>> have gazillions of monads in your code you have to repeat this
>> implementation for?
>
> Yes, actually.  First, I like writing monads.  See
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 
> MonadPrompt-1.0.0.1
>
> And second, just today I had to write
> instance Applicative STM where
>     pure = return
>     (<*>) = ap
>
> It felt like it was driving home the point.

I'll agree with this point.  I've complained, concretely, about the  
lack of instances for (some) standard types before.  (STM is actually  
a rather bad offender here; it's lacking MonadPlus, as well, despite  
the specific observation in the paper that it has the right signature  
for that class.)

>>> 2) You can't add sensible superclasses.  I was playing with  
>>> QuickCheck
>>> and wanted to write "equal with regards to testing".  So I wrote  
>>> up a
>>> class for it:
>>>
>>> class TestableEq a where
>>>    (~=) :: a -> a -> Property
>>>
>>> instance Eq a => TestableEq a where
>>>    -- should be a superclass of Eq instead!
>>>    a ~= b = a == b
>>>
>>
>>  Again, this is one (*) line per type.  How many types do you  
>> declare?
>
> I don't declare too many myself, except on days when I'm trying to
> embed system F in Haskell via GADTs, but I use a lot of them; and many
> of them the authors have conveniently already made instances of useful
> typeclasses.  Then I try to add some new functionality and run into a
> lot of friction because now every library I use needs an
> implementation which matches.
>
> Have you ever tried to write a monad transformer that is compatible
> with the MTL?  O(n^2) instances is not a fun place to be, especially
> when most of the definitions are just variations on "lift".

Not yet.  For which I am grateful.  But I think this is more a  
problem with monad transformers than with type classes; monad  
transformers just do not seem to have solid mathematical underpinnings.

> Disclaimer: this is actually a hard problem; I don't expect the
> compiler to be able to solve it, but it's frustrating nonetheless.
> The things I bring up here are easy in comparison.
>
>>> Sure, there is an alternative: I could manually declare instances of
>>> TestableEq for EVERY SINGLE TYPE that is an instance of Eq.  I am  
>>> sure
>>> nobody here would actually suggest that I do so.
>
>>  Bzzzt.  Wrong.  Thanks for playing!
>
> Ha ha, you got me there :)
>
>>> But why do I need to jump through these hoops for a perfectly safe &
>>> commonly desired operation?
>>
>>  It's called a proof obligation.
>
> My argument is that there shouldn't even be a proof obligation here;
> the language is just not expressive enough to allow me to write the
> code that I want; something that is actually completely decidable &
> non-overlapping.

Just remember that `choose this instance if there's no other instance  
available' means `no other instance on the planet' everywhere but Main.

>>> 3) There's no reflection or ability to choose an implementation  
>>> based
>>> on other constraints.
>>>
>>> In QuickCheck, (a -> b) is an instance of Arbitrary for  
>>> appropriate a,
>>> b.  But you can't use this instance in forAll or for testing  
>>> functions
>>> without being an instance of Show.  Now, this is probably a design
>>> mistake, but it's the right choice with the current typeclass system
>>> (see (2)).  But it'd be a million times better to have something  
>>> like
>>> the following:
>>>
>>> class Arbitrary a => MkArbitrary a where
>>>   mkArbitrary :: Gen (a, String)
>>>
>>> case instance MkArbitrary a where
>>>   Show a =>
>>>       mkArbitrary = do
>>>           x <- arbitrary
>>>           return (x, show x)
>>>   otherwise =>
>>>       mkArbitrary = do
>>>           st <- getGenState
>>>           x <- arbitrary
>>>           return (x, "evalGen arbitrary " ++ show st)
>>>
>>
>>  So we compile in a table of every instance and every datatype, add a
>> Typeable constraint to forAll (since parametricity just got shot  
>> to heck),
>> and scan through that table on every test.  Millions of times  
>> better.  And
>> slower.
>
> It's had a lot of research; I want the best of all worlds.  For a  
> start:
> http://www.google.com/search?q=optimizing+dynamic+dispatch

I'll read through the results.  My complaint about parametricity  
stands, I think.

> You could get close without going to full dynamic dispatch, though;
> consider the following "core":
>
> -- This part is all in haskell now
> data ShowDict a = ShowDict { show :: a -> String }
>
> show_String :: ShowDict String
> show_Int :: ShowDict Int
> show_List :: ShowDict a -> ShowDict [a]
>
> -- foo :: Show a => [a] -> String
> -- foo x = show x ++ "!"
> foo :: ShowDict a -> [a] -> String
> foo sd x = show (show_List sd) x ++ "!"
>
> -- This part isn't in haskell, and the syntax sucks, but the idea  
> is there.
> type MaybeShow a = Maybe (ShowDict a)
>
> -- bar :: MaybeInstance Show a => [a] -> String
> -- bar xs
> --   | Show a = foo xs
> --   | otherwise = show (length xs)
> bar :: MaybeShow a -> [a] -> String
> bar (Just sd) xs = foo sd xs
> bar Nothing xs = show (show_Int) (length xs)
>
> With this I could write
>
> instance (MaybeInstance Show a, Arbitrary a) => MkArbitrary a where
>     mkArbitrary xs
>         | Show a = do
>               x <- arbitrary
>               return (x, show x)
>         | otherwise = do
>               st <- getGenState
>               x <- arbitrary
>               return (x, "evalGen arbitrary " ++ show st)
>
> Now, every concrete type would be an instance of MaybeInstance
> <classname>, and "dynamic" dispatch and (I think) closed typeclasses
> would be a free benefit.

When can we discharge a MaybeInstance context?

>> And more likely to develop odd changes and hard-to-debug errors.
>
> Or so you claim :)

Having the | Show a test suddenly trip from False to True because  
some other module imported Text.Show.Functions sounds like an odd  
change to me.  At any rate, it scares me enough to make me oppose the  
idea.

>>  QuickCheck makes testing so easy, I think the Arbitrary (a -> b)  
>> instance
>> is almost unnecessary; (btw., functions /are/ instances of Show).
>
> Now it's my turn to call:
>
> Prelude Test.QuickCheck> show ((\x -> x) :: Int -> Int)
> <interactive>:1:0:
>     No instance for (Show (Int -> Int))

Prelude Text.Show.Functions> show ((\x -> x) :: Int -> Int)
"<function>"

> Although, I do see a useless instance in the standard prelude at
> http://www.haskell.org/haskell-report/standard-prelude.html
>
> I actually would love to have (unsafeShow :: a -> String) which made a
> "best effort" attempt (subject to the compiler's debugging level) to
> evaluate an object and tell you what it contains, including source
> code for functions if possible.

I wonder how useful this would be in practice.

>> You can easily write a showable ADT encoding the functions you  
>> want to test.
>
> That's fair (and actually pretty interesting).  But definitely less  
> elegant than
>
> -- assuming Arbitrary (Behavior Int)
> prop_fmap_at :: (Int -> Int) -> Property
> prop_fmap_at f = fmap f . at ~= at . fmap f
>
> (see Conal's recent FRP paper for the formulation of this property)

Point.

>>> 4) Every concrete type should be an instance of Typeable without
>>> having to do anything,
>>
>> Sure.  And seq should go back to being a class method.  (See  
>> earlier about
>> parametricity being shot to heck).  I have an excellent design  
>> which will
>> preserve the language's semantics (which are fine the way they  
>> are, thank
>> you), while being convenient for programmers, which this margin is  
>> too small
>> to contain.[1]
>
> At least we agree on something.  But please don't keep your design to
> yourself, share!

class Forceable alpha where
   seq :: alpha -> beta -> beta

Instances derived automatically by the compiler, when possible, for  
every type (like Typeable should be).  We can omit functions if  
desired (I don't remember why I thought this was a good idea).  When  
you say

f :: alpha -> beta

or

f :: C alpha => alpha -> beta

The compiler adds implicit Forceable constraints on alpha and beta.   
But, if you say

f :: !Forceable alpha => alpha -> beta

The compiler leaves the Forceable alpha constraint off.  Then you can  
say

build :: (forall c. !Forceable c => (a -> c -> c) -> c -> c) -> [a]

And the foldr/build law is still sound.

>> Reflection is harder, because of the need for the lookup table  
>> with every
>> instance of every class I mentioned earlier.  (And you get to  
>> figure out how
>> to encode polymorphic instances, too!  Good luck[2]).
>
> See dynamic dispatch, above.  Although polymorphic instances do seem
> tricky.  But you could probably get away with treating each typeclass
> as a member of the "typerep" object for each type with some amount of
> lookup; doesn't one of the existing compilers implement typeclasses in
> this way already?

I can't speak to the specific issue of dynamic dispatch.  Most of the  
links I've looked at thus far seem to be about deciding when you  
actually /don't/ need dynamic dispatch.  Haskell has that down pat,  
now; I haven't seen anything about making the actual function call go  
faster yet.  Neither have I seen anything suggesting that the  
behavior of a function in one module cannot change because I added a  
multi-method in another module.  That's what I'm most worried about;  
it sounds too much like perl's spooky action at a distance 10x over.

jcc