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.
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)
.