有没有看起来不像容器的非平凡可折叠或可遍历实例？

Question

有没有看起来不像容器的非平凡可折叠或可遍历实例？

23

有很多像容器（列表、序列、映射等）的函数子，还有许多不是容器的（状态转换器、IO、解析器等）。我还没有看到过任何不像容器的非平凡的Foldable或Traversable实例（至少如果你眯一下眼睛的话）。是否存在任何不是容器的实例？如果没有，我想更好地理解它们不能存在的原因。

- dfeuer

9

如果你有点眯起眼睛，那么任何 Foldable 都必然看起来像一个列表。 - leftaroundabout

@leftaroundabout，这并不完全正确，因为Foldable可以在两个方向上无限扩展。但我对其潜在的直觉很感兴趣。它似乎主要与能够直接折叠该物体而无需在中间进行任何其他操作有关，但这并不是非常正式的。 - dfeuer

像 data Prod1 f g a = P1 (f a) (g a); newtype Comp f g a = Comp (f (g a)); data Sum1 f g a = L1 (f a) | R1 (g a) 这样的东西呢？它们都有一个 instance (Foldable f, Foldable g) => Foldable (X f g)；我认为这些都是非平凡的（我相信但还没有检查它们是否都是合法的实例）。 - user2407038

@user2407038，我不认为你能从这些东西中建造出任何不像容器的东西。 - dfeuer

2

在Daniel Wagner的答案上进行扩展，您可以将StateT编写为newtype StateT s m a = St { runSt :: (((->) s) :.: m :.: ((,) s)) a }，其中:.:是Comp。如果您同意StateT是一个非平凡的Foldable，那么确实可以从中构建一个非平凡的Foldable。这依赖于Finite a => Foldable ((->) a) 来作为“非平凡”的Foldable，如果您足够仔细地看（例如(->) Natural可以表示列表），它也看起来像一个容器。我认为答案主要基于您如何定义“容器”。 - user2407038

1

任何东西都可以使用 toList x = [] 具有可折叠实例。我不知道你所说的“非平凡”是什么意思；如果你试图形式化它，你可能会发现这是强制你的函子成为“容器类”的条件。Traversable 更加有趣。 - Reid Barton

3个回答

10

借助于universe，一个人理论上可以为有限状态空间上的状态转换器编写Foldable和Traversable实例。这个想法大致类似于函数的Foldable和Traversable实例：对于Foldable，在每个地方运行该函数；对于Traversable，制作一个查找表。因此：

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

我不确定这是否有意义。如果有的话，我想我会很乐意将其添加到包中；你觉得呢？

- Daniel Wagner

我认为到那时你已经有了一个容器，而这些实例听起来很合理。 - dfeuer

4

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

- Davislor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pigworker · Accepted Answer

每个有效的 Traversable f 都同构于某个s :: Nat -> * 的 Normal s，其中

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 本身的长度。

向左遍历每个元素恰好遍历一次向量。法线可以保持形状（因此大小）遍历元素向量。可遍历的含义是有限多个元素位置按线性顺序排列：与正常的函数对象同构正好暴露了它们的线性顺序中的元素(所以法线也是一个容器)。相应地，每个遍历结构都是(finitary)容器:它们具有一组具有尺寸的形状，并且对于自然数初始段严格小于该尺寸的位置给出了相应的概念。

Foldable的东西也是finitary，它们以一定的顺序保持物品(有一个明智的toList)，但是它们不能保证是Functor，因此它们没有如此精确的形状概念。在我同事Abbott、Altenkirch和Ghani定义的“容器”的意义下，它们不一定能够允许形状和位置的刻画，因此不是容器。如果你很幸运，其中一些可能是容器的等价物。确实，Foldable的存在允许处理像 Set 这样的结构，其内部结构被认为是秘密的，并且肯定取决于关于元素的排序信息，这些信息不一定受到遍历操作的尊重。然而，什么构成一个良好的Foldable实际上是一个有争议的问题:我不会对该库设计选择的实用主义效益提出异议，但我希望有一个更清晰的规范。