Code Monkey home page Code Monkey logo

invariant-functors's People

Contributors

ashleyyakeley avatar dnnx avatar fumieval avatar glguy avatar josephcsible avatar nikita-volkov avatar peti avatar quasicomputational avatar ryanglscott avatar

Stargazers

avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar

Watchers

avatar avatar avatar

Forkers

dnnx puffnfresh glguy quasicomputational haskell-vanguard hackage-package-forks nikita-volkov ashleyyakeley terrorjack josephcsible

invariant-functors's Issues

Invariant analogs of Applicative/Divisible and Alternative/Decidable?

We all know about Applicative and Alternative:

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a

And the contravariant package has analogs for these two classes in the Data.Functor.Contravariant.Divisible module:

class Contravariant f => Divisible f where
  divide  :: (a -> (b, c)) -> f b -> f c -> f a
  conquer :: f a

class Divisible f => Decidable f where
  lose   :: (a -> Void) -> f a
  choose :: (a -> Either b c) -> f b -> f c -> f a

The invariant package gives us the wonderful Invariant typeclass that brings together covariant and contravariant functors into a single abstraction. Can we similarly bring together Applicative/Divisible and Alternative/Decidable?

Some things to consider:

  1. What would we name these typeclasses?
  2. What would the laws be?

Could the relationship between covariant / contravariant / invariant functors be a little more fine-grained?

Should the instances

(Invariant f, Invariant g) => Invariant (ComposeFC f g)
(Invariant f, Invariant g) => Invariant (ComposeCF f g)

be

(Functor f, Contravariant g) => Invariant (ComposeFC f g)
(Contravariant f, Functor g) => Invariant (ComposeCF f g)

instead?

This would possibly lead to some additional newtypes to handle all of the other combinations of covariant / contravariant / invariant functors that can be composed to form an invariant functor:

ComposeFI
ComposeIF
ComposeIC
ComposeCI
ComposeII

I'm happy to do this work - and I have usages in mind for all (or at least most) of this - I just wanted to check if it was a welcome change before I got stuck in.

Deriving Invariant(2) chokes on type families with an appropriate return kind

Consider the following setup:

