关于Haskell中的Church编码列表

Question

像这样的各种优化问题导致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,相信我...... headL' :: ListL a -> ListL a另一方面,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)

目的很明确:重复一个monadic动作,m a直到a->Bool满意为止.当然,这个想法是立即折叠ListL a并实现流融合(列表融合).例如:

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实施？

除了是一个很好的学习练习,这实际上是个好主意吗？

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

这个序言,我们需要提出两个问题:

• 这些函数(head和iterUntilM)是仅在foldr表示(如append),unfoldr表示(如tail),或两者(如map)中有效工作？
• 严格的左折编码是否适合这些？它是否受到限制(即我们需要foldr吗？),还是可以限制得更多？

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

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

在foldl'列表中,它有点复杂:

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

您会注意到此函数(如tailon foldr-lists)是O(n).它也不适用于无限列表.这是一个很好的指示,foldl'不是融合的正确选择head.

现在,因为iterUntilM,我们看到一个案例(我不认为)甚至融合是可能的.因为m最终在外面,你必须运行列表中的所有效果(实现它).

有关此区域的概述,请查看此博客文章.