[解決済み] パラモルフィズムとは何ですか？

質問

読み上げ この古典的な論文 を読んでいて、パラメオフィズムに行き詰った。 残念ながら、このセクションはかなり薄く、Wikipediaのページには何も書かれていません。

私のHaskell翻訳は

para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
  where
    h []       =   base
    h (x:xs)   =   f x xs (h xs)

しかし、私はそれを理解できません。型シグネチャや望ましい結果について、直感的に理解できないのです。

パラモルフィズムとは何か、そして実際に役立つ例は何か？

はい、私が見たのは これら 質問 を参照してください。しかし、これらは直接パラメオフィズムを扱っておらず リソース を紹介しているだけで、参考にはなっても学習教材としては使えません。

どのように解決するのですか？

はい、それは para . カタモルフィズムと比較したり foldr :

para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldr :: (a ->        b -> b) -> b -> [a] -> b

para  c n (x : xs) = c x xs (para c n xs)
foldr c n (x : xs) = c x    (foldr c n xs)
para  c n []       = n
foldr c n []       = n

カタモルフィズムと対比して、パラモルフィズムをプリミティブ再帰と呼ぶ人もいる ( foldr ) が反復であることと対比して、quot;iteration" と呼ぶ人もいます。

ここで foldr の2つのパラメータは、入力データの再帰的なサブオブジェクト（ここではリストの末尾）ごとに再帰的に計算された値が与えられます。 para のパラメータは、元のサブオブジェクトとそこから再帰的に計算された値の両方を取得します。

でうまく表現された関数の例です。 para はリストの適切な充足のコレクションです。

suff :: [x] -> [[x]]
suff = para (\ x xs suffxs -> xs : suffxs) []

ということで

suff "suffix" = ["uffix", "ffix", "fix", "ix", "x", ""]

もっと簡単なのは

safeTail :: [x] -> Maybe [x]
safeTail = para (\ _ xs _ -> Just xs) Nothing

は、"cons" ブランチが再帰的に計算された引数を無視し、単に末尾を返すというものです。遅延評価では、再帰的な計算は決して起こらず、tailは一定時間で抽出されます。

を定義することができます。 foldr を使って para を使うのは非常に簡単です。 para から foldr のようなものですが、確かに可能です。

foldr c n =       para  (\ x  xs  t ->           c x    t)       n
para  c n = snd . foldr (\ x (xs, t) -> (x : xs, c x xs t)) ([], n)

を定義するコツは para と foldr を再構築することです。 コピー を再構築することで、元のデータにはアクセスできなかったのに、各ステップで末尾のコピーにアクセスできるようになります。最後には snd は入力のコピーを破棄し、出力値だけを与えます。これはあまり効率的ではありませんが、表現力を重視するのであれば para は foldr . もし、この foldr -のエンコード版です。 para であれば safeTail は結局、要素ごとに末尾をコピーするため、線形時間がかかることになります。

というわけで、これで para はより便利なバージョンで foldr で、リストの末尾やそこから計算された値にすぐにアクセスすることができます。

一般的なケースでは，ファンクタの再帰的な固定点として生成されたデータ型を扱うことで

data Fix f = In (f (Fix f))

をお持ちの方

cata :: Functor f => (f         t  -> t) -> Fix f -> t
para :: Functor f => (f (Fix f, t) -> t) -> Fix f -> t

cata phi (In ff) = phi (fmap (cata phi) ff)
para psi (In ff) = psi (fmap keepCopy   ff) where
  keepCopy x = (x, para psi x)

であり、また、この二つは相互に定義可能であり、その中で para から定義されます。 cata を定義することができます。

para psi = snd . cata (\ fxt -> (In (fmap fst fxt), psi fxt))

もう一度 para よりも表現力がありません。 cata よりも表現力はありませんが、入力の部分構造に簡単にアクセスする必要がある場合にはより便利です。

編集する。 もう一ついい例を思い出しました。

で与えられる二分探索木を考えてみましょう。 Fix TreeF ここで

data TreeF sub = Leaf | Node sub Integer sub

で、二分探索木の挿入を定義してみると、最初は cata として、次に para . を見つけることができます。 para の方がずっと簡単だと思うでしょう。各ノードで、一方のサブツリーを挿入し、もう一方をそのまま維持する必要があるからです。