Фильтр списка с использованием анаморфизма

Я реализовал сломанную функцию filter, используя анаморфизм из recursion-schemes Библиотека Hackage:

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] vs [a] -> Prim [a] [a] (Either [a] [a])

Так что интересно, возможно ли реализовать фильтрацию с использованием апоморфизмов или других обобщенных разворачиваний, или ana . para - лучшее, на что я могу надеяться?

Я знаю, что могу использовать складки, но вопрос конкретно о разворачивается.

Ответы

Ответ 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?

  • Катаморфизмы представляют собой индуктивную рекурсию, где каждый рекурсивный шаг потребляет по меньшей мере один конструктор. Поскольку каждый шаг занимает только конечное время, вместе это гарантирует, что при потреблении (конечной) структуры данных вся рекурсия всегда заканчивается.
  • Анаморфизмы представляют собой коиндуктивную рекурсию, где каждый рекурсивный шаг защищен конструктором. Это означает, что хотя результат может быть бесконечным, каждая часть (конструктор) построенной структуры данных создается за конечное время.

Теперь, как работает filter: на каждом шаге он потребляет один элемент списка и иногда создает выходной элемент (если он удовлетворяет заданному предикату).

Итак, мы видим, что мы можем реализовать filter как катаморфизм - мы потребляем каждый элемент списка за конечное время.

Но мы не можем реализовать filter как анаморфизм. Мы никогда не узнаем, когда filter создаст новый результат. Мы не можем описать создание следующего выходного элемента, используя только конечное число операций. Например, возьмите filter odd (replicate n 0 ++ [1]) - для выполнения первого элемента 1 требуется выполнить шаги O (n). Таким образом, должна существовать какая-то рекурсия, которая ищет список ввода до тех пор, пока не найдет удовлетворяющий элемент.

Ответ 2

    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)

Но последнее - ката.