是否存在看似容器的非平凡可折叠或可遍历实例？

Question

有许多仿函数看起来像容器(列表,序列,映射等),还有许多仿函数没有(状态转换器IO,解析器等).我还没有看到任何看起来像容器的非平凡Foldable或Traversable实例(至少如果你斜视一下).有存在吗？如果没有,我很想更好地了解他们为什么不能这样做.

Answer 1

对于某些人来说,每个有效的Traversable f都是同构的Normal ss :: Nat -> *地方,

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 ()),关键在于a的形状f x长度是其f x自身的长度.

向量可以在访问 - 每次 - 从左到右的意义上遍历.通过保持形状(因此大小)和遍历元素向量,可以精确地遍历法线.可遍历的是有限多个元素位置以线性顺序排列:与普通仿函数的同构精确地以线性顺序暴露元素.相应地,每一个Traversable结构都是一个(有限的)容器:它们具有一组形状 - 大小和相应的位置概念,由自然数的初始段给出,严格小于该大小.

的Foldable东西也有穷的,他们保持订单的事情(有一个合理的toList),但他们不能保证FunctorS,所以他们没有这样的概念,酥形状.从这个意义上讲(由我的同事Abbott,Altenkirch和Ghani定义的"容器"意义),他们不一定承认形状和位置的特征,因此不是容器.如果你很幸运,他们中的一些人可能是一些容器.确实Foldable存在允许处理结构,这是一个有争议的问题,但是:我不会对该库设计选择的实用好处进行狡辩,但我希望有一个更清晰的规范.Set其内部结构旨在成为秘密的结构,并且当然取决于有关元素的排序信息,这些信息不一定被遍历操作所尊重.究竟是什么构成了良好的表现Foldable

Answer 2

那么,在宇宙的帮助下,人们可以在有限状态空间上为状态变换器编写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

我不确定这是否合理.如果确实如此,我想我很乐意将其添加到包装中; 你怎么看？