Avoiding use of unsafeCoerce in Hughes' list functor instance

Question

I have a newtype to represent Hughes' list (ie, list construction):

newtype Hughes a = Hughes {unHughes :: [a] -> [a]}

With some functions to work on it:

mkHughes :: [a] -> Hughes a
mkHughes = Hughes . (++)

runHughes :: Hughes a -> [a]
runHughes h = unHughes h []

The Monoid instance is as easy as the functions above are:

instance Monoid (Hughes a) where
    mempty = Hughes id
    mappend (Hughes f) (Hughes g) = Hughes (f . g)

...but trouble arises when I get to the Functor and Applicative instances. This is what I've come up with so far:

instance Functor Hughes where
    fmap f (Hughes h) = Hughes $ unsafeCoerce $ fmap f . h

instance Applicative Hughes where
    pure = Hughes . (:)
    (<*>) (Hughes f) (Hughes v) = Hughes $ unsafeCoerce $
                                  (<*>) <$> f <*> unsafeCoerce v

The problem I have is that I don't like using unsafeCoerce. Is there a way to design the Functor instance without using it, or is it unavoidable?

Furthermore, how would I implement the Monad instance for this datatype?

EDIT: Unlike in the DList package, I want to keep the performance improvement, ie, not evaluating the [a] -> [a] but mapping it.

Answer 1

There is no way to implement a Functor Hughes instance.

Let's examine the definition of Hughes:

data Hughes a = Hughes ([a] -> [a])
                         ^

We can see that the parameter a appears contravariant in the marked location. A Functor instance can only exist when all appearances of the last type parameter are covariant.

Basically you are asked to define a function fmap :: (a -> b) -> ([a] -> [a]) -> [b] -> [b]. The problem is that you can't do anything with [b], there is no function that accepts [b] or b. You can ignore it, but then the functor law fmap id = id will not hold.

As for DList, the Functor instance is valid because the implementation doesn't export the actual data constructor, only smart constructors. As a result, you cannot constuct dlist values that are arbitrary list processing functions. With provided smart constructors you can only construct dlists that are isomorphic to [a], which is why the functor laws hold.

If you were to somehow hack (bring) the constructor into the scope, you would find that the functor laws don't actually hold for arbitrary functions, for example that fmap id x /= x if x is something like DList (map negate).