haskell - 为 n 深度结构生成实例？

Question

作者:n-depth structure我的意思是某种嵌套一种结构的结构 n次，例如 [[a]]是一个 2 深度列表。

我随机想到 Functor 的一个实例, Foldable和Traversable今天的 3 深度列表 ( [[[a]]] )，发现了一些规律，如下所示:

instance Functor [[[]]] where
    fmap f n = fmap (fmap (fmap f)) n

instance Foldable [[[]]] where
    foldMap f n = foldMap (foldMap (foldMap f)) n

instance Traversable [[[]]] where
    sequenceA n =
        let fz = \z -> sequenceA z
            fy = \y -> sequenceA (fmap fz y)
            fx = \x -> sequenceA (fmap fy x)
        in  fx n

我认为这可以通过某种方式安全地自动化，不仅适用于 []但任何具有这些实例的结构(如 Vector )，不仅是 3 深度，而且是任何深度，只要它大于零。

我认为类似data Depth = One | Succ Depth将用于编译时深度计算，但除此之外，我不知道它是如何进行的。您认为这实际上可能吗？你会如何实现它？

Answer 1

你所说的本质上是仿函数的组合(具体来说，是n倍自组合，但这并不重要)。

确实such compositions可以自动创建 Functor、Applicative、Foldable 和 Traversable 类的实例。此外，您还可以拥有一堆 monad transformers (本质上是仿函数组合的另一种方法)。

要使用相同的仿函数使其n折叠，您需要一个合适的包装器。

{-# LANGUAGE DataKinds, KindSignatures, GADTs, FlexibleInstances, FlexibleContexts #-}
data Nat = Z | S Nat

data NCompose :: Nat -> (* -> *) -> * -> * where
  Singly :: f x -> NCompose (S Z) f x
  Multiplie :: NCompose n f (f x) -> NCompose (S n) f x

instance Functor (NCompose Z f) where
  fmap _ _ = undefined -- safe, since there's no constructor for `NCompose Z f x`
instance (Functor f, Functor (NCompose n f)) => Functor (NCompose (S n) f) where
  fmap f (Singly q) = Singly $ fmap f q
  fmap f (Multiplie q) = Multiplie $ fmap (fmap f) q