Why add extra functions to type classes instead of using rewrite rules?

Uncategorized
1

If we look e.g. at the definition of Foldable, aside from foldMap/foldr, it also contains a bunch of other methods like minimum that have a default implementation in terms of foldMap.

AFAIK this is done to allow to overwrite these default implementations in the instance declarations if there exists are more performant version for the concrete type.

Why would we clutter the definition of type classes just for this when rewrite rules would do the same? Is there a good reason?

E.g. length is part of the type class, so that e.g. Data.Map can just return the stored length instead of doing a traversal. But with a rewrite rule, the same could be achieved:
{-# RULES "Data.Foldable.length/Map" length = size #-}

2 Likes
2

Can you give a more detailed example of how this should work? As far as I can see:

length :: Foldable t => t a -> Int
size :: Map k a -> Int

So I guess we would rather need a rule like this:

{-# RULES "Data.Foldable.length/Map" length @Map = size #-}

I am not too familiar with what is allowed in RULES, @jaror might be more knowledgeable, but does GHC accept either of these rules? I am currently on a train and can’t check myself :slight_smile:

1 Like
3

If you did this, you would rely on rewrite rules firing for asymptotics and that would be a bit problematic.

E.g. in this case one immediate effect would be that any builds at -O0 (including ghci) would use an abysmally slow linear time length implementation.

In optimized builds, rewrite rules still won’t work in polymorphic contexts that aren’t inlined or specialized. If you have

average :: Foldable f => f Double -> Double
average foldable = sum foldable / length foldable

then if average is not inlined or specialized, it will have to use the generic length implementation on Foldables, whereas with a separate method, it will receive the optimized length implementation from the Foldable dictionary.

But even in optimized builds where every function you care about is entirely monomorphic, rewrite rules are still not guaranteed to fire depending on what exactly the optimizer does. If it inlines length before firing the rule, there is nothing for it to rewrite.

So even in this case there is still a chance that some length calls on maps will be extremely slow for no obvious reason.

2 Likes
4

Because extra functions is Haskell. Rewrite rules are not (they are a GHCism).

6 Likes
5

Yes, see 6.19.1. Rewrite rules — Glasgow Haskell Compiler 9.15.20260306 User's Guide

That is indeed a good point that I did not think about

6

I think the issue of how to handle unspecialized functions kills this idea (if only we had a JIT compiler…).

I think the issue with -O0 vs -O1 producing different asymptotics is not a huge issue in practice. There are already cases where -O0 is too slow to be practical. And we could conceivably change GHC to apply some lightweight rewrite rules even under -O0.

For optimized and monomorphic code you indeed still need to be careful defining rules on type class members, because GHC will indeed probably specialize or inline them before the rule can fire. But there are ways around it as described in the GHC guide. Instead of defining the rule like this:

{-# RULES "Data.Foldable.length/Map" length @Map = size #-}

You need to make sure that the foldr on your datatype has proper phase annotations:

instance Foldable (Map k) where
   foldr = foldrMap

foldrMap = ...
{-# NOINLINE [1] foldrMap #-}

Then you can define the rewrite rule on that foldrMap:

{-# RULES "Data.Foldable.length/Map" foldrMap (\_ n -> n + 1) 0 = size #-}
1 Like
7

What @augustss said. GHC was already too complicated ten years ago. It’s bad enough keeping up with all the syntax it has introduced within Haskell; let alone a completely other bunch of syntax for RULES; and it seems subtleties about when/how they fire.

1 Like