哪个Haskell Functors等同于Reader函子

Question

对于某些类型,一些Haskell仿函数F a显然是同构的,例如T -> aT

data Pair a = Pair a a            -- isomorphic to Bool -> a
data Reader r a = Reader (r -> a) -- isomorphic to r -> a (duh!)
data Identity a = Identity a      -- isomorphic to () -> a
data Phantom a = Phantom          -- isomorphic to void -> a

(这些同构只能达到严格,只考虑有限的数据结构.)

所以一般来说,我们如何在可能的情况下描述仿函数？

问题是"哪个Haskell Functors可以表示？"同样的问题？

Answer 1

挪亚说,对动物"你出来繁衍!",但蛇说:"我们不能繁殖,因为我们是加法器.",所以诺亚把木材从方舟,塑造它,说:"我建你的表日志."

表示的仿函数有时也被称为"Naperian"仿函数(这是彼得·汉考克的任期:汉克的爱丁堡相同的部分,约翰·纳皮尔的常客,对数成名),因为当F x ~= T -> x,并记住的是,组合地,T -> x是" x为动力T",我们T从某种意义上说,这是看到的Log F.

首先要注意的是F () ~= T -> () ~= ().这告诉我们只有一个形状.为我们提供形状选择的函数不能是Naperian,因为它们不能统一呈现数据的位置.这意味着[]不是Naperian,因为不同长度的列表具有由不同类型表示的位置.然而,无限Stream具有由自然数给出的位置.

相应地,给定任何两个F结构,它们的形状必然匹配,因此它们具有合理性zip,为我们提供了Applicative F实例的基础.

的确,我们有

          a  -> p x
=====================
  (Log p, a) ->   x

做p一个正确的伴随,所以p保留所有的限制,特别是单位和产品,使它成为一个幺正的函子,而不仅仅是一个松散的幺正函子.也就是说,Applicative具有同构的操作的替代表示.

unit  :: ()         ~= p ()
mult  :: (p x, p y) ~= p (x, y)

让我们有一个类型的东西.我和Representable同班同学的烹饪方法有点不同.

class Applicative p => Naperian p where
  type Log p
  logTable  :: p (Log p)
  project   :: p x -> Log p -> x
  tabulate  :: (Log p -> x) -> p x
  tabulate f = fmap f logTable
  -- LAW1: project logTable = id
  -- LAW2: project px <$> logTable = px

我们有一个类型Log f,至少代表一些位置f; 我们有一个logTable,在每个位置存储该位置的代表,就像f每个地方的地图名称"地图"; 我们有一个project函数提取存储在给定位置的数据.

第一条法则告诉我们,logTable所有代表的位置都是准确的.第二条法律告诉我们,我们代表了所有的立场.我们可以推断出这一点

tabulate (project px)
  = {definition}
fmap (project px) logTable
  = {LAW2}
px

然后

project (tabulate f)
  = {definition}
project (fmap f logTable)
  = {free theorem for project}
f . project logTable
  = {LAW1}
f . id
  = {composition absorbs identity}
f

我们可以设想一个通用实例 Applicative

instance Naperian p => Applicative p where
  pure x    = fmap (pure x)                    logTable
  pf <$> px = fmap (project pf <*> project ps) logTable

也就是说,p从通常的K和S继承自己的K和S组合器来实现功能.

当然,我们有

instance Naperian ((->) r) where
  type Log ((->) r) = r  -- log_x (x^r) = r
  logTable = id
  project = ($)

现在,所有类似限制的结构都保留了Naperianity.Log将limity事物映射到colimity事物:它计算左边的邻接.

我们有终端对象和产品.

data K1       x = K1
instance Applicative K1 where
  pure x    = K1
  K1 <*> K1 = K1
instance Functor K1 where fmap = (<*>) . pure

instance Naperian K1 where
  type Log K1 = Void -- "log of 1 is 0"
  logTable = K1
  project K1 nonsense = absurd nonsense

data (p * q)  x = p x :*: q x
instance (Applicative p, Applicative q) => Applicative (p * q) where
  pure x = pure x :*: pure x
  (pf :*: qf) <*> (ps :*: qs) = (pf <*> ps) :*: (qf <*> qs)
instance (Functor p, Functor q) => Functor (p * q) where
  fmap f (px :*: qx) = fmap f px :*: fmap f qx

instance (Naperian p, Naperian q) => Naperian (p * q) where
  type Log (p * q) = Either (Log p) (Log q)  -- log (p * q) = log p + log q
  logTable = fmap Left logTable :*: fmap Right logTable
  project (px :*: qx) (Left i)  = project px i
  project (px :*: qx) (Right i) = project qx i

我们有身份和构成.

data I        x = I x
instance Applicative I where
  pure x = I x
  I f <*> I s = I (f s)
instance Functor I where fmap = (<*>) . pure

instance Naperian I where
  type Log I = ()    -- log_x x = 1
  logTable = I ()
  project (I x) () = x

data (p << q) x = C (p (q x))
instance (Applicative p, Applicative q) => Applicative (p << q) where
  pure x = C (pure (pure x))
  C pqf <*> C pqs = C (pure (<*>) <*> pqf <*> pqs)
instance (Functor p, Functor q) => Functor (p << q) where
  fmap f (C pqx) = C (fmap (fmap f) pqx)

instance (Naperian p, Naperian q) => Naperian (p << q) where
  type Log (p << q) = (Log p, Log q)  -- log (q ^ log p) = log p * log q
  logTable = C (fmap (\ i -> fmap (i ,) logTable) logTable)
  project (C pqx) (i, j) = project (project pqx i) j

Naperian仿函数在最大的固定点下关闭,其对数是相应的最小固定点.例如,对于流,我们有

log_x (Stream x)
  =
log_x (nu y. x * y)
  =
mu log_xy. log_x (x * y)
  =
mu log_xy. log_x x + log_x y
  =
mu log_xy. 1 + log_xy
  =
Nat

这是一个有点繁琐呈现在Haskell中没有引入Naperian bifunctors(其中有两套两个各种各样的东西位置),或在索引类型(已编入索引的索引位置的东西)(更好)Naperian函子.然而,有趣的是,并且希望能够提出这个想法的是cofree comonad.

data{-codata-} CoFree p x = x :- p (CoFree p x)
  -- i.e., (I * (p << CoFree p)) x
instance Applicative p => Applicative (CoFree p) where
  pure x = x :- pure (pure x)
  (f :- pcf) <*> (s :- pcs) = f s :- (pure (<*>) <*> pcf <*> pcs)
instance Functor p => Functor (CoFree p) where
  fmap f (x :- pcx) = f x :- fmap (fmap f) pcx

instance Naperian p => Naperian (CoFree p) where
  type Log (CoFree p) = [Log p]  -- meaning finite lists only
  logTable = [] :- fmap (\ i -> fmap (i :) logTable) logTable
  project (x :- pcx) []       = x
  project (x :- pcx) (i : is) = project (project pcx i) is

我们可以接受Stream = CoFree I,给予

Log Stream = [Log I] = [()] ~= Nat

现在,D p仿函数的导数给出了它的单孔上下文类型,告诉我们i)a的形状p,ii)孔的位置,iii)不在孔中的数据.如果p是Naperian,没有形状的选择,所以将琐碎的数据放在非洞位置,我们发现我们只是得到了洞的位置.

D p () ~= Log p

关于这种联系的更多信息可以在我的关于尝试的答案中找到.

无论如何,Naperian对于Representable来说确实是一个有趣的苏格兰本地名称,你可以建立一个日志表:它们是完全由投影构成的结构,不提供"形状"选择.