2

在 Haskell 中，我们看到Foldable 和 Traversable 在 Haskell prelude 中落地。

这些都对序列进行操作。

Prelude Data.Sequence> map (\n -> replicate n 'a') [1,3,5]
["a","aaa","aaaaa"]
Prelude Data.Sequence> fmap (\n -> replicate n 'a') (1 <| 3 <| 5 <| empty)
fromList ["a","aaa","aaaaa"]

我的问题是Haskell 的 Foldable 和 Traversable 是否相当于Clojure 中的一个序列？

假设：

4

2 回答 2

16

不。虽然任何类型的Functor表示元素的有限序列都将是Traversable（因此Foldable），但还有许多其他结构是Traversable，但它们不是类似序列的，因为它们没有明显的连接概念。将有一种方法可以获取包含元素的序列，但结构可能不仅仅包含该序列。

实际上，这Traversable f意味着具有 type 的结构f x包含有限多个 type 元素x，并且该结构有某种方法可以只traverse访问每个元素x一次。因此，诸如“语法中的术语，被视为包含变量”之类的东西可以是Traversable.

data Term x
  = Var x
  | Val Integer
  | Add (Term x) (Term x)

instance Traversable Term where
  traverse f (Var x)    = pure Var <*> f x
  traverse f (Val i)    = pure (Val i)
  traverse f (Add s t)  = pure Add <*> traverse f s <*> traverse f t

您始终可以使用traverseto 对所有元素进行操作。我们fmap通过采取pure = id和<*>成为普通应用程序来获得。

instance Functor Term where
  fmap = fmapDefault

在哪里

fmap :: (x -> y) -> Term x -> Term y

实现同时重命名。

同时，Foldable实例

instance Foldable Term where
  foldMap = foldMapDefault

需要pure给一些幺半群的中性元素和<*>组合操作，所以我们得到了类似reduce的操作。例如，

foldMap (:[]) :: Term x -> [x]

给出一个术语中出现的变量列表. 也就是说，我们总是可以从Traversable数据中获取元素的序列，但数据可能具有这些元素以外的结构。Terms 具有除变量（它们Val的 s 和Adds）之外的结构，并且“cons”对于语法树的含义还不是很清楚。

因此，虽然结构比序列多Traversable，但该Traversable接口为您提供的类似序列的操作更少。的重点Traversable是概括map和reduce的操作，而不是捕获list。

于 2014-08-22T10:09:36.580 回答
1

我想指出有关Foldable 和 Traversable的 Haskell wiki 文档。

首先，Foldable和Traversable是两个不同的类型类。至于Foldable，维基页面的评论似乎表明它与 Clojure 序列几乎相同。每个Foldable都有一个列表表示：

toList :: Foldable a => [a]
toList a = foldr (:) [] a

并且（如果我错了，请纠正我）似乎折叠结构与折叠关联列表相同，即：

foldr f b a = foldr f b (toList a)

在这个等式中foldr，左侧是通用版本，而右侧是列表中的版本。

Haskell 和 Clojure 之间的主要区别在于，Clojure 要求您自己应用toList函数以在折叠/归约之前将数据结构转换为序列。对于平面数据结构（即列表、向量、哈希映射......）toList只是恒等函数，所以你看不到它。另一方面，对于像树这样的东西，你需要tree-seq在折叠之前调用一个函数。

于 2014-08-22T17:08:08.853 回答