为n维网格类型编写联合或cobind [英] Writing cojoin or cobind for n-dimensional grid type

问题描述

  { - ＃语言KindSignatures＃ - } 
 { - ＃LANGUAGE DataKinds＃ - } 
 { - ＃LANGUAGE GADTs＃ - } 
 { - ＃LANGUAGE TypeFamilies＃ - } 
 
 data Nat = Z | S Nat 
 
 data U（n :: Nat）x其中
 Point :: x  - > U Z x 
维度:: [U n x]  - > U n x  - > [U n x]  - > U（S n）x 
 
 dmap ::（U n x  - > U m r） - > U（S n）x  - > U（S m）r 
 dmap f（Dimension ls mid rs）= Dimension（map f ls）（f mid）（map f rs）
 
实例Functor（U n）where 
 fmap f（Point x）= Point（fx）
 fmap fd @ Dimension {} = dmap（fmap f）d 
  

现在我想让它成为Comonad的一个实例，但我不能完全包围它。

  class Functor w => Comonad w其中
（=>>）:: w a  - > （w a  - > b） - > w b 
 coreturn :: w a  - > a 
 cojoin :: w a  - > w（w a）
 
 x =>> f = fmap f（cojoin x）
 cojoin xx = xx =>> id 
 
实例Comonad（U n）其中
 coreturn（Point x）= x 
 coreturn（Dimension _ mid _）= coreturn mid 
 
  -  -  cojoin :: UZ x  - > U Z（U Z x）
 cojoin（Point x）= Point（Point x）
  -  cojoin :: U（S n）x  - > U（S n）（U（S n）x）
联合d @维{} =未定义
 
  -  =>> :: U Z x  - > （U Z x→r）→> U Z r 
 p @ Point {} =>> f = Point（f p）
  -  =>>> :: U（S n）x  - > （U（S n）x→r）→> U（S n）r 
 d @ Dimension {} =>> f = undefined 
  

在n上使用 cojoin 维网格将产生n维网格的n维网格。我想提供一个与这一个相同的想法的实例，它的值< （x，y，z）上的 cojoined 网格应该是（x，y，z）上的原始网格 。为了适应这些代码，看起来我们需要通过 n 来执行 n fmaps和 n 卷。你不必这样做，但如果这有帮助，那么你就去。

Richards：你不能总是得到你想要的东西，但是如果你尝试某个时候，你可能会发现你得到了你所需要的东西。

列表中的游标

让我使用snoc和cons列表重建您的结构组件，以保持空间属性清晰。我定义了

  data Bwd x = B0 | Bwd x：< x派生（Functor，Foldable，Traversable，Show）
数据Fwd x = F0 | x：> Fwd x派生（Functor，Foldable，Traversable，Show）
 infixl 5：< 
 infixr 5：> 
 
 data Cursor x = Cur（Bwd x）x（Fwd x）派生（Functor，Foldable，Traversable，Show）
  

让我们有comonads

  class Functor f => Comonad f where 
 counit :: f x  - > x 
 cojoin :: f x  - > f（fx）
  

让我们确保游标是连接符

  instance Comonad Cursor其中
 counit（Cur _ x _）= x 
 cojoin c = Cur（lefts c）c（rights c）where $ （Cur（xz：< x）yys）=左c：< b左b其中c = Cur xz x（y：> ys）
 rights（Cur __ F0）= F0 
 rights（Cur xz x（y：> ys））= c：>权利c其中c = Cur（xz：< x）y ys 
  

如果您已开启到这种东西，你会注意到 Cursor 是一个空间愉悦的变体 InContext []

  InContext fx =（x，∂fx）
  

其中∂取一个函数的形式导数，给出它的单孔上下文的概念。 InContext f 总是一个 Comonad ，如这个答案，我们在这里只是由差分结构引发的 Comonad ，其中 counit 提取焦点处的元素， cojoin 用各自的上下文装饰每个元素，实际上为您提供了一个充满重新聚焦的游标和未移动游标的上下文其重点。让我们来举个例子。

 > （B 0：< 1）2（3：> 4：> F 0））
 Cur（B 0：< Cur B 01（2：> 3：> 4：> F 0 ））
（Cur（B0：< 1：2）3（4：>）（b0：<1）2（3：> 4：> F0） ; F0）
：> Cur（B0：<1：<2：<3）4 F0 
：> F0）
  pre> 
 
 
