Specialize one method in typeclass in haskell?

user_4254145 0
Viewed 86

I'm writing a type where I want to be able to change the behavior of a method based on the typeclass instantiations of internal types.

As an example, consider this:

class Reduceable a where
    reduce :: a -> a
    -- Other methods not relevant here

instance Reduceable [[a]] where
    -- Reduce a list by dropping empty lists in the front
    reduce = dropWhile null
    -- Other methods implemented

instance Reduceable [a] => Reduceable [[a]] where
    -- Reduce a list of reduceable things by dropping empty lists in the front
    -- and also reducing the elements of the list
    reduce = dropWhile null . map reduce
    -- Other methods identical to Reduceable [[a]]

In this case, I could use OverlappingInstances to make this code work. However, the other functions are somewhat involved in their implementation and do not change based on the type, and so I'd rather not have to implement them multiple times (which, by my understanding of overlapping instances, would be required).

Is there a way I can get what I want in Haskell?

haskell
2 Answers

In general, there's not a really great way to do what you ask. The slightly verbose but idiomatic way is to use newtype to select between multiple instances when such exist. For example, you could wrap your elements in a newtype for which reduce does no work:

newtype Don'tReduce a = Don'tReduce a
instance Reduceable (Don'tReduce a) where reduce = id

Now your instance Reduceable a => Reduceable [a] instance can be made to "bottom out" by converting its elements to [Don'tReduce a]s before calling reduce. This also gives you some flexibility about where you consider the bottom to be; for example, these may all behave differently, and any one of them may be reasonable in a specific situation:

reduce :: Reduceable a => [[[[a]]]] -> [[[[a]]]]
reduce :: [[[[Don'tReduce a]]]] -> [[[[Don'tReduce a]]]]
reduce :: [[[Don'tReduce [a]]]] -> [[[Don'tReduce [a]]]]
reduce :: [[Don'tReduce [[a]]]] -> [[Don'tReduce [[a]]]]
reduce :: [Don'tReduce [[[a]]]] -> [Don'tReduce [[[a]]]]
reduce :: Don'tReduce [[[[a]]]] -> Don'tReduce [[[[a]]]]

You can use coerce to make conversion between [[[[a]]]] and any of the above variation types cheap (free, with optimizations on) at runtime.

user_7916040

The first instance for Reducable can be written as:

instance Reduceable [[a]] where
    reduce = dropWhile null . map id

And the second one is:

instance Reduceable [a] => Reduceable [[a]] where
    reduce = dropWhile null . map reduce

So, reduce is of the form:

reduce = dropWhile null . map reduceElem

where reduceElem :: [a] -> [a] can either be id or reduce.

So let's give reduceElem its own class.

class ReducableElem a where
    reduceElem :: [a] -> [a]
    
instance {-# OVERLAPPING #-} ReducableElem [a] where
    reduceElem = reduce

instance {-# OVERLAPPABLE #-} ReducableElem a where
    reduceElem = id

And then we only need one instance for Reducable.

instance ReducableElem a => Reducable [[a]] where
    reduce = dropWhile null . map reduceElem

Testing it out:

λ> reduce [[],[],[1,2],[3,4]] :: [[Int]]    
[[1,2],[3,4]]

λ> reduce [[],[],[[],[1,2]],[[3,4],[5,6]]] :: [[[Int]]]
[[[1,2]],[[3,4],[5,6]]]
user_175929950
Related