是否有看起来不像容器的非平凡的 Foldable 或 Traversable 实例？

Question

有很多函子看起来像容器（列表、序列、映射等），还有许多其他函子不像容器（状态转换器、IO、解析器等）。我还没有看到任何看起来不像容器的重要 Foldable 或 Traversable 实例（至少如果你眯着眼睛看的话）。存在吗？如果不是，我很乐意更好地理解为什么他们不能。

Answer 1

好吧，在 universe 的帮助下，我们可以为有限状态空间上的状态转换器编写 Foldable 和 Traversable 实例。这个想法大致类似于函数的 Foldable 和 Traversable 实例：运行函数无处不在 Foldable 并查找 table [=12] =].因此：

import Control.Monad.State
import Data.Map
import Data.Universe

-- e.g. `m ~ Identity` satisfies these constraints
instance (Finite s, Foldable m, Monad m) => Foldable (StateT s m) where
    foldMap f m = mconcat [foldMap f (evalStateT m s) | s <- universeF]

fromTable :: (Finite s, Ord s) => [m (a, s)] -> StateT s m a
fromTable vs = StateT (fromList (zip universeF vs) !)

float :: (Traversable m, Applicative f) => m (f a, s) -> f (m (a, s))
float = traverse (\(fa, s) -> fmap (\a -> (a, s)) fa)

instance (Finite s, Ord s, Traversable m, Monad m) => Traversable (StateT s m) where
    sequenceA m = fromTable <$> traverse (float . runStateT m) universeF

我不确定这是否有意义。如果是这样，我想我会很乐意将它添加到包中；你怎么看？

Answer 2

我不认为它实际上是可折叠或可遍历的，但 MonadRandom 是一个例子，它可以像无限列表一样运行，但它看起来不像其他任何可折叠的容器。从概念上讲，它是一个随机变量。

Answer 3

每个有效的 Traversable f 都同构于 Normal s 对于某些 s :: Nat -> * where

data Normal (s :: Nat -> *) (x :: *) where  -- Normal is Girard's terminology
  (:-) :: s n -> Vec n x -> Normal s x

data Nat = Zero | Suc Nat

data Vec (n :: Nat) (x :: *) where
  Nil   :: Vec Zero n
  (:::) :: x -> Vec n x -> Vec (Suc n) x

但是在 Haskell 中实现 iso 一点也不简单（但值得一试完全依赖类型）。从道德上讲，您选择的 s 是

data {- not really -} ShapeSize (f :: * -> *) (n :: Nat) where
  Sized :: pi (xs :: f ()) -> ShapeSize f (length xs)

和iso的两个方向分离和重组形状和内容。一个事物的形状是由fmap (const ())给出的，关键是f x的形状的长度就是f x本身的长度。

向量在从左到右访问一次的意义上是可遍历的。通过保留形状（因此大小）和遍历元素向量，法线可以精确地遍历。可遍历就是将有限多个元素位置按线性顺序排列：与普通函子的同构恰好按线性顺序公开元素。相应地，每个 Traversable 结构都是一个（有限的）容器：它们有一组大小相同的形状和相应的位置概念，由严格小于大小的自然数的初始段给出。

Foldable事物也是有限的，它们使事物保持秩序（有一个明智的toList），但不能保证它们是Functor，所以它们没有 shape 这样清晰的概念。在这个意义上（"container" 由我的同事 Abbott、Altenkirch 和 Ghani 定义），它们不一定承认形状和位置特征，因此不是容器。如果幸运的话，其中一些可能是容器到某个商数。事实上 Foldable 的存在是为了允许处理像 Set 这样的结构，其内部结构旨在保密，并且当然取决于遍历操作不一定遵守的元素的排序信息。然而，究竟什么构成了良好的表现 Foldable 是一个有争议的问题：我不会质疑该库设计选择的实际好处，但我希望有一个更清晰的规范。

是否有看起来不像容器的非平凡的 Foldable 或 Traversable 实例？

Are there non-trivial Foldable or Traversable instances that don't look like containers?

haskell

traversal

fold