Tôi 'đã phát minh ra' một lược đồ đệ quy, đó là sự khái quát hóa sự biến chất. Khi bạn gấp một cấu trúc dữ liệu với catamorphism bạn không có quyền truy cập vào subterms, chỉ để subresults của gấp:Việc triển khai thư viện của một lược đồ đệ quy
{-# LANGUAGE DeriveFunctor #-}
import qualified Data.Map as M
newtype Fix f = Fix { unFix :: f (Fix f) }
cata :: Functor f => (f b -> b) -> Fix f -> b
cata phi = self where
self = phi . fmap (\x -> self x) . unFix
Các chức năng gấp phi chỉ có quyền truy cập vào kết quả của self x, nhưng không phải để ban x. Vì vậy, tôi đã thêm một chức năng tham gia:
cataWithSubterm :: Functor f => (Fix f -> c -> b) -> (f b -> c) -> Fix f -> c
cataWithSubterm join phi = self
where self = phi . fmap (\x -> join x (self x)) . unFix
Bây giờ nó có thể kết hợp x và self x trong một cách có ý nghĩa, ví dụ sử dụng (,):
data ExampleFunctor a = Var String | Application a a deriving Functor
type Subterm = Fix ExampleFunctor
type Result = M.Map String [Subterm]
varArgs :: ExampleFunctor (Subterm, Result) -> Result
varArgs a = case a of
Var _ -> M.empty
Application ((Fix (Var var)), _) (arg, m) -> M.insertWith (++) var [arg] m
processTerm :: (ExampleFunctor (Subterm, Result) -> Result) -> Subterm -> Result
processTerm phi term = cataWithSubterm (,) phi term
processTerm varArgs lợi nhuận cho mỗi định danh sách các đối số thực tế nó nhận trên các đường dẫn điều khiển khác nhau. Ví dụ. cho bar (foo 2) (foo 5) nó trả về fromList [("foo", [2, 5])]
Lưu ý rằng trong kết quả ví dụ này được kết hợp thống nhất với các kết quả khác, vì vậy tôi mong đợi sự tồn tại của một thực hiện đơn giản hơn bằng cách sử dụng một thể hiện có nguồn gốc là Data.Foldable. Nhưng nói chung nó không phải là trường hợp như phi có thể áp dụng kiến thức của nó về cấu trúc bên trong của ExampleFunctor để kết hợp 'subterms' và 'subresults' theo những cách không thể với Foldable.
Câu hỏi của tôi là: Tôi có thể xây dựng processTerm sử dụng các chức năng cổ phiếu từ thư viện sơ đồ đệ quy hiện đại như recursion-schemes/Data.Functor.Foldable không?
cf. http://stackoverflow.com/questions/13317242/what-are-paramorphisms. –