请参阅？焦点2已被装饰成为光标在2;在左边，我们有光标在1的列表;在右侧，光标在-3和光标在-4的列表。
 
 
 
编写游标，转置游标？
 
 
 
现在，您要求的结构是 Comonad 是 Cursor 。让我们来看看
 
 pre $  newtype（：。:) fgx = C {unC :: f（gx）}派生Show 
  

说服comonads f 和 g 编写， counit 构成整齐，但您需要一个分配法则



  transpose :: f（gx） - > g（fx）
  

因此您可以使组合联合
$ f $ g $ $ b $（fmap cojoin） - >
f（g（g x））
-cojoin->
f（f（g（g x）））
- （fmap transpose） - >
f（g（f（gx）））


>转置满足？可能类似于



  counit。 transpose = fmap counit 
联合。转置= fmap转置。转置。 fmap联合
  

或者其他任何方法来确保有两种方式可以让f和g的某些序列从



我们可以为 Cursor定义一个转置 与自己？便宜地进行某种换位的一种方法是注意 Bwd 和 Fwd 是 zippily applicative，因此也是游标。

 实例Applicative Bwd其中
纯x =纯x：< x 
（fz：< f）< *> （sz：< s）=（fz * sz）：< f s 
 _< *> _ = B0 
 
实例应用程序转发其中
 pure x = x：>纯x 
（f：> fs）* （s：> ss）= f s：> （fs * ss）
 _ * _ = F0 
 
实例应用游标其中
 pure x = Cur（纯x）x（纯x）
 Cur fz f fs * Cur sz s ss = Cur（fz * sz）（fs）（fs * ss）
  

在这里你应该开始闻到老鼠。形状不匹配会导致截断，并且这将打破自转换为自反转的显然理想的属性。任何一种破烂都无法生存。我们确实得到了一个转位运算符： sequenceA ，对于完全正常的数据，所有的都是明亮而美丽的。



 > （B0：< 4）5（6：> F0））的正常矩阵游标
 Cur（B0： F0））
 
（Cur（B0：<7）8（9：> F0）：> F0）
> （B0：< Cur（B0：< 1）4（7：> F0））
（Cur（B0：< 2）5（8：> F0） ）
（Cur（B0：< 3）6（9：> F0）：> F0）
  

但是，即使我只是将一个内部游标移动到不对齐的位置（不必介意使尺寸变得不一致），情况就会出错。



 > raggedyMatrixCursor 
 Cur（B0：（Cur（B0：< 4）5（6：> F0）） 
（Cur（B0：<7）8（9：> F0）：> F0）
> （B0：< Cur（B0：2）4（7：> F0））
（Cur（B0：< 3）5（8：> F0） ）
 F0 
  

当您有一个外部光标位置和多个内部光标位置时，换位表现良好。自我组合 Cursor 允许内部结构相对于彼此不成立，所以没有转置，no cojoin 。您可以，也可以定义



 实例（Comonad f，Traversable f，Comonad g，Applicative g）=> 
 Comonad（f：。：g）其中
 counit = counit。议会。 unC 
 cojoin = C。 fmap（fmap C。sequenceA）。联合。 fmap联合。 unC 
  

但我们有责任确保内部结构保持规则。如果您愿意接受这种负担，那么您可以迭代，因为 和 Traversable 很容易在构图下关闭。这里有一些小部件：



  instance（Functor f，Functor g）=> Functor（f：。：g）其中
 fmap h（C fgx）= C（fmap（fmap h）fgx）
 
实例（Applicative f，Applicative g）=>应用（f：。：g）其中
 pure = C。纯粹。纯
 C f * C s = C（纯（*）* f * s）
 
实例（Functor f，Foldable f，Foldable g）=>可折叠（f：。：g）其中
折叠=折叠。 fmap折叠。 unC 
 
实例（Traversable f，Traversable g）=>可穿越（f：。：g）其中
遍历h（C fgx）= C< $>遍历（遍历h）fgx 
  

编辑：当所有的都是正常的时候，



 > （C：正常矩阵光标）
 C {unC = Cur（B0：< Cur（B0：< 
 C {unC = Cur B0（Cur B0 1（2：>（3：> F0 ）））（CurB0 4（5：>（6：> F0））：>（CurB07（8：>（9：> F0））：> F0））}）$ b （Cur（B0：<1）2（3：> F0））（Cur（B0：<4）5（6:> F0）：>（Cur B0：< 7）8（9：> F0）：> F0））}）
