Haskell 中的一个常见习惯用法，即差异列表，是将列表表示xs为 value (xs ++)。然后(.)变成“ (++)”并id变成“ []”（实际上这适用于任何幺半群或类别）。由于我们可以在恒定时间内组合函数，这为我们提供了一种通过附加来有效地构建列表的好方法。
不幸的是，该类型[a] -> [a]比表单的函数类型大得多(xs ++)——列表上的大多数函数都做一些事情，而不是在它们的参数前添加。
解决此问题的一种方法（如 中使用的）是使用智能构造函数dlist创建特殊类型。DList另一种方法（如 中使用的ShowS）是不在任何地方强制执行约束并希望获得最好的结果。但是，在使用大小正好合适的类型的同时，有没有一种很好的方法可以保留差异列表的所有所需属性？
是的！
我们可以将[a]其视为一个免费的 monad 实例Free ((,) a) ()。
因此，我们可以应用 Edward Kmett 在Free Monads for Less中描述的方案。
我们会得到的类型是
newtype F a = F { runF :: forall r. (() -> r) -> ((a, r) -> r) -> r }
或者干脆
newtype F a = F { runF :: forall r. r -> (a -> r -> r) -> r }
我们列表runF的函数就是这样！foldr
这被称为Boehm-Berarducci 编码，它与原始数据类型（列表）同构——所以它尽可能小。
威尔内斯 说：
所以这种类型仍然太“宽”，它允许的不仅仅是前缀 - 不限制 g 函数参数。
如果我正确理解了他的论点，他指出您可以将foldr(or runF) 函数应用于与 and 不同的[]东西(:)。
但我从未声称您只能将foldr-encoding 用于连接。事实上，正如这个名字所暗示的，你可以用它来计算任何折叠——这就是 Will Ness 所展示的。
如果您暂时忘记了有一个真正的列表类型，可能会变得更清楚，[a]. 可能有很多列表类型——例如我可以定义一个
data List a = Nil | Cons a (List a)
它与 不同，但同构[a]。
上面的foldr-encoding 只是列表的另一种编码，例如List aor [a]。它也与 同构[a]，正如函数所证明的那样\l -> F (\a f -> foldr a f l)，\x -> runF [] (:)并且它们的组合（以任一顺序）是同一性的事实。但是您没有义务转换为[a]- 您可以List直接转换为，使用\x -> runF x Nil Cons.
重要的一点是它F a不包含不是foldr某个列表的函数的元素 - 也不包含一个元素是foldr多个列表的函数（显然）。
因此，它不会包含太少或太多的元素——它包含的元素数量恰好与准确表示所有列表所需的一样多。
差异列表编码并非如此——例如，该reverse函数不是任何列表的追加操作。