Giter Club home page Giter Club logo

adjunctions's Introduction

adjunctions

Hackage Build Status

This package provides adjunctions for Haskell.

Contact Information

Contributions and bug reports are welcome!

Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.

-Edward Kmett

adjunctions's People

Contributors

aaronvargo avatar apsod avatar bgamari avatar bodigrim avatar ekmett avatar ggreif avatar hvr avatar icelandjack avatar juhp avatar ocharles avatar phadej avatar prophile avatar quasicomputational avatar ryanglscott avatar sjoerdvisscher avatar treeowl avatar xcthulhu avatar

Stargazers

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

Watchers

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

adjunctions's Issues

fmap @(Co _) should be fmapRep, not stock derived

Hi (not using the bleeding edge), let's say I have

data Pair a = a :# a

instance Distributive Pair where
 distribute :: Functor f => f (Pair a) -> Pair (f a)
 distribute = distributeRep

instance Representable Pair where
 type Rep Pair = Bool

 index :: Pair a -> (Bool->a)
 index (f:#_) False = f
 index (_:#t) True  = t

 tabulate :: (Bool->a) -> Pair a
 tabulate make = make False :# make True

Let's say I want to derive some instances via Co Pair

data Pair a ..
 deriving (Functor, Applicative, Monad, MonadReader Bool)
 via Co Pair

Spot the mistake?

Because the Functor (Co f) instance is stock derived it's the only instance that doesn't make use of Representable and depends on f being a functor already

-- | Data.Functor.Rep
newtype Co f a = Co { unCo :: f a } deriving Functor

This doesn't trigger an error? Maybe I'm doing it wrong. In any case this means that we trigger a cyclic definition fmap = fmap .

I propose the following definition, which is in line with all other instances

instance Representable f => Functor (Co f) where
 fmap :: (a->a') -> (Co f a->Co f a')
 fmap = fmapRep

New Representable methods feel cramped

We now have

  collect1 :: Functor1 w => (forall x. g x -> f x) -> w g -> f (w Identity)

We can generalize this immediately:

  coll2 :: (Applicative h, Functor1 w) => (forall x. g x -> f x) -> w g -> f (w h)
  coll2 f = cotraverse1 (map1 (pure . runIdentity)) . map1 f

I don't know if it's possible to weaken the Applicative constraint.

Define 'Representable (Join f)' once we have Bicomonad

For future reference, once we have Bicomonad

class Bifunctor bi => Bicomonad bi where
  fst :: bi a b -> a
  snd :: bi a b -> b

  bidup :: bi a b -> (bi a b `bi` bi a b)

I think we can define a Representable instance for (Join f)

instance (Biapplicative f, Bicomonad f) => Representable (Join f) where
  type Rep (Join f) = Bool

  index :: Join f a -> (Bool -> a)
  index (Join faa) = \case
    False -> fst faa
    True  -> snd faa

  tabulate :: (Bool -> a) -> Join f a
  tabulate gen = Join (False `bipure` True)

unless it's unlawful. It captures the pattern of Representable Pair for newtype Pair a = Pair (a, a).

Exploit the (_ *> as = as) property of Representables in Co

Edward says here:

For any Functor that is representable, .. you build a 'zipping' applicative that is isomorphic to reader. For that you can show that (m *> _ = m) and (_ <* m = m). So (<*) and (*>) are O(1) while the (<*>) pays for every point used.

It seems the order he drops things is flipped, in any case I propose we make use of this and define

instance Representable f => Applicative (Co f) where
 ..

 (*>) :: Co f a -> Co f b -> Co f b
 _ *> bs = bs

 (<*) :: Co f a -> Co f b -> Co f a
 as <* _ = as

Isomorphism `f (Rep r)` and `r ~> f`

There is an isomorphism between f (Rep r) and natural transformations r ~> f:

one :: RepresentableOf rep r => Functor f => f rep -> r ~> f
one fins as = index as <$> fins

two :: RepresentableOf rep r => (r ~> f) -> f rep
two make = make positions 

positions :: RepresentableOf rep r => r rep
positions = tabulate id

I don't know that it's useful, but there could be some Iso' (f rep) (r ~> f).

I got the idea of this isomorphism from Cofree Traversable Functors, where it is instantiated at RepresentableOf (Fin n) (Vec n). I'm curious if there is deeper history.

    forall x. x -> .. (n-times) .. x -> f x
  = Vec n ~> f
  = f (Fin n)

Representable (Kleisli r a) given a phantom 'l' argument

Does this instance exist anywhere? F l r a b is Kleisli r a b with a phantom l argument. It was inspired by the "In terms of representable functors" section.

type    F :: (Type -> Type) -> (Type -> Type) -> Type -> (Type -> Type)
newtype F l r a b = F (a -> r b)
  deriving Functor
  via Kleisli r a

instance Adjunction l r => Distributive (F l r a) where
  distribute :: Functor f => f (F l r a b) -> F l r a (f b)
  distribute = distributeRep

instance Adjunction l r => Representable (F l r a) where
 type Rep (F l r a) = l a

 index :: F l r a b -> (l a -> b)
 index (F f) = rightAdjunct f

 tabulate :: (l a -> b) -> F l r a b
 tabulate f = F (leftAdjunct f)

Day instances derived from from Compose

There is an isomorphism between Compose f g and Day f g of representable functors

c2d :: (Representable f, Representable g) => Compose f g a -> Day f g a
c2d = tabulate . index

d2c :: (Representable f, Representable g) => Day f g a -> Compose f g a
d2c = tabulate . index

This means every instance of Compose f g is a potential instance for Day, would these instances be useful and worth adding?

instance (Alternative f, Representable f, Alternative g, Representable g) => Alternative (Day f g) where
  empty :: Day f g a 
  empty  = c2d empty

  (<|>) :: Day f g a -> Day f g a -> Day f g a
  (d2c -> a) <|> (d2c -> b) = c2d (a <|> b)

This allows for an Alternative definition as well as an inordinate number of other instances.


We also get a handful of classes the other way: some instance for Compose f g that work for functors like Coyoneda f, (_ ->), Cofree, Day and recursively Compose (it would be an orphan instance I suppose)

instance (Comonad f, Representable f, Comonad g, Representable g) => Comonad (Compose f g) where
  extract :: Compose f g a -> a
  extract = extract . c2d

  duplicate :: Compose f g a -> Compose f g (Compose f g a)
  duplicate = fmap d2c . d2c . duplicate . c2d 

instance (ComonadApply f, ComonadApply g, Representable g, Representable f) => ComonadApply (Compose f g) where
  (<@>) :: Compose f g (a -> b) -> (Compose f g a -> Compose f g b)
  (c2d -> f) <@> (c2d -> x) = d2c (f <@> x)

Editable representable functors

In general,

ixSureDef   :: (Representable f, Eq (Rep f)) => Rep f -> Lens' (f a) a
ixSureDef i f fa = (\x' -> Rep.tabulate (\k -> if k == i then x' else Rep.index fa k)) <$> f (Rep.index fa i)

Of course, this is horrifically inefficient. Is there a good place here for a subclass supporting such an operation? Alternatively (or additionally), is there room in lens for an IxSure class similar to Ixed but providing a Lens instead of a Traversal?

broken with removing Coproduct from comonad

related commit: ekmett/comonad@f607067

problematic:

instance (Adjunction f g, Adjunction f' g') =>
         Adjunction (Coproduct f f') (Product g g') where
  unit a = Pair (leftAdjunct left a) (leftAdjunct right a)
  counit = coproduct (rightAdjunct fstP) (rightAdjunct sndP)
    where
      fstP (Pair x _) = x
      sndP (Pair _ x) = x

should be somehow replaced with Sum, not sure how

   * Variable not in scope: left :: f a -> Sum f f' a
    * Perhaps you meant one of these:
        data constructor `Left' (imported from Prelude),
        left' (imported from Data.Profunctor)
      Perhaps you want to add `left' to the import list in the import of
      `Control.Arrow' (src\Data\Functor\Adjunction.hs:37:1-35).

Does this exist or belong somewhere?

Is there a home for this class + associated data family?

A common example of data families

class Key key where
  data TotalMap key :: * -> *
  lookup :: key -> TotalMap key val -> val

with some modification

class Functor (TotalMap key) => Key key where
  data TotalMap key :: Type -> Type
  (¡) :: TotalMap key val -> (key -> val)
  tab :: (key -> val) -> TotalMap key val

can form a Representable functor for any instance of Key

instance Key key => Distributive  (TotalMap key) where
  distribute :: Functor f => f (TotalMap key val) -> TotalMap key (f val)
  distribute = distributeRep

instance Key key => Representable (TotalMap key) where
  type Rep (TotalMap key) = key
  index :: TotalMap key val -> (key -> val)
  index = (¡)
  tabulate :: (key -> val) -> TotalMap key val
  tabulate = tab

Since TotalMap key can be made an instance of all these nice classes

instance Key key => Applicative (TotalMap key) where
  pure :: a -> TotalMap key a
  pure = pureRep
  (<*>) :: TotalMap key (a -> b) -> (TotalMap key a -> TotalMap key b)
  (<*>) = apRep

instance Key key => Monad (TotalMap key) where
  return :: a -> TotalMap key a
  return = pureRep
  (>>=) :: TotalMap key a -> (a -> TotalMap key b) -> TotalMap key b
  (>>=) = bindRep

instance Key key => MonadFix (TotalMap key) where
  mfix :: (a -> TotalMap key a) -> TotalMap key a
  mfix = mfixRep

instance (Key key, Monoid key) => Comonad (TotalMap key) where
  extract :: TotalMap key a -> a
  extract = extractRep
  extend :: (TotalMap key a -> b) -> (TotalMap key a -> TotalMap key b)
  extend  = extendRep

instance Key key => MonadReader key (TotalMap key) where
  ask :: TotalMap key key
  ask   = askRep
  local :: (key -> key) -> (TotalMap key a -> TotalMap key a)
  local = localRep

And we can get any of these instances of Key automatically gets us all these nice things

Key key               :- MonadFix        (TotalMap key)
Key key               :- Applicative     (TotalMap key)
Key key               :- Monad           (TotalMap key)
Key key               :- MonadReader key (TotalMap key)
(Key key, Monoid key) :- Comonad         (TotalMap key)
instance Key Bool where
  data TotalMap Bool val = BoolMap val val deriving Functor
  (¡) :: TotalMap Bool val -> (Bool -> val)
  BoolMap f _ ¡ False = f
  BoolMap _ t ¡ True  = t
  tab :: (Bool -> val) -> TotalMap Bool val
  tab f = BoolMap (f False) (f True)

instance (Key key1, Key key2) => Key (key1, key2) where
  data TotalMap (key1, key2) val = PairMap (TotalMap key1 (TotalMap key2 val))
  (¡) :: TotalMap (key1, key2) val -> ((key1, key2) -> val)
  PairMap keys ¡ (k1, k2) = keys ¡ k1 ¡ k2
  tab :: ((key1, key2) -> val) -> TotalMap (key1, key2) val
  tab f = PairMap $
    tab @key1 $ \key1 ->
    tab @key2 $ \key2 ->
    f (key1, key2)
deriving instance (Key key1, Key key2) => Functor (TotalMap (key1, key2))

Update for comonad 4

There doesn't seem to be a version of adjunctions available that advertises itself as working with the new comonad 4.0. Please could you release one? Thanks!

Adjunction f u means f a is isomorphic to (a, Rep u)

There is an explicit isomorphism for this:

fromAdj :: Adjunction f u => f a -> (a, Rep u)
fromAdj = rightAdjunct (tabulate . (,))

toAdj :: Adjunction f u => a -> Rep u -> f a
toAdj = index . unit

And there should be a newtype wrapper, for instance named Adj, that works like Co in Data.Functor.Rep, and provides instances for Comonad, instances for Applicative and Monad when Rep u is a Monoid, etc. Also, there would be an Adjunction between Adj f and Co u, so that Co u has an Adjunction whenever u does.

Add FunctorWithIndex constraint to Representable?

defaultimap ::
  Representable f => (Rep f -> a -> b) -> f a -> f b
defaultimap f fa = tabulate (f <*> index fa)

proves that we can (modulo package issues) use

class (FunctorWithIndex (Rep f) f, Distributive f) => Representable f where ...

The only potential downside (aside from package dep and compatibility issues) is that someone could theoretically use something other than Rep f as the index. This seems a bit unlikely, but not entirely impossible.

As for the packaging, I think it's weird that XxxWithIndex live in lens. Are the lensy defaults really worth tying these simple classes up with the behemoth?

Add withIndex helper function?

Hey there; this is a nicely thought out and very elegant lib!

I've found the following functions useful:

withIndex :: (Eq (Rep f), Representable f) => Rep f -> (a -> a) -> f a -> f a
setIndex :: (Eq (Rep f), Representable f) => Rep f -> a -> f a -> f a

With the relatively inefficient implementations:

withIndex :: (Eq (Rep f), Representable f) => Rep f -> (a -> a) -> f a -> f a
withIndex ind g fa = tabulate $ \rep ->
      let existing = index fa rep
       in if rep == ind then g existing
          else existing

setIndex :: (Eq (Rep f), Representable f) => Rep f -> a -> f a -> f a
setIndex ind = withIndex ind . const

If these would be of interest to others I can write up a PR. Let me know what you think;

Build issues with 7.8.4 and adjunctions 4.3

The latest version of adjunctions (4.3) fails to build for me with the following error:

Preprocessing library adjunctions-4.3...
[ 1 of 11] Compiling Data.Functor.Contravariant.Rep ( src/Data/Functor/Contravariant/Rep.hs, dist/dist-sandbox-fffe542f/build/Data/Functor/Contravariant/Rep.o )
[ 2 of 11] Compiling Control.Monad.Trans.Conts ( src/Control/Monad/Trans/Conts.hs, dist/dist-sandbox-fffe542f/build/Control/Monad/Trans/Conts.o )
[ 3 of 11] Compiling Data.Functor.Contravariant.Adjunction ( src/Data/Functor/Contravariant/Adjunction.hs, dist/dist-sandbox-fffe542f/build/Data/Functor/Contravariant/Adjunction.o )
[ 4 of 11] Compiling Control.Monad.Trans.Contravariant.Adjoint ( src/Control/Monad/Trans/Contravariant/Adjoint.hs, dist/dist-sandbox-fffe542f/build/Control/Monad/Trans/Contravariant/Adjoint.o )
[ 5 of 11] Compiling Data.Functor.Rep ( src/Data/Functor/Rep.hs, dist/dist-sandbox-fffe542f/build/Data/Functor/Rep.o )

src/Data/Functor/Rep.hs:234:10:
    No instance for (Distributive Dual)
      arising from the superclasses of an instance declaration
    In the instance declaration for Representable Dual

src/Data/Functor/Rep.hs:239:10:
    No instance for (Distributive Monoid.Product)
      arising from the superclasses of an instance declaration
    In the instance declaration for Representable Monoid.Product

src/Data/Functor/Rep.hs:244:10:
    No instance for (Distributive Sum)
      arising from the superclasses of an instance declaration
    In the instance declaration for Representable Sum

src/Data/Functor/Rep.hs:250:10:
    No instance for (Distributive Complex)
      arising from the superclasses of an instance declaration
    In the instance declaration for Representable Complex

The previous version 4.2.2 doesn't have this issue, locking to 4.2.2 in the cabal file works. Using 7.8.4 with base-4.7.0.2.

It appears that the lines it's complaining about were recently added. I'm not very familiar with this package but perhaps it's expecting newer versions of these classes than what I've got.
Diff between v4.2.2 and v4.3

Add instance for WrappedMonad

Whenever ekmett/distributive#52 lands, we can and presumably should add

instance (Representable m, Monad m) => Representable (WrappedMonad m) where
  type Rep (WrappedMonad m) = Rep m
  index (WrapMonad m) k = index m k
  tabulate f = WrapMonad (tabulate f)

instance Representable f => Representable (Reverse f)?

Is there a valid Representable instance for Reverse?

instance Representable f => Representable (Reverse f) where
  type Rep (Reverse f) = Rep f
  tabulate = Reverse . tabulate
  index (Reverse f) i = index f i

gives the same result for these two expressions

>>> (!) = index; infixl 6 ! 
>>> V3 'x' 'y' 'z' ! E _x
'x'
>>> Reverse (V3 'x' 'y' 'z') ! E _x
'x'

representable-functors package

I'm confused on why there is a Representable class in both representable-functors and adjunctions. Does the version here supersede the version in representable-functors? If yes, can the documentation in both packages be updated to reflect that?

Newtype to specify Rep: deriving Representable via Pair `ShapedBy` Bool

The generic Rep definition is too robotic, if I derive Representable Count I most likely don't want to index by Rep Count = Either () (Either () ()) but by something like data Move = Rock | Paper | Scissors!

data Count a = Count
  { rock     :: a
  , paper    :: a
  , scissors :: a
  }
  deriving stock (Functor, Generic1)
  deriving anyclass Distributive  -- dummy
  deriving anyclass Representable -- Rep Count = () `Either` () `Either` ()

I have implemented a via type that allows us to derive Representable with a specified Rep:

-- >> index (Count 1 2 3) Rock
-- 1
-- >> index (Count 1 2 3) Paper
-- 2
-- >> index (Count 1 2 3) Scissors
-- 3
data Count a = Count ..
  deriving stock (Functor, Generically1)
  deriving anyclass Distributive -- dummy

  deriving Representable via Count `ShapedBy` Move -- Rep Count = Move

data Move = Rock | Paper | Scissors deriving stock Generic
-- >> (pi :# 10) `index` False
-- 3.141592653589793
-- >> (pi :# 10) `index` True
-- 10.0
--
-- >> tabulate @Pair id
-- False :# True
data Pair a = a :# a
  deriving stock (Show, Functor, Generic1)
  deriving anyclass Distributive -- dummy

  deriving Representable via Pair `ShapedBy` Bool -- Rep Pair = Bool
{-# Language BlockArguments           #-}
{-# Language FlexibleContexts         #-}
{-# Language ImportQualifiedPost      #-}
{-# Language InstanceSigs             #-}
{-# Language PolyKinds                #-}
{-# Language RankNTypes               #-}
{-# Language ScopedTypeVariables      #-}
{-# Language StandaloneKindSignatures #-}
{-# Language TypeApplications         #-}
{-# Language TypeFamilies             #-}
{-# Language TypeOperators            #-}
{-# Language UndecidableInstances     #-}

import Data.Coerce
import Data.Distributive
import Data.Functor.Rep hiding (gtabulate, gindex)
import Data.Kind
import GHC.Generics hiding (Rep)
import GHC.Generics qualified as GHC

type    ShapedBy :: (k -> Type) -> argument -> (k -> Type)
newtype ShapedBy f arg a = ShapedBy (f a)

instance (Coercible (GHC.Rep rep ()) (RepToRep f), Generic1 f, Generic rep, GTabulate (Rep1 f), GIndex (Rep1 f)) => Functor (ShapedBy f rep) where
  fmap = fmapRep

instance (Coercible (GHC.Rep rep ()) (RepToRep f), Generic1 f, Generic rep, GTabulate (Rep1 f), GIndex (Rep1 f)) => Distributive (ShapedBy f rep) where
  distribute = distributeRep
  collect = collectRep

instance (Coercible (GHC.Rep rep ()) (RepToRep f), Generic1 f, Generic rep, GTabulate (Rep1 f), GIndex (Rep1 f)) => Representable (ShapedBy f rep) where
  type Rep (ShapedBy f rep) = rep
  index :: ShapedBy f rep a -> (rep -> a)
  index (ShapedBy as) = gindex as . roundtrip where

   roundtrip :: rep -> RepToRep f
   roundtrip = coerce . GHC.from @rep @()

  tabulate :: forall a. (rep -> a) -> ShapedBy f rep a
  tabulate make = ShapedBy $ gtabulate (make . roundtrip) where

   roundtrip :: RepToRep f -> rep
   roundtrip = GHC.to @rep @() . coerce

this uses the GRep' machinary from adjunctions except RepToRep' takes a generic representation and returns another generic representation.

type RepToRep :: (Type -> Type) -> Type
type RepToRep f = RepToRep' (Rep1 f) ()

gtabulate :: Generic1 f => GTabulate (Rep1 f) => (RepToRep f -> a) -> f a
gtabulate = to1 . gtabulate'

gindex :: Generic1 f => GIndex (Rep1 f) => f a -> RepToRep f -> a
gindex = gindex' . from1

type
  RepToRep' :: (Type -> Type) -> (Type -> Type)
type family
  RepToRep' rep
class GTabulate rep where
  gtabulate' :: (RepToRep' rep () -> a) -> rep a
class GIndex rep where
  gindex' :: rep a -> (RepToRep' rep () -> a)

type instance
  RepToRep' Par1 = U1
instance GTabulate Par1 where
  gtabulate' :: (U1 () -> a) -> Par1 a
  gtabulate' f = Par1 (f U1)
instance GIndex Par1 where
  gindex' :: Par1 a -> (U1 () -> a)
  gindex' (Par1 a) U1 = a

type instance
  RepToRep' (rep1 :*: rep2) = RepToRep' rep1 :+: RepToRep' rep2
instance (GTabulate rep1, GTabulate rep2) => GTabulate (rep1 :*: rep2) where
  gtabulate' :: ((RepToRep' rep1 :+: RepToRep' rep2) () -> a) -> (rep1 :*: rep2) a
  gtabulate' f = gtabulate' (f . L1) :*: gtabulate' (f . R1)
instance (GIndex rep1, GIndex rep2) => GIndex (rep1 :*: rep2) where
  gindex' :: (rep1 :*: rep2) a -> ((RepToRep' rep1 :+: RepToRep' rep2) () -> a)
  gindex' (a :*: _) (L1 i) = gindex' a i
  gindex' (_ :*: b) (R1 j) = gindex' b j

type instance
  RepToRep' (Rec1 f) = Rec0 (WrappedRep f)
instance Representable f => GTabulate (Rec1 f) where
  gtabulate' :: forall a. (Rec0 (WrappedRep f) () -> a) -> Rec1 f a
  gtabulate' = coerce do
    tabulate @f @a
instance Representable f => GIndex (Rec1 f) where
  gindex' :: forall a. Rec1 f a -> (Rec0 (WrappedRep f) () -> a)
  gindex' = coerce do
    index @f @a

type instance
  RepToRep' (M1 i c rep) = RepToRep' rep
instance GTabulate rep => GTabulate (M1 i c rep) where
  gtabulate' :: (RepToRep' rep () -> a) -> M1 i c rep a
  gtabulate' = M1 . gtabulate'
instance GIndex rep => GIndex (M1 i c rep) where
  gindex' :: M1 i c rep a -> (RepToRep' rep () -> a)
  gindex' = gindex' . unM1

type instance
  RepToRep' (f :.: rep) = Rec0 (WrappedRep f) :*: RepToRep' rep
instance (Representable f, GTabulate rep) => GTabulate (f :.: rep) where
  gtabulate' :: forall a. ((Rec0 (WrappedRep f) :*: RepToRep' rep) () -> a) -> (f :.: rep) a
  gtabulate' make = Comp1 do tabulate (gtabulate' <$> f) where
     f :: Rep f -> RepToRep' rep () -> a
     f a b = make (K1 (WrapRep a) :*: b)
instance (Representable f, GIndex rep) => GIndex (f :.: rep) where
  gindex' :: (f :.: rep) a -> ((Rec0 (WrappedRep f) :*: RepToRep' rep) () -> a)
  gindex' (Comp1 reps) (K1 (WrapRep a) :*: b) = gindex' (index reps a) b

Use lens Iso in Data.Functor.Rep

Hi Edward,

I notice that the Representable class define an isomorphism (between the functor and its representation), but that you avoid defining it in terms if lens's Iso. Is there a reason for this?

I have been using the following in my own code but I would rather it was in an official package.

import Control.Lens
import Data.Functor.Rep

tabulated :: Representable f => Iso (Rep f -> a) (Rep f -> b) (f a) (f b)
tabulated = iso tabulate index

List vs. Seq for Rep Cofree

The index for Cofree is currently Seq from Data.Sequence:

instance Representable f => Representable (Cofree f) where
type Rep (Cofree f) = Seq (Rep f)
index (a :< as) key = case Seq.viewl key of
Seq.EmptyL -> a
k Seq.:< ks -> index (index as k) ks
tabulate f = f Seq.empty :< tabulate (\k -> tabulate (f . (k Seq.<|)))

But it looks like the sequence is only ever accessed with consing and unconsing. If so, would it be possible to change the implementation to use lists instead? Maybe something like:

instance Representable f => Representable (Cofree f) where
  type Rep (Cofree f) = [Rep f]
  index = flip (foldr f extract) where
    f x xs ys = xs (index (unwrap ys) x)
  tabulate = coiterW (\f -> tabulate (\x -> f . (:) x))

tabulate could alternatively be:

tabulate = unfold (\f -> (f [], tabulate (\x -> f . (:) x)))
-- Or
tabulate = coiterW (collect (flip (.)) (tabulate (:)))

The extra flexibility and lower overhead of lists would be handy, and I haven't seen any of the extra features of sequences being used with this instance.

indexM in Representable?

There should be a function called something like indexM in the Representable typeclass, with the type

indexM :: (Representable f, Monad m) => f a -> Rep f -> m a

Its default definition would simply be

indexM f k = return $ index f k

But for some Representables, it could produce a more defined result, for the same reasons as in Data.Vector. An example for Product:

indexM (Pair a _) (Left i) = indexM a i
indexM (Pair _ b) (Right j) = indexM b j

The result passed to return contains no reference to the original Product value. This could be a win for people using Representables for memoization.

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.