list - 关于 Haskell 中的 Church 编码列表

Question

各种优化问题，如this one ，导致了 Church 编码列表作为实现流融合的一种方式，即编译器消除中间结果(例如列表)。以下是在优化问题中成功使用的定义:

{-# LANGUAGE RankNTypes #-}

-- A list encoded as a strict left fold.
newtype ListL a = ListL {build :: forall b. (b -> a -> b) -> b -> b}

我对教会事物的看法是这样的:不要问“某物”是什么，而是问它能为你做什么。对于列表，答案是:列表可以折叠。为了折叠，我需要一个 b->a->b 类型的“更新”函数以及 b 类型的起始值。然后我会给你返回折叠的结果，其类型为 b 。因此 ListL 的定义。下面是对ListL的一些基本操作:

mapL :: (a -> a') -> ListL a -> ListL a'
mapL f l = ListL (\f' b' -> build l (\b a -> f' b (f a)) b')

instance Functor ListL where fmap = mapL

fromList :: [a] -> ListL a
fromList l = ListL (\c z -> foldl' c z l)

toList :: ListL a -> [a]
toList l = build l snoc [] where snoc xs x = xs ++ [x]

nullL :: ListL a -> Bool
nullL l = build l (\_ _->False) True

这里有更多:

filterL :: (a->Bool) -> ListL a -> ListL a
filterL p l = ListL (\f b->build l (\b' a'->if p a' then f b' a' else b') b)

iterUntil :: (a->Bool) -> a -> (a->a) -> ListL a
iterUntil p a f = ListL (\g b-> snd $ until (p.fst) (\(a',b')->(f a', g b' a')) (a,b))

iterUntil迭代函数a->a ，以 a 类型的某个值开始，直到谓词 a->bool已实现。像 Prelude 的 iterate 这样的函数不可能的 - 至少我不知道如何定义它，它必须是某种递归。

继续举例，length和sum只是在 foldl 中选择正确的“更新”函数和起始值的练习:

lengthL :: ListL a -> Int
lengthL l = build l (\b _ -> b+1) 0

sumL :: Num a => ListL a -> a
sumL l = build l (+) 0

现在，让我们尝试 headL :

headL :: ListL a -> a
headL l = build l (\_ a->a) _   -- this does not compile!

无论怎样开始b提供，第一个a应该被退回。 build l需要 b ，但我们没有。这是一个奇怪的:基本上我们想告诉编译器:你不需要 b ，相信我... A headL' :: ListL a -> ListL a另一方面，易于构造。安error "empty list!"代替孔_不起作用，因为它总是被调用 - 懒惰似乎并没有解决这个问题。所以，与 headL我被困住了。因此这里是

问题1:headL怎么样？实现了吗？

当尝试实现 repeatM :: Monad m => m a -> m [a] 的等效项时，会出现第二个问题。 。与 iterUntil 一样, 谓词 a->Bool需要停止迭代:

iterUntilM :: Monad m => (a->Bool) -> m a -> m (ListL a)

目的很明确:重复单一 Action m a直到a->Bool很满意。当然，这个想法是折叠这个 ListL a马上实现流融合(列表融合)。例如:

import System.Random (randomIO)

main :: IO ()
main = do
     rs <- iterUntilM (>42::Int) randomIO
     print $ lengthL rs

该示例相当人为，它打印了找到第一个 >42 的数字之前所花费的抽奖次数。在更现实的设置中，单子(monad) m例如， ST s 包装一些 FFI 的 monad。要点是:这应该有效运行。我完全被这个困住了。我该如何纠缠(>>=) :: m a -> (a->m b) -> m b与 build获得 m (ListL a) ？ IE。这是

问题2:iterUntilM怎么样实现了吗？

除了作为一个很好的学习练习之外，这实际上是一个好主意吗？

Answer 1

一般来说，当您消除对类型的假设时，您编写的函数不仅会更加通用(就其可以使用的类型而言)，而且对于什么内容也会更加具体正是它正在做的。这就是允许融合的教堂编码所发生的情况:当列表表示为

data [a] = [] | a : [a]

在函数中使用它们的方法有无数种，其中只有一种是 foldr。但是，当您有:

newtype List a = { runList :: forall b. (a -> b -> b) -> b -> b }

使用该类型的唯一方法是通过foldr。这就是您可以进行我们所了解和喜爱的优化的原因。顺便说一下，流融合只是其中之一:例如，您还可以获得 O(1) 追加。

您的类型仍然受到更多限制:它告诉我们底层列表不能(有意义地)无限。

还有另一种列表的约束表示可以转移焦点:

data List a = forall b. List b (b -> Maybe (a, b))

如果教堂编码列表是消费者，那么这是生产者。它没有说明如何使用该列表，但详细说明了如何创建该列表。

所以我们已经看到，我们从这些受限表示中得到了很多，但我们失去了什么？ tail 就是一个很好的例子。对于生产者:

tail (List x f) = case f x of
  Just (_,xs) -> List xs f

对于消费者来说:

tail xs =
    List (\c n ->
        runList xs 
            (\h t g -> g h (t c)) 
            (const n) 
            (const id))

消费者的实现是O(n)，而生产者的实现显然是O(1)。

这两种类型都可以进行融合，但某些功能可以比另一种更有效地实现。 GHC 碰巧选择了前一种表示形式作为融合的基础，但没有任何根本性的因素可以使该选择变得优越:Haskellers 使用的大多数函数似乎在融合的 foldr/build 模式中比在另一个。在 other places ，使用展开图案。

序言结束了，我们需要问两个问题:

• 这些函数(head 和 iterUntilM)是否仅在 foldr 表示(如追加)中有效工作，或者在 展开器表示(如tail)，或两者(如map)？
• 严格的左折叠编码是这些的正确选择吗？是不是太受限制了(即我们需要 foldr？)，还是可以受更多限制？

head 可以很容易地在 foldr 编码列表上实现:

head xs = runList xs const (error "head: empty list")

在 foldl'-lists 上，情况有点复杂:

head xs =
    fromMaybe
        (error "head: empty list")
        (build xs (\xs x -> maybe (Just x) Just xs) Nothing)

您会注意到这个函数(如 foldr-lists 上的 tail)的复杂度为O(n)。它也不适用于无限列表。这很好地表明 foldl' 不是融合 head 的正确选择。

现在，对于iterUntilM，我们看到了一种情况(我认为)甚至融合也是可能的。因为 m 最终位于外部，所以您必须运行列表中的所有效果(具体化它)。

有关此区域的详细概述，请查看 this博客文章。