haskell - 是否可以懒惰地获取 Traversable 的所有上下文？

Question

lens报价 holesOf ，这是这个假设函数的一个更通用和更强大的版本:

holesList :: Traversable t
          => t a -> [(a, a -> t a)]

给定一个容器， holesList生成容器的元素列表以及替换这些元素的函数。
holesList的类型，就像真正的 holesOf ，未能捕捉到产生的对数将等于容器元素数的事实。因此，一个更漂亮的类型将是

holes :: Traversable t
      => t a -> t (a, a -> t a)

我们可以实现 holes通过使用 holesList做一个列表然后遍历 State把这些元素重新灌进去。但这并不令人满意，原因有两个，其中一个有实际后果:

slurping 代码将有一个无法访问的错误调用来处理列表在遍历完成之前运行为空的情况。这很恶心，但对于使用该功能的人来说可能并不重要。

向左无限延伸的容器，或在左侧触底的容器根本不起作用。向左延伸很远的容器处理起来效率很低。

我想知道是否有任何方法可以解决这些问题。使用 Magma 之类的方法很可能捕获遍历的形状。镜头中:

data FT a r where
  Pure :: r -> FT a r
  Single :: a -> FT a a
  Map :: (r -> s) -> FT a r -> FT a s
  Ap :: FT a (r -> s) -> FT a r -> FT a s

instance Functor (FT a) where
  fmap = Map
instance Applicative (FT a) where
  pure = Pure
  (<*>) = Ap

runFT :: FT a t -> t
runFT (Pure t) = t
runFT (Single a) = a
runFT (Map f x) = f (runFT x)
runFT (Ap fs xs) = runFT fs (runFT xs)

现在我们有

runFT . traverse Single = id

traverse Single使一棵树充满元素以及将它们构建到容器中所需的功能应用程序。如果我们替换树中的一个元素，我们可以 runFT获得替换该元素的容器的结果。不幸的是，我被困住了:我不知道下一步会是什么样子。

模糊的想法:添加另一个类型参数可能有助于更改元素类型。 Magma type 做了这样的事情，它至少可以追溯到 Zemyla 对 Van Laarhoven 关于 FunList 的博客文章的评论。 .

Answer 1

Your existing solution来电runMag Ap 定义的树中的每个分支一次构造函数。

我没有分析任何东西，但作为 runMag本身是递归的，这可能会减慢一棵大树的速度。

另一种方法是打结，所以你只(实际上)调用runMag。整个树一次:

data Mag a b c where
  One :: a -> Mag a b b
  Pure :: c -> Mag a b c
  Ap :: Mag a b (c -> d) -> Mag a b c -> Mag a b d

instance Functor (Mag a b) where
  fmap = Ap . Pure

instance Applicative (Mag a b) where
  pure = Pure
  (<*>) = Ap

holes :: forall t a. Traversable t => t a -> t (a, a -> t a)
holes = \t -> 
    let m :: Mag a b (t b)
        m = traverse One t 
    in fst $ go id m m
  where
    go :: (x -> y)
       -> Mag a (a, a -> y) z
       -> Mag a a x
       -> (z, x)
    go f (One a)    (One _)    = ((a, f), a)
    go _ (Pure z)   (Pure x)   = (z, x)
    go f (Ap mg mi) (Ap mh mj) = 
      let ~(g, h) = go (f . ($j)) mg mh
          ~(i, j) = go (f .   h ) mi mj
      in (g i, h j)
    go _ _ _ = error "only called with same value twice, constructors must match"