Leggendo questo classico documento , sono bloccato sui paramorfismi. Sfortunatamente la sezione è piuttosto sottile e la pagina di Wikipedia non dice nulla.
La mia traduzione di Haskell è:
para :: (a -> [a] -> b -> b) -> b -> [a] -> b para f base = h where h [] = base h (x:xs) = fx xs (h xs) Ma non lo bevo – non ho intuito per la firma del tipo o il risultato desiderato.
Cos’è un paramorfismo e quali sono alcuni esempi utili in azione?
Sì, ho visto queste domande , ma non trattano direttamente i paramorfismi e indicano solo risorse che possono essere utili come riferimenti, ma non come materiali di apprendimento.
Sì, questo è para . Confronta con il catamorfismo, o foldr :
para :: (a -> [a] -> b -> b) -> b -> [a] -> b foldr :: (a -> b -> b) -> b -> [a] -> b para cn (x : xs) = cx xs (para cn xs) foldr cn (x : xs) = cx (foldr cn xs) para cn [] = n foldr cn [] = n
Alcuni chiamano i paramorfismi “ricorsione primitiva” per contrasto con i catamorfismi (foldr) “iterazione”.
Laddove a due parametri di foldr viene assegnato un valore calcolato ricorsivamente per ogni suboggetti ricorsivo dei dati di input (qui, questa è la coda della lista), i parametri di para ottengono sia il subobject originale che il valore calcolato in modo ricorsivo da esso.
Una funzione di esempio che è ben espressa con para è la raccolta dei suffissi appropriati di una lista.
suff :: [x] -> [[x]] suff = para (\ x xs suffxs -> xs : suffxs) []
così che
suff "suffix" = ["uffix", "ffix", "fix", "ix", "x", ""]
Forse è ancora più semplice
safeTail :: [x] -> Maybe [x] safeTail = para (\ _ xs _ -> Just xs) Nothing
in cui il ramo “contro” ignora il suo argomento ricorsivamente calcolato e restituisce la coda. Valutato pigramente, il calcolo ricorsivo non avviene mai e la coda viene estratta in tempo costante.
Puoi definire foldr usando para abbastanza facilmente; è un po ‘più complicato definire para da foldr , ma è certamente ansible, e tutti dovrebbero sapere come è fatto!
foldr cn = para (\ x xs t -> cxt) n para cn = snd . foldr (\ x (xs, t) -> (x : xs, cx xs t)) ([], n)
Il trucco per definire para con foldr è ribuild una copia dei dati originali, in modo da ottenere l’accesso a una copia della coda ad ogni passaggio, anche se non abbiamo avuto accesso all’originale. Alla fine, snd scarta la copia dell’input e fornisce solo il valore di output. Non è molto efficiente, ma se sei interessato alla pura espressività, para ti dà solo foldr . Se si utilizza questa versione di para safeTail in safeTail , safeTail prenderà del tempo lineare dopo tutto, copiando l’elemento tail per elemento.
Quindi, questo è tutto: para è una versione più comoda di foldr che ti dà accesso immediato alla coda della lista così come il valore calcolato da essa.
Nel caso generale, funziona con un tipo di dati generato come fixpoint ricorsivo di un functor
data Fix f = In (f (Fix f))
hai
cata :: Functor f => (ft -> 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)
e ancora, i due sono mutuamente definibili, con para definito da cata dallo stesso trucco “make a copy”
para psi = snd . cata (\ fxt -> (In (fmap fst fxt), psi fxt))
Di nuovo, para non è più espressivo del cata , ma è più conveniente se hai bisogno di accedere facilmente alle sottostrutture dell’input.
Modifica: ho ricordato un altro bel esempio.
Considera gli alberi di ricerca binaria forniti da Fix TreeF dove
data TreeF sub = Leaf | Node sub Integer sub
e prova a definire l’inserimento per gli alberi di ricerca binari, prima come cata , poi come para . Troverai la versione para molto più semplice, poiché in ogni nodo dovrai inserire in una sottostruttura, ma conservare l’altra com’era.