11

我filter使用来自recursion-schemesHackage 库的变形实现了一个损坏的函数：

import Data.Functor.Foldable

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana $ project . phi f

phi :: (a -> Bool) -> [a] -> [a]
phi f (h : t) | not (f h) = t
phi f l = l

该函数不是 : 的忠实实现filter，xfilter odd [1..5]但xfilter odd [0,0]没有。我试图通过使用显式递归来实现“重试”，phi然后用超态重新实现它，所以我以ana . para：

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana . para $ phi where
    phi Nil = Nil
    phi (Cons h (t, tt)) | f h = Cons h t
    phi (Cons h (t, tt)) = tt

这是令人满意的，但我随后尝试在内部明确表达重试phi并在外部执行它们：

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana $ project . retry (phi f)

phi :: (a -> Bool) -> [a] -> Either [a] [a]
phi f (h : t) | not (f h) = Left t
phi f l = Right l

retry f x = case f x of
    Right x -> x
    Left x -> retry f x

Right意思是“产生一个新元素”，Left意思是“用新种子重试”。

的签名phi开始看起来与专门用于列表的同态的第一个参数非常相似：

xxapo :: ([a] -> Prim [a] (Either [a] [a])) -> [a] -> [a]
xxapo = apo

（[a] -> Either [a] [a]对[a] -> Prim [a] [a] (Either [a] [a]）

所以我想知道是否有可能使用同构或其他广义展开来实现过滤，或者ana . para是我所希望的最好的？

我知道我可以使用折叠，但问题是专门关于展开的。

4

2 回答 2

10

简而言之：这是做不到的。您总是必须以某种方式分解输入列表，而仅靠展开是无法完成的。您已经可以在代码中看到这一点。你有retry (phi f)，它等价于dropWhile (not . f)，它递归地使用一个输入列表。在你的情况下，递归是 inside retry。

我们可以实现filterusing ana，但传递给的函数ana必须是递归的，如

filter1 :: (a -> Bool) -> [a] -> [a]
filter1 p = ana f
  where
    f [] = Nil
    f (x : xs') | p x       = Cons x xs'
                | otherwise = f xs'

但是，我们可以para在没有任何进一步递归的情况下实现过滤：

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 p = cata f
  where
    f Nil = []
    f (Cons x r) | p x          = x : r
                 | otherwise    = r

（虽然这不是你一直感兴趣的）。

那么为什么它适用于cata但不适用ana呢？

  • Catamorphisms 表示归纳递归，其中每个递归步骤至少消耗一个构造函数。由于每个步骤只需要有限的时间，因此这确保了在使用（有限）数据结构时，整个递归总是终止。
  • Anamorphisms 表示共归纳递归，其中每个递归步骤都由构造函数保护。这意味着虽然结果可能是无限的，但构建的数据结构的每个部分（构造函数）都是在有限时间内产生的。

现在是如何filter工作的：在每一步它都会消耗列表中的一个元素，有时它会产生一个输出元素（如果它满足给定的谓词）。

所以我们看到我们可以实现filter为 catamorphism - 我们在有限的时间内消耗列表的每个元素。

但是我们不能filter仅仅作为变形来实现。我们永远不知道什么时候filter会产生新的结果。我们不能仅使用有限数量的操作来描述下一个输出元素的产生。例如，让我们采取filter odd (replicate n 0 ++ [1])- 它需要O(n)步骤来生成第一个元素1。所以必须有某种递归来搜索输入列表，直到找到一个令人满意的元素。

于 2013-08-25T08:09:38.613 回答
1 
    xfilter :: (a -> Bool) -> [a] -> [a]
    xfilter f xs = last $ apo phi ([xs], []) where
        phi ([[]], ys) = Cons [] $ Left [ys]
        phi ([h:t], ys) | f h = Cons [] $ Right ([t], h:ys)
        phi ([h:t], ys) = Cons [] $ Right ([t], ys)

但最后是一个cata。

于 2013-08-25T14:10:06.727 回答