Haskell create functor with type constraints-CodePudding

I have this Haskell code fragment:

{-# LANGUAGE InstanceSigs #-}

module LatticePoint 
where

import Data.List    

data (Eq v) => LatticePoint v = LatticePoint{prob::Double, value::v}

instance Functor LatticePoint where
    fmap :: (Eq a, Eq b) => (a -> b) -> LatticePoint a -> LatticePoint b 
    fmap f lp = LatticePoint {prob = prob lp, value = f $ value lp}

On compilation I get the following error, which I don't understand

src/LatticePoint.hs:12:14: error:
    • No instance for (Eq a)
      Possible fix:
        add (Eq a) to the context of
          the type signature for:
            fmap :: forall a b. (a -> b) -> LatticePoint a -> LatticePoint b
    • When checking that instance signature for ‘fmap’
        is more general than its signature in the class
        Instance sig: forall a b.
                      (Eq a, Eq b) =>
                      (a -> b) -> LatticePoint a -> LatticePoint b
           Class sig: forall a b.
                      (a -> b) -> LatticePoint a -> LatticePoint b
      In the instance declaration for ‘Functor LatticePoint’
   |
12 |     fmap ::  (Eq a, Eq b) => (a -> b) -> LatticePoint a -> LatticePoint b 
   | 

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

What I'm trying to achieve is for LatticePoint to be restricted to any type v which is an instance of Eq, and to make LatticePoint an instance of Functor.

Any help appreciated!

Steve

CodePudding user response：

Your LatticePoint is not a Functor. A Functor is defined to state "For every pair of types a and b, I can lift a function a -> b to a function f a -> f b". You can't provide an instance that only works for a few types, or for some but not all. This is the same reason Set is not a functor, since all nontrivial operations on it require Ord on the element type.

Before we can use an alternative to Functor, we will actually need to take some advice from the comment section of this post. As pointed out, in Haskell, it's typical to not constrain a datatype itself but to merely constrain all functions that act on it (the feature allowing datatype constraints is largely considered a misfeature and its use is discouraged). So rather than putting the Eq constraint in the data line, it's more idiomatic to leave the data line an ordinary declaration and constrain every function that takes or produces a LatticePoint.

This is because, if you constrain the datatype directly, it's not even meaningful to say LatticePoint a for every a, which makes it much harder to reason about types (every time you want to mention your type in any context, you effectively need to accompany it with a proof of correctness). But if the LatticePoint a type is well-defined for every a but just happens to be useless and unconstructible for some of them, it's much easier to reason about our types. So I'll assume our declaration is

data LatticePoint v = LatticePoint{prob::Double, value::v}

We can approximate what you want with MonoFunctor. MonoFunctor provides a much weaker constraint. It says "Given some definition of 'element type' for our container, I can lift functions on elements to functions on the container type". Crucially, we never said it had to work for all types, just for types which the container says are valid "elements".

type instance Element (LatticePoint a) = a

Now we can write our MonoFunctor instance.

instance Eq a => MonoFunctor (LatticePoint a) where
  omap :: (a -> a) -> LatticePoint a -> LatticePoint a
  omap f latticePoint = ...

You'll note one thing here: our function has to map from a to a. It can't map to a different target type, even if both the source and target are Eq. This is simply a restriction of MonoFunctor, and I'm not aware of any typeclass that allows MonoFunctor-style class constraints and allows maps which are not endomorphisms.

CodePudding user response：

Converting my comments to an answer, you typically defer the constraints to the functions that use LatticePoint in a context where the value requires an Eq constraint. This lets you define fmap.

module LatticePoint 
where

import Data.List    

data LatticePoint v = LatticePoint{prob::Double, value::v}

instance Functor LatticePoint where
    fmap :: (a -> b) -> LatticePoint a -> LatticePoint b 
    fmap f lp = LatticePoint {prob = prob lp, value = f $ value lp}

foo :: Eq a => LatticePoint a -> Whatever
foo lp = ...

If you think about it, the data structure itself doesn't care whether value can be compared for equality, only functions that use the data structure.

As a concrete example, consider a definition of (==) itself:

instance Eq a => Eq (LatticePoint a) where
    (LatticePoint p1 v1) == (LatticePoint p2 v2) = p1 == p2 && v1 == v2