使用变形的列表过滤器 [英] List filter using an anamorphism

问题描述

我使用了recursion-schemes黑客库中的变形来实现了损坏的filter函数:

I implemented a broken filter function using an anamorphism from recursion-schemes Hackage library:

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结尾:

The function is not a faithful implementation of filter: xfilter odd [1..5] works, but xfilter odd [0,0] doesn't. I tried to implement "retries" by using explicit recursion in phi and then reimplemented that with a paramorphism, so I ended with 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中明确表示重试并在外部执行:

This is satisfactory, but I then tried to express retries explicitly in phi and perform them outside:

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表示重试新种子".

Right means 'produce a new element' and Left means 'retry with a new seed'.

phi的签名开始看起来与专门用于列表的阿朴素的第一个参数非常相似:

The signature of phi started to look pretty similar to the first argument of apomorphism specialized for lists:

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

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

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

So I wonder is it possible to implement filtering using apomorphisms or other generalized unfolds, or ana . para is the best I can hope for?

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

I know I can use folds, but the question is specifically about unfolds.

推荐答案

总之:无法完成.您总是必须以某种方式分解输入列表，而仅靠展开是无法完成的.您已经在代码中看到了.您有retry (phi f)，它等效于dropWhile (not . f)，它递归地使用一个输入列表.在您的情况下，递归位于retry内部.

In short: This can't be done. You always have to break down the input list somehow, which you can't accomplish by unfolding alone. You can see that in your code already. You have retry (phi f), which is equivalent to dropWhile (not . f), which recursively consumes an input list. In your case, the recursion is inside retry.

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

We can implement filter using ana, but the function passed to ana will have to be recursive, as in

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

但是，我们可以使用para进行过滤，而无需任何进一步的递归:

However, we can implement filtering using para without any further recursion:

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

(尽管这不是您感兴趣的内容).

(although this is not what you've been interested in).

• 同形表示递归递归，其中每个递归步骤至少消耗一个构造函数.由于每个步骤只需要有限的时间，因此这一起确保了在使用(有限)数据结构时，整个递归始终终止.
• 变形表示共归纳递归，其中每个递归步骤都由构造函数保护.这意味着尽管结果可能是无限的，但构造的数据结构的每个部分(构造函数)都是在有限的时间内产生的.

现在filter的工作方式:在每个步骤中，它消耗列表的一个元素，有时会生成一个输出元素(如果它满足给定谓词).

Now how filter works: At each step it consumes one element of a list and sometimes it produces an output element (if it satisfies a given predicate).

因此，我们看到可以将filter实现为类推化-我们在有限的时间内消耗列表的每个元素.

So we see that we can implement filter as a catamorphism - we consume each element of a list in a finite time.

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

But we can't implement filter just as an anamorphism. We can never know when filter produces a new result. We can't describe the production of a next output element using just a finite number of operations. For example, let's take filter odd (replicate n 0 ++ [1]) - it takes O(n) steps to produce the first element 1. So there must be some kind of recursion that searches an input list until it finds a satisfying element.

这篇关于使用变形的列表过滤器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！