（C {unC = CurB0（Cur（（B0：< 1）：< 2） ）（Cur（（B0：<4）：<5）6F0：>（Cur（（B0：<7）：<8）9F0：> F0））}：> F0） ）（b 0：（C {unC = Cur（B 0： Cur（B 0：<4）5（6：> F 0））（Cur（B 0：< 7）8（9：> F0）：> F0）}）
（C {unC = Cur（B0： F0）}：> F0））
（Cur（B0：< b $ b C {unC = Cur（（B0：< Cur B0 1（2：>（3：> F0）））：< （B 0（8：>（9：> F 0）））F 0}）
（C {unC = Cur（（ B0：< Cur（B0：< 4）5（6：> F0））（Cur（B0：< 7） 8（9：> F0））F0}）
（C {unC = Cur（（B0：：> F0）} 
  





汉考克的张量积

为了规律，你需要比构图更强的东西。您需要能够捕捉到g-结构的f-结构 - 所有 - 相同形状的概念。这就是不可估量的Peter Hancock所称的张量积，我将写出 f：><：g ：有一个外f形和所有内部g结构都有一个内部g形，所以换位很容易定义，并且总是自反。 Hancock的张量在Haskell中并不方便定义，但在一个依赖类型的设置中，很容易形成具有这个张量的容器的概念。为了给你提供想法，考虑容器的退化概念

  data（：<|）spx = s：< | （p  - > x）
  

其中我们说 s 是形状的类型， p 是职位的类型。一个值包含形状的选择和每个位置的 x 的存储。在相关情况下，位置的类型可能取决于形状的选择（例如，对于列表，形状是一个数字（长度），并且您有多个位置）。这些容器具有张量积b
$ b

 （s：< | p）：>< ;:（s'：< | p'）=（s，s'）：< | （p，p'）
  

这就像一个广义矩阵：一对形状给出了尺寸，然后你在每一对位置都有一个元素。当类型 p 和 p'取决于 s 和 s'，这正是汉考克对容器张量积的定义。

Incontext for Tensor Products

现在，正如您在高中时所了解的那样，∂（s：<| p）=（s， p）：< | （p-1）其中 p-1 是某种类型，其元素少于 p 。像∂（s x x ^ p）=（s p p）* x ^（p-1）。您选择一个位置（将其记录在形状中）并将其删除。这个障碍是 p-1 在没有依赖类型的情况下很难实现。但是 InContext 在不删除它的情况下选择一个位置 。

  InContext（s：< | p）〜=（s，p）：< | p 
  

对于相关情况，这同样适用，我们很高兴地获得了

  InContext（f：><：g）〜= InContext f：><：InContext g 
  InContext f 总是一个 Comonad  / code>，这告诉我们， InContext 的张量产品是共性的，因为它们本身就是 InContext 秒。也就是说，你在每个维度选择一个位置（并且在整个事物中恰好给出了一个位置），在这之前我们有一个外部位置和许多内部位置。用张量产品代替组合物，一切都很好。 
 
 
 Naperian Functors 
 
 
 
但是有一个子类 Functor ，其张量积和构图一致。这些是 Functor  s  f ，其中 f（）〜（）：也就是说，无论如何只有一种形状，所以首先排除组合中的破碎的值。这些 Functor  s对于某些位置集 p同构于（p  - >） 我们可以把它看作 logarithm （必须将 x >的指数赋予给 FX ）。相应地，汉考克在John Napier（他的鬼魂出没在Hancock住的爱丁堡的一部分）之后称这些 Naperian  functor。 
 
 
  class Applicative f => Naperian f where 
 type Log f 
 project :: f x  - >记录f  - > x 
仓位:: f（Log f）
 ---项目仓位= id 
  
 
 
一个 Naperian  functor具有一个对数，它将一个项目离子函数映射位置映射到在那里找到的元素。  Naperian 函数都是zippily  Applicative ，其中纯和 *> 对应于投影的K和S组合器。也可以构建一个值，在每个位置存储该位置的表示。 
  newtype Id x = Id {unId :: x}派生Show 
 
实例Naperian Id其中
类型Log Id =（）
项目（Id x）（）= x 
职位= Id（）
 
 newtype（：* :) fgx = Pr（fx，gx）导出显示
 
