使用anamorphism列出过滤器

Question

我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,然后使用paramorphism重新实现,所以我结束于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开始看起来非常类似于专门用于列表的apomorphism的第一个参数:

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

([a] -> Either [a] [a]vs [a] -> Prim [a] [a] (Either [a] [a])

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

我知道我可以使用折叠,但问题是关于展开.

Answer 1

简而言之:这是不可能做到的.你总是必须以某种方式分解输入列表,而单独展开则无法实现.您可以在代码中看到它.你有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？

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

现在如何filter工作:在每一步它消耗一个列表的一个元素,有时它产生一个输出元素(如果它满足给定的谓词).

所以我们看到我们可以实现filter一个catamorphism - 我们在有限的时间内使用列表的每个元素.

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