Opened 3 years ago

Last modified 2 years ago

#13403 new feature request

Derive instances (Applicative, Monad, ...) for structures lifted over functors

Reported by: Iceland_jack Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.0.1
Keywords: deriving Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

I'll start small: Given that we know how to define various instances for Product GHC could do it automatically.

data P f g a = f a ::: g a deriving (Functor, Applicative, Alternative)

{-
instance (Applicative f, Applicative g) => Applicative (P f g) where
  pure x = pure x ::: pure x
  (f:::g) <*> (x:::y) = (f <*> x) ::: (g <*> y)
-}

And for specific constructors as well

data Q a = [a] :*: Maybe a deriving (Functor, Applicative, Alternative)

{-
instance Applicative Q where
  pure x = [x] :*: Just x
  (f:*:g) <*> (x:*:y) = (f <*> x) :*: (g <*> y)
-}

Alternative

Use GeneralizedNewtypeDeriving

newtype Q a = Q (Product [] Maybe a)
  deriving (Functor, Applicative, Alternative)

pattern (:*:) :: [a] -> Maybe a -> Q a
pattern a :*: b = Q (Pair a b)

Future Work

This should work for a combination of various things, using Const _ deprives us of Alternative

newtype U e a = U (([] `Product` Maybe `Product` Const e) a)
  deriving (Functor, Applicative)

using sums where one summand is identity gives us Applicative / Alternative

-- data Lift f a = Pure a | Other (f a)
import Control.Applicative.Lift

data V a = V ((Lift [] `Product` Maybe) a) 
  deriving (Functor, Applicative, Alternative)

I want to be able to write this directly

data U e a = U [a] (Maybe a) (Const e a)
  deriving (Functor, Applicative)

data V a
  = VL a   (Maybe a)
  | VR [a] (Maybe a)
  deriving (Functor, Applicative, Alternative)

Future, Future Work

left-Kan extension

data Lan g h a where
  Lan :: (g b -> a) -> h b -> Lan g h a
  deriving (Functor, Applicative)

codensity

data Endo a = Endo (a -> a)

newtype CodEndo a = CE (forall xx. (a -> Endo xx) -> Endo xx)
  deriving (Functor, Applicative, Monad)

and comonad

data Rose a = a :< [Rose a]
  deriving (Functor, Applicative, Monad, Comonad, ...)

Change History (8)

comment:1 Changed 3 years ago by Iceland_jack

I'm sure some derivations will be ambiguous, but some can be determined uniquely surely.

Getting instances for free is such a huge strength of Haskell, it would be great to have better support for it.

comment:2 Changed 3 years ago by RyanGlScott

This feels extremely ad hoc and not nearly formalized enough to where I'd be comfortable with it. One nice thing about deriving is that it tends to work with ~90% of the datatypes you'd use regularly, but with this proposal, it feels closer to <50%.

I have no idea how you could teach GHC to recognize "product types" in a way that's uniform and comprehensive. What happens when there are more than two fields? What happens when you have arbitrary nestings of types like data Product f g h a = Product (f (g (f a))) (h (f (g a)))? What if there are constants like data Product a = Product Int a?

But I'm even more concerned about what this proposed feature would do on things that aren't of the particular form that you've labeled "product types". What happens with:

  • newtype Compose f g a = Compose (f (g a))
  • data Proxy a = Proxy

and so on? What would the error messages be like in cases where it wouldn't work?

I'm quite skeptical that this could be made workable. -1 from me.

comment:3 in reply to:  2 ; Changed 3 years ago by Iceland_jack

Thanks for taking the time to respond to my proposals

Replying to RyanGlScott:

This feels extremely ad hoc and not nearly formalized enough to where I'd be comfortable with it.

At least it incites a reaction :) the proposal was but we can go into the direction of Generic's Rep

I have no idea how you could teach GHC to recognize "product types"

It's not just for product types, I should have made myself more clear but I didn't want to complicate the proposal. This should work for our entire polynomial arsenal, Sum, Product, Identity, Const _, when we get to weirder things like Biff things start to collide. Maybe it's a matter of picking a comfortable subset.

data Product f g h a = Product (f (g (f a))) (h (f (g a)))?

That could be encoded as ↓ and we can still derive a whole host of instances

infixr 9 ·
type (·) = Compose

newtype P f g h a = P (Product (f · g · f) (h · f · g) a)
  deriving (Functor, Foldable, Traversable, Applicative, Alternative, Contravariant)

In any case it could be implemented incrementally.

What if there are constants like data Product a = Product Int a?

They could always be rewritten as (I changed Int to String to get that Applicative instance)

newtype Q a = Q (Product (Const String) Identity a)
  deriving (Functor, Foldable, Traversable, Applicative)
  • newtype Compose f g a = Compose (f (g a))
  • data Proxy a = Proxy

Compose and Proxy would likely be primitives in what ever subset of types we support.

Are there other discussions about something similar? Or is this the first time this is proposed.

Last edited 3 years ago by Iceland_jack (previous) (diff)

comment:4 in reply to:  3 Changed 3 years ago by RyanGlScott

Replying to Iceland_jack:

At least it incites a reaction :) the proposal was but we can go into the direction of Generic's Rep

Funny enough, I was going recommend exactly GHC.Generics as a solution to your problem. It gives you the power to exclude awkward subsets of datatypes (e.g., no Monad instances for Compose-like things), and it requires no changes to GHC.

comment:5 Changed 3 years ago by RyanGlScott

Moreover, it wouldn't take much code at all to set up the machinery needed to do this:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE FlexibleContexts #-}
module DeriveApplicativeMonad where

import GHC.Generics

-- Applicative
genericPure :: (Generic1 f, Applicative (Rep1 f))
            => a -> f a
genericPure = to1 . pure

genericAp :: (Generic1 f, Applicative (Rep1 f))
          => f (a -> b) -> f a -> f b
genericAp f x = to1 $ from1 f <*> from1 x

-- Monad
genericBind :: (Generic1 m, Monad (Rep1 m))
            => m a -> (a -> m b) -> m b
genericBind m f = to1 $ from1 m >>= from1 . f

-- Example
data Product f g h a = Product (f (g (f a))) (h (f (g a)))
  deriving (Functor, Generic1)
instance (Applicative f, Applicative g, Applicative h)
    => Applicative (Product f g h) where
  pure  = genericPure
  (<*>) = genericAp

comment:6 Changed 2 years ago by RyanGlScott

Type: bugfeature request

comment:7 Changed 2 years ago by Iceland_jack

Good solution, it won't be possible to derive them unless added as default methods.

I am getting feedback on and mulling over an approach different from my initial proposal

comment:8 Changed 2 years ago by RyanGlScott

Keywords: deriving added
Note: See TracTickets for help on using tickets.