实例（Naperian f，Naperian g）=> Naperian（f：*：g）其中
类型Log（f：*：g）=（Log f）（Log g）
项目（Pr（fx，gx））（Left p）=项目fx p 
项目（Pr（fx，gx））（Right p）=项目gx p 
仓位= Pr（fmap左仓位，fmap右仓位）
  
请注意，固定大小的数组（ vector ）由（Id：*： Id：*：...：*：Id：*：One），其中 One 是常量单位仿函数，其对数为空隙。所以一个数组是 Naperian 。现在，我们也有 
 
 
 实例（Naperian f，Naperian g）=> Naperian（f：。：g）其中
类型Log（f：。：g）=（Log f，Log g）
项目（C fgx）（p，q）=项目（项目fgx p ）
仓位= C $ fmap（\ p  - > fmap（p，仓位）仓位
  
这意味着多维数组是 Naperian 。
 
 
 
要构造一个 InContext f  for  Naperian f ，只需指向一个位置即可！
  data focused fx = fx：@ Log f 
 
实例Functor f => Functor（Focused f）其中
 fmap h（fx：@ p）= fmap h fx：@ p 
 
实例Naperian f => Comonad（focused f）其中
 counit（fx：@ p）= project fx p 
 cojoin（fx：@ p）= fmap（fx：@）职位：@ p 
  Focused  n维数组确实会是一个数组c code $> 
 $ b $> comonad。向量的组合是n个向量的张量积，因为向量是 Naperian 。但是 Focused  n维数组将是n  Focused的n倍张量积，而不是组合确定其尺寸的矢量>。为了用拉链表达这个共同点，我们需要用一种能够构造张量产品的形式来表达它们。我将把它作为未来的练习。
 
Using the typical definition of type-level naturals, I've defined an n-dimensional grid.
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeFamilies #-}

data Nat = Z | S Nat

data U (n :: Nat) x where
  Point :: x -> U Z x
  Dimension :: [U n x] -> U n x -> [U n x] -> U (S n) x

dmap :: (U n x -> U m r) -> U (S n) x -> U (S m) r
dmap f (Dimension ls mid rs) = Dimension (map f ls) (f mid) (map f rs)

instance Functor (U n) where
  fmap f (Point x) = Point (f x)
  fmap f d@Dimension{} = dmap (fmap f) d
Now I want to make it an instance of Comonad, but I can't quite wrap my brain around it.
class Functor w => Comonad w where
  (=>>)    :: w a -> (w a -> b) -> w b
  coreturn :: w a -> a
  cojoin   :: w a -> w (w a)

  x =>> f = fmap f (cojoin x)
  cojoin xx = xx =>> id

instance Comonad (U n) where
  coreturn (Point x) = x
  coreturn (Dimension _ mid _) = coreturn mid

  -- cojoin :: U Z x -> U Z (U Z x)
  cojoin (Point x) = Point (Point x)
  -- cojoin ::U (S n) x -> U (S n) (U (S n) x)
  cojoin d@Dimension{} = undefined

  -- =>> :: U Z x -> (U Z x -> r) -> U Z r
  p@Point{} =>> f = Point (f p)
  -- =>> :: U (S n) x -> (U (S n) x -> r) -> U (S n) r
  d@Dimension{} =>> f = undefined
Using cojoin on an n-dimensional grid will produce an n-dimensional grid of n-dimensional grids. I'd like to provide an instance with the same idea as this one, which is that the value of the cojoined grid at (x,y,z) should be the original grid focused on (x,y,z). To adapt that code, it appears that we need to reify n in order to perform n "fmaps" and n "rolls". You don't have to do it that way but if that helps, then there you go.
解决方案
Jagger/Richards: you can't always get what you want, but if you try sometime you just might find that you get what you need.

Cursors in Lists

Let me rebuild the components of your structure using snoc- and cons-lists to keep the spatial properties clear. I define
data Bwd x = B0 | Bwd x :< x deriving (Functor, Foldable, Traversable, Show)
data Fwd x = F0 | x :> Fwd x deriving (Functor, Foldable, Traversable, Show)
infixl 5 :<
infixr 5 :>

