Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

NFData1 helper #8

Closed
hvr opened this issue Jun 11, 2015 · 8 comments

Comments

@hvr
Copy link
Member

commented Jun 11, 2015

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

@hvr hvr added the enhancement label Jun 11, 2015

@RyanGlScott

This comment has been minimized.

Copy link
Member

commented Jun 18, 2015

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

This comment has been minimized.

Copy link

commented Jun 19, 2015

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

This comment has been minimized.

Copy link
Member

commented Jun 19, 2015

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

This comment has been minimized.

Copy link

commented Jun 20, 2015

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

This comment has been minimized.

Copy link
Contributor

commented Jun 12, 2016

@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

This comment has been minimized.

Copy link
Contributor

commented Jun 12, 2016

@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

This comment has been minimized.

Copy link

commented Jun 12, 2016

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

This comment has been minimized.

Copy link
Contributor

commented Oct 9, 2016

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

@phadej phadej referenced this issue Oct 11, 2016
4 of 4 tasks complete
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.