3

各种优化问题，例如这个问题，导致 Church 编码列表作为一种启用流融合的方式，即编译器消除中间结果（例如列表）。这是在优化问题中成功使用的定义：

{-# LANGUAGE RankNTypes #-}

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

以下是我对 Church-somethings 的看法：与其问“某事”是什么，不如问它能为你做什么。对于列表，答案是：列表可以折叠。为了折叠，我需要一个 type 的“更新”函数b->a->b和一个 type 的起始值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在 a 中选择正确的“更新”函数和起始值的练习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 ，但我们没有。这是一个奇怪的问题：基本上我们想告诉编译器：你不需要，相信我...另一方面， A 很容易构造。一个in place of the hole不起作用，因为它总是被调用 - 懒惰似乎并没有解决这个问题。所以，我被困住了。因此这里是abuild lbbheadL' :: ListL a -> ListL aerror "empty list!"_headL

问题一：如何headL实施？

第二个问题出现在尝试实现repeatM :: Monad m => m a -> m [a]. 与 一样iterUntil，需要谓词a->Bool来停止迭代：

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

目的很明确：重复一个单子动作m a，直到a->Bool满足为止。想法当然是ListL a马上把它折叠起来，实现流融合（list fusion）。例如：

import System.Random (randomIO)

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

这个例子是相当做作的，它打印出在找到第一个数字 >42 之前所花费的抽奖次数。m例如，在更现实的环境中，monad是ST s包装了一些 FFI 的 monad。关键是：这应该有效地运行。我完全被这个卡住了。我如何纠缠(>>=) :: m a -> (a->m b) -> m b与build得到一个m (ListL a)？即这是

问题2：如何iterUntilM实施？

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

4

1 回答 1

5

一般来说，当你删除关于一个类型的假设时，你编写的函数不仅会更通用（就它可以使用的类型而言），它也会更具体地说明它到底在做什么。这就是教堂编码允许融合所发生的事情：当列表表示为

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融合模式中比另一种更好。在其他地方，使用展开模式。

前言不碍事，我们需要问两个问题：

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

head可以foldr很容易地在 -encoded 列表上实现：

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)

你会注意到这个函数（就像tail-lists一样foldr）是O(n)。它也不适用于无限列表。这是一个很好的迹象，表明它foldl'不是融合的正确选择head。

现在，对于iterUntilM，我们看到（我不认为）甚至可以进行融合的情况。因为m最终在外面，你必须运行列表中的所有效果（实现它）。

如需对该领域的全面了解，请查看此博客文章。

于 2018-06-08T18:40:10.597 回答