data Cursor x = Cur (Bwd x) x (Fwd x) deriving (Functor, Foldable, Traversable, Show)
Let's have comonads
class Functor f => Comonad f where
  counit  :: f x -> x
  cojoin  :: f x -> f (f x)
and let's make sure cursors are comonads
instance Comonad Cursor where
  counit (Cur _ x _) = x
  cojoin c = Cur (lefts c) c (rights c) where
    lefts (Cur B0 _ _) = B0
    lefts (Cur (xz :< x) y ys) = lefts c :< c where c = Cur xz x (y :> ys)
    rights (Cur _ _ F0) = F0
    rights (Cur xz x (y :> ys)) = c :> rights c where c = Cur (xz :< x) y ys
If you're turned on to this kind of stuff, you'll note that Cursor is a spatially pleasing variant of InContext []
InContext f x = (x, ∂f x)
where ∂ takes the formal derivative of a functor, giving its notion of one-hole context. InContext f is always a Comonad, as mentioned in this answer, and what we have here is just that Comonad induced by the differential structure, where counit extracts the element at the focus and cojoin decorates each element with its own context, effectively giving you a context full of refocused cursors and with an unmoved cursor at its focus. Let's have an example.
> cojoin (Cur (B0 :< 1) 2 (3 :> 4 :> F0))
Cur (B0 :< Cur B0 1 (2 :> 3 :> 4 :> F0))
    (Cur (B0 :< 1) 2 (3 :> 4 :> F0))
    (  Cur (B0 :< 1 :< 2) 3 (4 :> F0)
    :> Cur (B0 :< 1 :< 2 :< 3) 4 F0
    :> F0)
See? The 2 in focus has been decorated to become the cursor-at-2; to the left, we have the list of the cursor-at-1; to the right, the list of the cursor-at-3 and the cursor-at-4.

Composing Cursors, Transposing Cursors?

Now, the structure you're asking to be a Comonad is the n-fold composition of Cursor. Let's have
newtype (:.:) f g x = C {unC :: f (g x)} deriving Show
To persuade comonads f and g to compose, the counits compose neatly, but you need a "distributive law"
transpose :: f (g x) -> g (f x)
so you can make the composite cojoin like this
f (g x)
  -(fmap cojoin)->
f (g (g x))
  -cojoin->
f (f (g (g x)))
  -(fmap transpose)->
f (g (f (g x)))
What laws should transpose satisfy? Probably something like
counit . transpose = fmap counit
cojoin . transpose = fmap transpose . transpose . fmap cojoin
or whatever it takes to ensure that any two ways to shoogle some sequence of f's and g's from one order to another give the same result.

Can we define a transpose for Cursor with itself? One way to get some sort of transposition cheaply is to note that Bwd and Fwd are zippily applicative, hence so is Cursor.
instance Applicative Bwd where
  pure x = pure x :< x
  (fz :< f) <*> (sz :< s) = (fz <*> sz) :< f s
  _ <*> _ = B0

instance Applicative Fwd where
  pure x = x :> pure x
  (f :> fs) <*> (s :> ss) = f s :> (fs <*> ss)
  _ <*> _ = F0

instance Applicative Cursor where
  pure x = Cur (pure x) x (pure x)
  Cur fz f fs <*> Cur sz s ss = Cur (fz <*> sz) (f s) (fs <*> ss)
And here you should begin to smell the rat. Shape mismatch results in truncation, and that's going to break the obviously desirable property that self-transpose is self-inverse. Any kind of raggedness will not survive. We do get a transposition operator: sequenceA, and for completely regular data, all is bright and beautiful.
> regularMatrixCursor
Cur (B0 :< Cur (B0 :< 1) 2 (3 :> F0))
          (Cur (B0 :< 4) 5 (6 :> F0))
          (Cur (B0 :< 7) 8 (9 :> F0) :> F0)
> sequenceA regularMatrixCursor
Cur (B0 :< Cur (B0 :< 1) 4 (7 :> F0))
          (Cur (B0 :< 2) 5 (8 :> F0))
          (Cur (B0 :< 3) 6 (9 :> F0) :> F0)
But even if I just move one of the inner cursors out of alignment (never mind making the sizes ragged), things go awry.
> raggedyMatrixCursor
Cur (B0 :< Cur ((B0 :< 1) :< 2) 3 F0)
          (Cur (B0 :< 4) 5 (6 :> F0))
          (Cur (B0 :< 7) 8 (9 :> F0) :> F0)
