NFData1 helper

[hvr]

quoting http://permalink.gmane.org/gmane.comp.lang.haskell.libraries/24907, Henning writes

I have the type

   data NonEmpty f a = NonEmpty a (f a)

and want to declare an NFData instance in Haskell 98. With the
existing NFData class this is not possible because it requires a
(NFData (f a)) constraint which needs FlexibleContexts. A solution
would be an NFData1 class analogously to the classes in
transformers:Data.Functor.Classes:

  class NFData1 f where
     rnf1 :: NFData a => f a -> ()

  instance NFData1 [] where
     rnf1 = rnf

  instance (NFData1 f) => NFData1 (NonEmpty f) where
     rnf1 (NonEmpty x xs) = rnf (x, rnf1 xs)

  instance (NFData1 f, NFData a) => NFData (NonEmpty f a) where
     rnf = rnf1

[RyanGlScott]

Note that in the next version of transformers, the typeclasses in Data.Functor.Classes will look slightly different. If you want the proposed NFData1 class to match the new design, it will look something like this:

class NFData1 f where
   rnfWith :: (a -> ()) -> f a -> ()

rnf1 :: (NFData1 f, NFData a) => f a -> ()
rnf1 = rnfWith rnf

instance NFData1 [] where
    rnfWith _ []      = ()
    rnfWith rw (x:xs) = rw x `seq` rnfWith rw xs

instance (NFData1 f) => NFData1 (NonEmpty f) where
    rnfWith rw (NonEmpty x xs) = rnf (rw x, rnfWith rw xs)

instance (NFData1 f, NFData a) => NFData (NonEmpty f a) where
    rnf = rnf1

Functionally, rnf1 would be the same, but rnfWith allows more flexibility in defining how the occurrence of the type parameter should be reduced to NF.

[ezyang]

I am not very sympathetic to the Haskell'98 motivation. For example, if you look at the evolution of Typeable, we have moved away from Typeable/Typeable1/Typeable2 using kind polymorphism. In the requester's case, FlexibleInstances works fine to support the instances he wants to write.

[RyanGlScott]

Keep in mind that there is another important use-case for higher-kinded class analogues: handling polymorphic recursion. Using an example from http://flint.cs.yale.edu/trifonov/papers/sqcc.pdf:

newtype Two f a = Two (f (f a))
data Sq f a = M a (f a) | E (Sq (Two f) a)

One can create an NFData instance for Two:

instance NFData (f (f a)) => NFData (Two f a) where
    rnf (Two t) = rnf t

However, if we try to define an NFData instance for Sq:

instance (NFData a, NFData (f a)) => NFData (Sq f a) where
    rnf (M a f) = rnf (a, f)
    rnf (E sq) = rnf sq

If we try to typecheck this, GHC will complain that an NFData (f (f a)) constraint is needed. Adding that, GHC will complain that an NFData (f (f (Two f a))) constraint is needed. Adding that, GHC will complain that an NFData (f (f (Two f (Two (Two f) a)))) instance... repeat ad infinitum.

With NFData1, this is possible:

class NFData1 f where
   rnfWith :: (a -> ()) -> f a -> ()

instance NFData1 f => NFData1 (Two f) where
    rnfWith r (Two t) = rnfWith (rnfWith r) t

instance NFData1 f => NFData1 (Sq f) where
    rnfWith r (M a f) = rnf (r a, rnfWith r f)
    rnfWith r (E sq) = rnfWith r sq

By the way, this reveals the power of the rnfWith :: (a -> ()) -> f a -> () as opposed to rnf1 :: NFData a => f a -> (). With the latter, you cannot define an NFData1 instance for Two.

[dolio]

Technically, anything you can do with rnfWith can be done with rnf1. It's much nicer to just have the former, though.

If someone can come up with a way to make NFData polykinded, that'd be great. But it's not going to be anywhere near as easy as Typeable, because we need to take actual arguments of the relevant type, not just deal in things like TypeRep and Proxy where the polykinded argument is phantom. I'd be a bit surprised if there were a solution that weren't fairly messy.

[phadej]

@dolio I doubt that

Technically, anything you can do with rnfWith can be done with rnf1.

E.g. Eq1 from transformers-0.4 for Compose has definition

instance (Functor f, Eq1 f, Eq1 g) => Eq1 (Compose f g) where eq1 = (==)

when in transformers-0.5 it's more sensible head, though a bit more complex definition

instance (Eq1 f, Eq1 g) => Eq1 (Compose f g) where
    liftEq eq (Compose x) (Compose y) = liftEq (liftEq eq) x y

Same would hold for Two example, you'd need to fmap thru outer f to do stuff there, see: https://gist.github.com/phadej/75f9c8ce4958102242e3646d3cc885ae

class NFData1' f where
    rnf1 :: NFData a => f a -> ()

{-
instance NFData1' f => NFData1' (Two f) where
    rnf1 (Two t) = rnf1 t

--    Could not deduce (NFData (f a)) arising from a use of ‘rnf1’
--    from the context (NFData1' f)
-}

data X f a = X { getX :: f a }

instance Functor f => Functor (X f) where
   fmap f (X x) = X (fmap f x)

instance NFData1' f => NFData1' (X f) where
    rnf1 (X x) = rnf1 x

instance (NFData1' f, NFData a) => NFData (X f a) where
    rnf = rnf1

instance (NFData1' f, Functor f) => NFData1' (Two f) where
    rnf1 (Two t) = rnf1 (fmap X t)

[phadej]

@dolio also in GHC-8.0 you can do not so messy polymorphic classes, because of injective type families and TypeInType: https://gist.github.com/phadej/2fc066c00e33b9486e1a3e5f7767a8d7 but that's very fragile looking, and you still have todo some manual work per new kind you want to support

[dolio]

Yes, I think it's true that you need some extra conditions to use the old style, because fooWith contains some evidence that the type in question is covariant (or more precisely perhaps, foldable).

I guess that polykinded NFData example isn't too terrible. :) I'm not sure I could support it going into the library, though. It seems like it'd be unpleasant to actually use without the wrappers. But maybe that's not a big deal; I don't know.

[phadej]

ekmett/bound#36 needs for some kind of NFData1 too