Suppose I have a data type T that has an equality function and a list:
data T a = T (a -> a -> Bool) [a]
How can I use a predefined function that requires Eq a, but uses the equality function in T?
As an example:
elemIndices' x (T eq xs) = (???? Data.List.elemIndices) x xs
-- same as Data.List.elemIndices:
elemIndices' 1 (T (==) [0,1,2,1,3]) == [1,3]
-- "inverse" of Data.List.elemIndices:
elemIndices' 1 (T (/=) [0,1,2,1,3]) == [0,2,4]
I would prefer not to re-implement the functions like Data.List.elemIndices above.
As @chi notes in a comment, there's no direct way to "override" an Eq a constraint with your own implementation, as it would be an unsafe operation. This is why most Data.List functions that use an Eq constraint (e.g., group) also have a separate version where the equality function can be supplied by the caller (e.g., groupBy). @cafce25 has pointed out in their answer that findIndices will work well as a more general elemIndices.
More generally, the usual, safe way of calling a function with a different Eq a instance is to introduce a newtype to replace the Eq instance. This works fine when you have a fixed alternative equality function:
myEq :: Int -> Int -> Bool
myEq x y = even x == even y
newtype MyInt = MyInt Int
instance Eq MyInt where
(==) == coerce myEq
elemIndices' :: Int -> [Int] -> [Int]
elemIndices' x xs = elemIndices (MyInt x) (coerce xs)
main = print $ elemIndices' 2 [1..10] -- indices of all even elements
but adapting it to your situation, where the equality operation is determined at runtime, is a bit of a challenge.
I think the best you can do is construct a data type that pairs each element with a copy of the equality function, and give it an appropriate Eq instance:
data WithEq a = WithEq (a -> a -> Bool) a
instance Eq (WithEq a) where
WithEq eq x == WithEq _ y = eq x y
Then, you can write:
data T a = T (a -> a -> Bool) [a]
elemIndices' :: a -> T a -> [Int]
elemIndices' x (T eq xs) = elemIndices (withEq x) (map withEq xs)
where withEq = WithEq eq
and, for example:
main = print $ elemIndices' 2 (T (\x y -> even x == even y) [1..10])
Obviously, there are some potential efficiency problems here, though GHC may do a reasonable job optimization away some of the extra copies of the equality function.
In the example above, GHC optimizes the code to equivalent of:
go x i | x > 10 = []
| even x = i : go (x+1) (i+1)
| otherwise = go (x+1) (i+1)
main = print $ go 1 0
with the integers unboxed, so no time or space is wasted making copies of the equality function, and it's fully lifted out of the data structure so it can be inlined into the rest of the code.
So, even though this is a little ugly, it seems like a workable solution.
Full example:
import Data.List
data WithEq a = WithEq (a -> a -> Bool) a
instance Eq (WithEq a) where
WithEq eq x == WithEq _ y = eq x y
data T a = T (a -> a -> Bool) [a]
elemIndices' :: a -> T a -> [Int]
elemIndices' x (T eq xs) = elemIndices (withEq x) (map withEq xs)
where withEq = WithEq eq
main :: IO ()
main = print $ elemIndices' 2 (T (\x y -> even x == even y) [1..10])