> sequenceA raggedyMatrixCursor
Cur (B0 :< Cur (B0 :< 2) 4 (7 :> F0))
          (Cur (B0 :< 3) 5 (8 :> F0))
          F0
When you have one outer cursor position and multiple inner cursor positions, there's no transposition which is going to behave well. Self-composing Cursor allows the inner structures to be ragged relative to one another, so no transpose, no cojoin. You can, and I did, define
instance (Comonad f, Traversable f, Comonad g, Applicative g) =>
  Comonad (f :.: g) where
    counit = counit . counit . unC
    cojoin = C . fmap (fmap C . sequenceA) . cojoin . fmap cojoin . unC
but it's an onus on us to make sure we keep the inner structures regular. If you're willing to accept that burden, then you can iterate, because Applicative and Traversable are readily closed under composition. Here are the bits and pieces
instance (Functor f, Functor g) => Functor (f :.: g) where
  fmap h (C fgx) = C (fmap (fmap h) fgx)

instance (Applicative f, Applicative g) => Applicative (f :.: g) where
  pure = C . pure . pure
  C f <*> C s = C (pure (<*>) <*> f <*> s)

instance (Functor f, Foldable f, Foldable g) => Foldable (f :.: g) where
  fold = fold . fmap fold . unC

instance (Traversable f, Traversable g) => Traversable (f :.: g) where
  traverse h (C fgx) = C <$> traverse (traverse h) fgx
Edit: for completeness, here's what it does when all is regular,
> cojoin (C regularMatrixCursor)
C {unC = Cur (B0 :< Cur (B0 :<
  C {unC = Cur B0 (Cur B0 1 (2 :> (3 :> F0))) (Cur B0 4 (5 :> (6 :> F0)) :> (Cur B0 7 (8 :> (9 :> F0)) :> F0))}) 
 (C {unC = Cur B0 (Cur (B0 :< 1) 2 (3 :> F0)) (Cur (B0 :< 4) 5 (6 :> F0) :> (Cur (B0 :< 7) 8 (9 :> F0) :> F0))})
 (C {unC = Cur B0 (Cur ((B0 :< 1) :< 2) 3 F0) (Cur ((B0 :< 4) :< 5) 6 F0 :> (Cur ((B0 :< 7) :< 8) 9 F0 :> F0))} :> F0))
(Cur (B0 :<
  C {unC = Cur (B0 :< Cur B0 1 (2 :> (3 :> F0))) (Cur B0 4 (5 :> (6 :> F0))) (Cur B0 7 (8 :> (9 :> F0)) :> F0)})
 (C {unC = Cur (B0 :< Cur (B0 :< 1) 2 (3 :> F0)) (Cur (B0 :< 4) 5 (6 :> F0)) (Cur (B0 :< 7) 8 (9 :> F0) :> F0)}) 
 (C {unC = Cur (B0 :< Cur ((B0 :< 1) :< 2) 3 F0) (Cur ((B0 :< 4) :< 5) 6 F0) (Cur ((B0 :< 7) :< 8) 9 F0 :> F0)} :> F0))
(Cur (B0 :<
  C {unC = Cur ((B0 :< Cur B0 1 (2 :> (3 :> F0))) :< Cur B0 4 (5 :> (6 :> F0))) (Cur B0 7 (8 :> (9 :> F0))) F0})
 (C {unC = Cur ((B0 :< Cur (B0 :< 1) 2 (3 :> F0)) :< Cur (B0 :< 4) 5 (6 :> F0)) (Cur (B0 :< 7) 8 (9 :> F0)) F0})
 (C {unC = Cur ((B0 :< Cur ((B0 :< 1) :< 2) 3 F0) :< Cur ((B0 :< 4) :< 5) 6 F0) (Cur ((B0 :< 7) :< 8) 9 F0) F0} :> F0)
:> F0)}


Hancock's Tensor Product

For regularity, you need something stronger than composition. You need to be able to capture the notion of "an f-structure of g-structures-all-the-same-shape". This is what the inestimable Peter Hancock calls the "tensor product", which I'll write f :><: g: there's one "outer" f-shape and one "inner" g-shape common to all the inner g-structures, so transposition is readily definable and always self-inverse. Hancock's tensor is not conveniently definable in Haskell, but in a dependently typed setting, it's easy to formulate a notion of "container" which has this tensor.

