Is it possible to define instances of Data.Foldable with foldr where foldr takes arguments of different types?

Question

The type class Data.Foldable has the following definition:

class Foldable t where
    {-# MINIMAL foldMap | foldr #-}
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr :: (a -> b -> b) -> b -> t a -> b
    ....
    <more definitions>

The minimal stanza says, that I it's possible to define an instance only with the foldr function. In all the examples I can compile, the foldr function has type a -> a -> a. However I'm unable to define something where the foldr function has really type a -> b -> b where the types a and b are different.

The following code shows an example, that does NOT compile:

import Data.Foldable

data Tree a = Tree a a | Leaf a

class Size a where
   size :: a -> Int 

instance Size a => Foldable (Tree a) where
  foldr :: a -> Int -> Int
  foldr x n = size x + n

Is it possible to define an instance of Foldable with foldr, where the types a and b are really different?

Peter Hall Peter Hall · Accepted Answer · 2017-09-19T10:55:37

The problem isn't that the types are different. The type of your foldr is just not the same as what Foldable requires. It would need to be:

foldr :: (a -> b -> b) -> b -> Tree a -> b

And those a and b type parameters must remain as parameters: this has to work for all choices of a and b. You can't constrain them to some other type class and you can't restrict one of them to be a concrete Int type.

Is it possible to define instances of Data.Foldable with foldr where foldr takes arguments of different types?

2 Answers