11

Hackage ライブラリのアナモフィズムを使用して壊れた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 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)あなたの場合、再帰は内部にあり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でしょうか?

  • カタモルフィズムは、各再帰ステップが少なくとも 1 つのコンストラクターを消費する帰納的再帰を表します。各ステップは有限の時間しかかからないため、(有限の) データ構造を消費するときに、再帰全体が常に終了することが保証されます。
  • アナモフィズムは、再帰的な各ステップがコンストラクターによって保護される共誘導再帰を表します。これは、結果は無限になる可能性がありますが、構築されたデータ構造の各部分 (コンストラクター) は有限の時間で生成されることを意味します。

どのようにfilter動作するか: 各ステップで、リストの 1 つの要素を消費し、場合によっては出力要素を生成します (指定された述語を満たす場合)。

したがってfilter、カタモルフィズムとして実装できることがわかります-リストの各要素を有限時間で消費します。

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)

しかし、最後はカタです。

于 2013-08-25T14:10:06.727 に答える