Unexpected behavior of coerce inside foldMap's callback

Question

This code compiles:

import Data.List (isPrefixOf)
import Data.Monoid (Any(..))
import Data.Coerce

isRoot :: String -> Bool
isRoot path = getAny $ foldMap (coerce . isPrefixOf) ["src", "lib"] $ path

I'm using coerce as a shortcut for wrapping the final result of isPrefixOf in Any.

This similar code doesn't compile (notice the lack of .):

isRoot :: String -> Bool
isRoot path = getAny $ foldMap (coerce isPrefixOf) ["src", "lib"] $ path

The error is:

* Couldn't match representation of type `a0' with that of `Char'
    arising from a use of `coerce'
* In the first argument of `foldMap', namely `(coerce isPrefixOf)'
  In the first argument of `($)', namely
    `foldMap (coerce isPrefixOf) ["src", "lib"]'
  In the second argument of `($)', namely
    `foldMap (coerce isPrefixOf) ["src", "lib"] $ path'

But my intuition was that it, too, should compile. After all, we know that the arguments of isPrefixOf will be Strings, and that the result must be of typeAny. There's no ambiguity. So String -> String -> Bool should be converted to String -> String -> Any. Why isn't it working?

Answer 1

This doesn't really have anything to do with coercions. It's just constraint solving in general. Consider:

class Foo a b
instance Foo (String -> Bool) (String -> Any)
instance Foo (String -> String -> Bool) (String -> String -> Any)

foo :: Foo a b => a -> b
foo = undefined

bar :: String -> String -> Any
bar = foo . isPrefixOf

baz :: String -> String -> Any
baz = foo isPrefixOf

The definition of bar works fine; the definition of baz fails.

In bar, the type of isPrefixOf can be directly inferred as String -> String -> Bool, simply by unifying the type of bars first argument (namely String) with the first argument type of isPrefixOf.

In baz, nothing whatsoever can be inferred about the type of isPrefixOf from the expression foo isPrefixOf. The function foo could do anything to the type of isPrefix to get the resulting type String -> String -> Any.

Remember that constraints don't really influence type unification. Unification occurs as if the constraints weren't there, and when unification is finished, the constraints are demanded.

Getting back to your original example, the following is a perfectly valid coercion, so the ambiguity is real:

{-# LANGUAGE TypeApplications #-}

import Data.Char
import Data.List (isPrefixOf)
import Data.Monoid (Any(..))
import Data.Coerce

newtype CaselessChar = CaselessChar Char
instance Eq CaselessChar where CaselessChar x == CaselessChar y = toUpper x == toUpper y

isRoot :: String -> Bool
isRoot path = getAny $ foldMap (coerce (isPrefixOf @CaselessChar)) ["src", "lib"] $ path

Answer 2

isPrefix has inferred type [a] -> [a] -> Bool (with a constraint Eq a) the expected type of coerce isPrefix there is [Char] -> [Char] -> Any, so you end up with a constraint Coercible a Char, but there is nothing that actually constrains a to be Char. In fact, it could be any newtype around Char, which might have a different Eq instance.

newtype CChar = CChar Char

instance Eq CChar where
  _ == _ = True

bad :: String -> Bool
bad path = getAny $ foldMap (coerce (isPrefixOf :: [CChar] -> [CChar] -> Bool)) ["src", "lib"] $ path

Answer 3

I figured I'd point out one sometimes-convenient workaround. You basically want

isRoot :: String -> Bool
isRoot path = getAny $ foldMap (Any . isPrefixOf) ["src", "lib"] $ path

but want to coerce isPrefixOf rather than composing a function with it. In this situation, there's really no point, but if you have some unknown passed function instead of isPrefixOf, this can sometimes be important for performance. If you don't want to give a full type signature to coerce, or use type applications, one option is to replace the composition operator with a coercing one.

import Data.Profunctor.Unsafe ((#.))

isRoot :: String -> Bool
isRoot path = getAny $ foldMap (Any #. isPrefixOf) ["src", "lib"] $ path

The Profunctor instance for -> defines (#.) something like

-- (#.) :: Coercible b c => q b c -> (a -> b) -> a -> c
_ #. f = coerce f

Answer 4

Here's how I think of it.

You have a function coerce isPrefixOf, and via context that function is constrained to have type String -> String -> Any. isPrefixOf on its own has type Eq a => [a] -> [a] -> Bool.

Clearly coerce needs to convert the Bool into an Any in the return value, but what about the arguments? Are we instantiating isPrefixOf to [Char] -> [Char] -> Bool and then coercing to [Char] -> [Char] -> Any? Or are we instantiating isPrefixOf to [T] -> [T] -> Bool (for some T) and then coercing T to Char as well as Bool to Any? We need to know the instantiation of isPrefixOf before we can say whether this is valid.¹

If we were applying isPrefixOf directly² then the fact that we were processing a String would instantiate isPrefixOf's type variable to Char and everything would work. But you never directly use isPrefixOf; you use coerce isPrefixOf. So those strings you're processing are not connected to the a in isPrefixOf's type, they're connected to the resulting type of coerce isPrefixOf. That doesn't help us instantiate the type of isPrefixOf before coerce gets hold of it. That a could be anything that coerce could translate into Char, it is not forced to be Char by this context. Something else is needed to tell us that a must be Char.

That ambiguity is what GHC is complaining about. It's not that the compiler isn't clever enough to notice that the only possible choice for isPrefixOf is [Char] -> [Char] -> Any, rather the code you've written is actually missing a piece of information the compiler needs to (correctly) deduce that.

coerce utterly destroys type inference "through" it, because as far as type inference is concerned coerce :: a -> b (whether the Coercible a b constraint actually holds up to scrutiny is another matter). There are no constraints on what types coerce can "try" to convert between, only on what it can successfully convert, so no chains of unification can be drawn through coerce. You'll need to pin down the types of each side independently, if there are any type variables.³

---

¹ And actually, there could be multiple valid ways to instantiate it that result in different behaviour for your final function. An obvious one would be newtype CaseInsensitiveChar = C Char where the Eq instance uses toLower; isPrefixOf :: [CaseInsensitiveChar] -> [CaseInsensitiveChar] -> Bool can also be coerced to [Char] -> [Char] -> Any, but has different behaviour than a coerced isPrefixOf :: [Char] -> [Char] -> Bool.

² Or rather, passing it to a foldMap which is applied to strings.

³ By "side" I'm referring to the way isPrefixOf is on the "inside" of a coerce application, and everything else only interacts with the result of coerce and so is on the "outside".