使用无变形的列表过滤器
我使用来自filter黑客库的非变态功能实现了一个破碎的recursion-schemes函数：
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 xRight的意思是‘产生一个新的元素’，而Left的意思是‘用新的种子重试’。
phi的签名开始非常类似于专用于列表的同胚的第一个参数：
xxapo :: ([a] -> Prim [a] (Either [a] [a])) -> [a] -> [a]
xxapo = apo([a] -> Either [a] [a] vs [a] -> Prim [a] [a] (Either [a] [a])
所以我想知道是否有可能使用同态或其他广义展开来实现过滤，或者ana . para是我所希望的最好的呢？
我知道我可以使用折叠，但问题是具体的展开。
回答 2
Stack Overflow用户
发布于 2013-08-25 08:09:38
简而言之，这是不可能的。您总是必须以某种方式分解输入列表，这是无法通过单独展开来完成的。您可以在代码中看到这一点。您有retry (phi f)，它相当于dropWhile (not . f)，它递归地使用一个输入列表。在您的例子中，递归在retry中。
我们可以使用filter实现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呢？
- 变体表示归纳递归，其中每个递归步骤至少消耗一个构造函数。因为每个步骤只需要有限的时间，这就确保了当使用(有限)数据结构时，整个递归总是终止的。
- 无形化表示共归纳递归，其中每个递归步骤都由构造函数保护.这意味着，尽管结果可以是无限的，但所构造的数据结构的每个部分(构造函数)都是在有限的时间内产生的。
现在，filter是如何工作的:在每一步，它都会消耗列表中的一个元素，有时它会生成一个输出元素(如果它满足给定的谓词)。
因此，我们可以将filter作为一种变形来实现--我们在有限的时间内消耗列表中的每一个元素。
但是我们不能把filter仅仅作为一种变形来实现。我们永远无法知道filter何时会产生新的结果。我们不能用有限的操作来描述下一个输出元素的产生。例如，让我们采用filter odd (replicate n 0 ++ [1]) -它需要O(n)步骤来生成第一个元素1。因此，必须有某种递归来搜索输入列表，直到找到令人满意的元素为止。
Stack Overflow用户
发布于 2013-08-25 14:10:06
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)但最后是猫。
https://stackoverflow.com/questions/18421926
复制相似问题
腾讯云开发者