{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE TypeFamilies #-}
module Bug where

import Data.Functor.Invariant
import Data.Functor.Invariant.TH
import Data.Kind

type family F :: Type -> Type
type instance F = Maybe
newtype T a = MkT (F a)

One can derive an Invariant instance for T using GeneralizedNewtypeDeriving:

deriving newtype instance Invariant T

Trying to use Template Haskell to accomplish the same thing, however, fails:

$(deriveInvariant ''T)
Bug.hs:1:1: error:
    Exception when trying to run compile-time code:
      Constructor ‘MkT‘ must only use its last two type variable(s) within the last two argument(s) of a data type
CallStack (from HasCallStack):
  error, called at src/Data/Functor/Invariant/TH.hs:765:32 in invariant-0.5.3-5edbdf16830a74cf3d873d1e8c189d1d1072916c6f619d755ea7cef9a655ef4d:Data.Functor.Invariant.TH
    Code: deriveInvariant ''T
  |
1 | {-# LANGUAGE DerivingStrategies #-}
  | ^

The issue is that deriveInvariant is too conservative: it bails out if the last type variable (a) occurs as the argument to any type family whatsoever. Although F is a type family, its use in MkT is benign, since the type F a oversaturates F (it has zero type variable binders). deriveInvariant should take the number of type variable binders a type family has into account so as to permit the program above.

Build failure: invariant-0.2.2 using bifunctors-5.2 

[4 of 4] Compiling Data.Functor.Invariant ( src/Data/Functor/Invariant.hs, .stack-work/dist/x86_64-linux/Cabal-1.22.5.0/build/Data/Functor/Invariant.o )

/home/dan/scratch/invariant-0.2.2/src/Data/Functor/Invariant.hs:277:12:
    Kind incompatibility when matching types:
      f0 :: * -> * -> *
      Joker g :: k -> * -> *
    Expected type: (a1 -> b)
                   -> (b -> a1) -> Joker g a a1 -> Joker g a b
      Actual type: (a1 -> b) -> (b -> a1) -> f0 c0 a1 -> f0 c0 b
    Relevant bindings include
      invmap :: (a1 -> b) -> (b -> a1) -> Joker g a a1 -> Joker g a b
        (bound at src/Data/Functor/Invariant.hs:277:3)
    In the expression: invmap2 id id
    In an equation for ‘invmap’: invmap = invmap2 id id

How I reproduced this on my local machine:

  • stack unpack invariant-0.2.2 && cd invariant-0.2.2
  • stack init --resolver nightly-2016-01-16
  • edit stack.yaml, change extra-deps: [] to extra-deps: [bifunctors-0.2]
  • stack build

Deriving Invariant(2) falls over on sufficiently higher-rank field types

It turns out that Data.Functor.Invariant.TH suffers from the same bug that caused GHC#17880. Here is a minimal demonstration of the bug:

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TemplateHaskell #-}
module Bug where

import Data.Functor.Invariant.TH

data T a = MkT (forall b. b -> (forall c. a -> c) -> a)
$(deriveInvariant ''T)

This should compile, but fails with the following error:

Bug.hs:8:3: error:
    • Couldn't match type ‘forall c. a -> c’ with ‘a -> p0’
      Expected type: b1 -> (a -> p0) -> a
        Actual type: b1 -> (forall c. a -> c) -> a
    • In the first argument of ‘\ x_aiIU b_aiIV
                                  -> (\ x_aiIW b_aiIX
                                        -> covMap1_aiIR
                                             (x_aiIW
                                                ((\ x_aiIY b_aiIZ
                                                    -> (\ x_aiJ0 -> x_aiJ0)
                                                         (x_aiIY (covMap1_aiIR b_aiIZ)))
                                                   b_aiIX)))
                                       (x_aiIU ((\ x_aiJ1 -> x_aiJ1) b_aiIV))’, namely
        ‘arg1_aiIT’
      In the first argument of ‘MkT’, namely
        ‘((\ x_aiIU b_aiIV
             -> (\ x_aiIW b_aiIX
                   -> covMap1_aiIR
                        (x_aiIW
                           ((\ x_aiIY b_aiIZ
                               -> (\ x_aiJ0 -> x_aiJ0) (x_aiIY (covMap1_aiIR b_aiIZ)))
                              b_aiIX)))
                  (x_aiIU ((\ x_aiJ1 -> x_aiJ1) b_aiIV)))
            arg1_aiIT)’
      In the expression:
        MkT
          ((\ x_aiIU b_aiIV
              -> (\ x_aiIW b_aiIX
                    -> covMap1_aiIR
                         (x_aiIW
                            ((\ x_aiIY b_aiIZ
                                -> (\ x_aiJ0 -> x_aiJ0) (x_aiIY (covMap1_aiIR b_aiIZ)))
                               b_aiIX)))
                   (x_aiIU ((\ x_aiJ1 -> x_aiJ1) b_aiIV)))
             arg1_aiIT)
    • Relevant bindings include
        arg1_aiIT :: forall b. b -> (forall c. a -> c) -> a
          (bound at Bug.hs:8:3)
        value_aiIQ :: T a (bound at Bug.hs:8:3)
        contraMap1_aiIS :: b -> a (bound at Bug.hs:8:3)
        covMap1_aiIR :: a -> b (bound at Bug.hs:8:3)
        invmap :: (a -> b) -> (b -> a) -> T a -> T b (bound at Bug.hs:8:3)
  |
8 | $(deriveInvariant ''T)
  |   ^^^^^^^^^^^^^^^^^^^

GHC has fixed this bug upstream, and it should be possible to apply a similar fix in Data.Functor.Invariant.TH.

Applicative-like invariant

Many invariant functors can be composed as products. Think about an abstraction like Codec a for binary serialisation. To be able to compose a codec of a product value from codecs of its components, such a class will come in handy.

What do you think?

-- |
-- Combination of 'Divisible' and 'Applicative'
-- providing the ability to combine invariant functors.
--
-- The inherited 'Pointed' instance provides
-- the identity operation.
-- Think of it as a comination of 'conquer' and 'pure'.
class (Invariant f, Pointed f) => ProductInvariant f where
  invmapBoth ::
    -- | Dissect contravariantly.
    (c -> (a, b)) ->
    -- | Combine covariantly. 'liftA2'-style.
    (a -> b -> c) ->
    f a ->
    f b ->
    f c

BTW, I am not sure whether this design is correct or optimal yet.

Endo-style profunctor wrapper 

newtype Expo p a = Expo { getExpo :: p a a }

instance Profunctor p => Invariant (Expo p) where
  ...

Is it useful? Dunno. But it seems an obvious thing.

deriveInvariant2 fails due to incorrect role-checking logic

deriveInvariant2 has a special case for data types whose last type parameters have phantom roles, but the logic that checks for this special case is incorrect. Here is an example that demonstrates the issue:

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE TypeFamilies #-}
module Bug where

import Data.Functor.Invariant.TH

data T a b c = MkT c (T a a c)
$(deriveInvariant2 ''T)

This should work, but it fails to compile with the following error message:

[1 of 1] Compiling Bug              ( Bug.hs, interpreted )

Bug.hs:8:3: error:
    • Couldn't match representation of type ‘b’ with that of ‘d’
        arising from a use of ‘GHC.Prim.coerce’
      ‘b’ is a rigid type variable bound by
        the type signature for:
          Data.Functor.Invariant.invmap2 :: forall a1 c b d.
                                            (a1 -> c)
                                            -> (c -> a1)
                                            -> (b -> d)
                                            -> (d -> b)
                                            -> T a a1 b
                                            -> T a c d
        at Bug.hs:8:3-22
      ‘d’ is a rigid type variable bound by
        the type signature for:
          Data.Functor.Invariant.invmap2 :: forall a1 c b d.
                                            (a1 -> c)
                                            -> (c -> a1)
                                            -> (b -> d)
                                            -> (d -> b)
                                            -> T a a1 b
                                            -> T a c d
        at Bug.hs:8:3-22
    • In the first argument of ‘invariant-0.5.3:Data.Functor.Invariant.TH.Internal.invmap2Const’, namely
        ‘(GHC.Prim.coerce value_aiBO)’
      In the expression:
        (((((invariant-0.5.3:Data.Functor.Invariant.TH.Internal.invmap2Const
               (GHC.Prim.coerce value_aiBO))
              covMap1_aiBP)
             contraMap1_aiBR)
            covMap2_aiBQ)
           contraMap2_aiBS)
          value_aiBO
      In the expression:
        \ covMap1_aiBP
          contraMap1_aiBR
          covMap2_aiBQ
          contraMap2_aiBS
          value_aiBO
          -> (((((invariant-0.5.3:Data.Functor.Invariant.TH.Internal.invmap2Const
                    (GHC.Prim.coerce value_aiBO))
                   covMap1_aiBP)
                  contraMap1_aiBR)
                 covMap2_aiBQ)
                contraMap2_aiBS)
               value_aiBO
    • Relevant bindings include
        value_aiBO :: T a a1 b (bound at Bug.hs:8:3)
        contraMap2_aiBS :: d -> b (bound at Bug.hs:8:3)
        covMap2_aiBQ :: b -> d (bound at Bug.hs:8:3)
        invmap2 :: (a1 -> c)
                   -> (c -> a1) -> (b -> d) -> (d -> b) -> T a a1 b -> T a c d
          (bound at Bug.hs:8:3)
  |
8 | $(deriveInvariant2 ''T)
  |   ^^^^^^^^^^^^^^^^^^^^

This line of code is to blame:

invariant-functors/src/Data/Functor/Invariant/TH.hs

Line 348 in d289fc2

(all (== PhantomR) (take numNbs rroles))

Instead of checking if the last two type variables are phantom-roled, it actually checks if the first two type variables are phantom-roled! This shouldn't be difficult to fix, thankfully.

Add more instances

For the sake of thoroughness (and to make this library more useful in the wild), we should defined Invariant and Invariant2 instances for data types in the following packages:

  • array
  • base (there's several data types we missed previously)
  • containers
  • semigroups
  • stm
  • tagged
  • transformers/transformers-compat
  • unordered-containers

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.