为什么差异列表不是可折叠的实例？ [英] Why are difference lists not an instance of foldable?

问题描述

dlist包包含 DList 数据类型，其中包含大量实例，但不包含 Foldable 或 Traversable 。在我看来，这些是最类似列表类型中的两个。是否有一个性能原因， DList 不是这些类的实例？

另外，该包还实现了 foldr 和 unfoldr ，但没有其他折叠功能。

[a] ，它在逆变位置有一个 a ，所以它不能实现 Foldable 或 Traversable ，甚至可以直接使用 Functor 。实现它们的唯一方法是转换到常规列表和从常规列表转换（请参阅 foldr 实现），这会破坏差异列表的性能优势。

The dlist package contains the DList data type, which has lots of instances, but not Foldable or Traversable. In my mind, these are two of the most "list-like" type classes. Is there a performance reason that DList is not an instance of these classes?

Also, the package does implement foldr and unfoldr, but none of the other folding functions.

解决方案

DList a is a newtype wrapper around [a] -> [a], which has an a in a contravariant position, so it cannot implement Foldable or Traversable, or even Functor directly. The only way to implement them is to convert to and from regular lists (see the foldr implementation), which defeats the performance advantage of difference lists.

这篇关于为什么差异列表不是可折叠的实例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！