Weird type error when implementing MonoFoldable instance

[lehmacdj]

I tried implementing a MonoFoldable instance, but got this terrible type error.

mono-foldable-impl.hs:31:10: error:
    • Occurs check: cannot construct the infinite type:
        a2 ~ Element (t2 a2)
        arising from a use of ‘Data.MonoTraversable.$dmofoldr1Ex’
      The type variables ‘t2’, ‘a2’ are ambiguous
    • In the expression: Data.MonoTraversable.$dmofoldr1Ex @(Test)
      In an equation for ‘ofoldr1Ex’:
          ofoldr1Ex = Data.MonoTraversable.$dmofoldr1Ex @(Test)
      In the instance declaration for ‘MonoFoldable Test’
   |
31 | instance MonoFoldable Test where
   |          ^^^^^^^^^^^^^^^^^

Based on what I can tell it looks like the ambiguity is caused by the default method implementation, but I don't understand what would cause that, because I don't have a Foldable instance.

Here are 2 minimal examples that produces this type error. I'm using all of the language extensions from Data.MonoTraversable in case one of those was necessary for implementing MonoFoldable. I get it uniformly either when implementing all methods or when copying the implementation of MonoFoldable ByteString but introducing a newtype wrapper.

#!/usr/bin/env stack
{- stack
  exec ghci
  --resolver lts-16.25
  --package mono-traversable
  --package bytestring
-}

{-# LANGUAGE ConstrainedClassMethods #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

module Main (main) where

import Data.ByteString (ByteString)
import qualified Data.ByteString as S
import Data.MonoTraversable
import Data.Word

data Test = Test {_a :: Int, _b :: Int}

type instance Element Test = Int

instance MonoFoldable Test where
  -- I also tried providing InstanceSigs but that didn't help
  -- ofoldMap :: Monoid m => (Int -> m) -> Test -> m
  ofoldMap f (Test a b) = f a <> f b
  -- ofoldr :: (Int -> a -> a) -> a -> Test -> a
  ofoldr f acc (Test a b) = f a (f b acc)
  -- ofoldl' :: (a -> Int -> a) -> a -> Test -> a
  ofoldl' f acc (Test a b) = f (f acc a) b

newtype Test2 = Test2 {unTest2 :: ByteString}

type instance Element Test2 = Word8

instance MonoFoldable Test2 where
  ofoldMap f = ofoldr (mappend . f) mempty
  ofoldr f acc = S.foldr f acc . unTest2
  ofoldl' f acc = S.foldl' f acc . unTest2
  otoList = S.unpack . unTest2
  oall f = S.all f . unTest2
  oany f = S.any f . unTest2
  onull = S.null . unTest2
  olength = S.length . unTest2
  oelem e = S.elem e . unTest2
  onotElem e = S.notElem e . unTest2

main :: IO ()
main = error "only intended for use in interactive ghci session"

Would greatly appreciate it if someone could help me understand this error and a working example of how to implement MonoFoldable. We can add an example to the documentation then too so others don't face a similar problem in the future.

[snoyberg]

I agree that the error message isn't great. But this is the way that default implementations work. The solution is to provide an explicit implementation for the missing ofoldr1Ex and ofoldl1Ex' methods.

[lehmacdj]

Okay, my bad, I didn't see those.

Hmm, one thing that made this more challenging than necessary to figure out was that minimal complete implementation wasn't useful because it doesn't list what things one needs to implement unless your type is already an instance of Foldable.

A thing that might have made this a little easier for me would have been a newtype WrappedFoldable that provides the default implementations for the case when the implementing type is also Foldable that could be used DerivingVia which would avoid this type errors. Then because we aren't relying on the default implementations with DefaultSignatures we could also provide default implementations for more of MonoFoldable's methods so instances that don't have Foldable to rely on would be able to implement only ofoldMap for example just like Foldable.

This is a breaking change though so probably not worth doing :(

Thanks, feel free to close this.

[lehmacdj]

Oh one more thought, is there a reason why we have 5 methods with DefaultSignatures instead of just 1 or 2 and then providing implementations of the others in terms of only MonoFoldable? We can easily implement ofoldr1Ex and ofoldlEx' in terms of ofoldr1 and ofoldl' respectively, just as base does for the corresponding operations:

foldr1Ex f xs = fromMaybe (errorWithoutStackTrace "ofoldr1Ex: empty structure") (ofoldr mf Nothing xs)
      where
        mf x m = Just (case m of
                         Nothing -> x
                         Just y  -> f x y)

[snoyberg]

It's because the underlying Foldable implementations may be more optimized than a default implementation, and we'd want to take advantage of them if possible. Unfortunately GHC doesn't support "use a default implementation if this constraint is satisfied, and fall back to this other default implementation otherwise."