95

この古典的な論文を読んで、私はパラモルフィズムに固執しています。残念ながら、セクションは非常に薄く、ウィキペディアのページには何も書かれていません。

私のHaskellの翻訳は次のとおりです。

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

しかし、私はそれを理解していません-型署名や望ましい結果についての直感はありません。

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

はい、私はこれらの 質問を見ましたが、それらはパラモルフィズムを直接カバーしておらず、参考資料としては役立つかもしれないが、学習資料としては役に立たないかもしれないリソースを指しているだけです。

4

1 に答える 1

112

はい、そう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）が「反復」であるのとは対照的に、パラモルフィズムを「原始再帰」と呼びます。

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」ブランチは再帰的に計算された引数を無視し、テールを返すだけです。怠惰に評価され、再帰的な計算は決して行われず、テールは一定時間で抽出されます。

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を再構築することです。最後に、入力のコピーを破棄し、出力値のみを提供します。それはあまり効率的ではありませんが、あなたが純粋な表現度に興味があるなら、あなたにそれ以上のものを与えません。このエンコードされたバージョンのを使用する場合、結局のところ線形時間がかかり、要素ごとにテールをコピーします。sndparafoldrfoldrparasafeTail

これで、リストの末尾とそこから計算された値にすぐにアクセスできる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)

繰り返しになりますが、この2つは相互に定義可能であり、同じ「コピーを作成する」トリックによって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各ノードで1つのサブツリーに挿入する必要がありますが、他のサブツリーはそのままにしておく必要があるため、バージョンははるかに簡単です。

于 2012-11-09T23:34:22.483 に答える