To give you the idea, consider a degenerate notion of container
data (:<|) s p x = s :<| (p -> x)
where we say s is the type of "shapes" and p the type of "positions". A value consists of the choice of a shape and the storage of an x in each position. In the dependent case, the type of positions may depend on the choice of the shape (e.g., for lists, the shape is a number (the length), and you have that many positions). These containers have a tensor product
(s :<| p) :><: (s' :<| p')  =  (s, s') :<| (p, p')
which is like a generalised matrix: a pair of shapes give the dimensions, and then you have an element at each pair of positions. You can do this perfectly well when types p and p' depend on values in s and s', and that is exactly Hancock's definition of the tensor product of containers.

InContext for Tensor Products

Now, as you may have learned in high school, ∂(s :<| p) = (s, p) :<| (p-1) where p-1 is some type with one fewer element than p. Like ∂(sx^p) = (sp)*x^(p-1). You select one position (recording it in the shape) and delete it. The snag is that p-1 is tricky to get your hands on without dependent types. But InContext selects a position without deleting it.
InContext (s :<| p) ~= (s, p) :<| p
This works just as well for the dependent case, and we joyously acquire
InContext (f :><: g) ~= InContext f :><: InContext g
Now we know that InContext f is always a Comonad, and this tells us that tensor products of InContexts are comonadic because they are themselves InContexts. That's to say, you pick one position per dimension (and that gives you exactly one position in the whole thing), where before we had one outer position and lots of inner positions. With the tensor product replacing composition, everything works sweetly.

Naperian Functors

But there is a subclass of Functor for which the tensor product and the composition coincide. These are the Functors f for which f () ~ (): i.e., there is only one shape anyway, so raggedy values in compositions are ruled out in the first place. These Functors are all isomorphic to (p ->) for some position set p which we can think of as the logarithm (the exponent to which x must be raised to give f x). Correspondingly, Hancock calls these Naperian functors after John Napier (whose ghost haunts the part of Edinburgh where Hancock lives).
class Applicative f => Naperian f where
  type Log f
  project :: f x -> Log f -> x
  positions :: f (Log f)
  --- project positions = id
A Naperian functor has a logarithm, inducing a projection function mapping positions to the elements found there. Naperian functors are all zippily Applicative, with pure and <*> corresponding to the K and S combinators for the projections. It's also possible to construct a value where at each position is stored that very position's representation. Laws of logarithms which you might remember pop up pleasingly.
newtype Id x = Id {unId :: x} deriving Show

instance Naperian Id where
  type Log Id = ()
  project (Id x) () = x
  positions = Id ()

newtype (:*:) f g x = Pr (f x, g x) deriving Show

instance (Naperian f, Naperian g) => Naperian (f :*: g) where
  type Log (f :*: g) = Either (Log f) (Log g)
  project (Pr (fx, gx)) (Left p) = project fx p
  project (Pr (fx, gx)) (Right p) = project gx p
  positions = Pr (fmap Left positions, fmap Right positions)
Note that a fixed size array (a vector) is given by (Id :*: Id :*: ... :*: Id :*: One), where One is the constant unit functor, whose logarithm is Void. So an array is Naperian. Now, we also have
instance (Naperian f, Naperian g) => Naperian (f :.: g) where
  type Log (f :.: g) = (Log f, Log g)
  project (C fgx) (p, q) = project (project fgx p) q
  positions = C $ fmap (\ p -> fmap (p ,) positions) positions
which means that multi-dimensional arrays are Naperian.

To construct a version of InContext f for Naperian f, just point to a position!
data Focused f x = f x :@ Log f

instance Functor f => Functor (Focused f) where
  fmap h (fx :@ p) = fmap h fx :@ p

instance Naperian f => Comonad (Focused f) where
  counit (fx :@ p) = project fx p
  cojoin (fx :@ p) = fmap (fx :@) positions :@ p
So, in particular, a Focused n-dimensional array will indeed be a comonad. A composition of vectors is a tensor product of n vectors, because vectors are Naperian. But the Focused n-dimensional array will be the n-fold tensor product, not the composition, of the n Focused vectors which determine its dimensions. To express this comonad in terms of zippers, we'll need to express them in a form which makes it possible to construct the tensor product. I'll leave that as an exercise for the future.

                        
这篇关于为n维网格类型编写联合或cobind的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！