Unikaj niewyczerpującego dopasowania wzorców podczas korzystania z programu rekursji w stylu para

Question

Poniżej znajduje się kod, który napisałem jako ćwiczenie do korzystania z para z recursion-schemes (Wiem, że ten zredukowany przykład można również rozwiązać za pomocą tylko cata, ale zignorujmy to dla to pytanie).

Podczas tej czynności zauważyłem, że muszę wykonać niewyczerpujący wzorzec dopasowania, gdy używam para, jeśli chcę uzyskać dostęp do drzewa wyrażeń dowolnego z argumentów konstruktora Depth.

znalazłem alternatywną realizację gcata' i para' że nie ma tego problemu, a także nie wymagają Comonad, ale tylko Functor wystąpienie na w. Zastanawiam się: dlaczego ta wersja nie była używana w implementacji recursion-schemes? Czy coś jest z tym nie tak, czy też istnieją lepsze sposoby na osiągnięcie tego, czego szukam?

{-# LANGUAGE DeriveFunctor #-} 
{-# LANGUAGE ScopedTypeVariables #-} 
{-# LANGUAGE RankNTypes #-} 
module Test where 

import Data.Functor 
import Data.Functor.Foldable 

data ExprF a = Depth a a --^Counts the maximum depth of the tree 
      | Unit 
    deriving Functor 
type Expr = Fix ExprF 

unit :: Expr 
unit = Fix Unit 

depth :: Expr -> Expr -> Expr 
depth a b = Fix $ Depth a b 

evalDepth :: Expr -> Int 
evalDepth = cata phi where 
    phi Unit = 0 
    phi (Depth a b) = max a b + 1 

eval :: Expr -> Int 
eval = para phi where 
    phi Unit = 0 
    phi (Depth (Fix (Depth a b), _) _) = evalDepth a + evalDepth b 
--   ^^^^^^^^^^^^^^^ 
-- at this point is the whole *current* expression tree, not just 
-- the subtree that was given as first argument to `depth` 

-------------------------------------------------------------------------------- 
-- Is this possible without definining gcata'/para' myself with the current API? 

eval' :: Expr -> Int 
eval' = para' phi where 
    phi Unit = 0 
    phi (Depth (a,_) (b,_)) = evalDepth a + evalDepth b 
--   ^ ^
-- a and b are just the first and second argument to `depth`. No need 
-- to do a pattern match which might go wrong. 

gcata' :: forall t w a. (Foldable t, Functor w) 
     => (forall b. Base t (w b) -> w (Base t b)) 
     -> (Base t (w a) -> a) 
     -> t -> a 
gcata' k g = fst . c where 
    c :: t -> (a, w a) 
    c y = (g x, g x <$ k x) where 
    x :: Base t (w a) 
    x = fmap (snd . c) . project $ y 

para' :: (Foldable t, Unfoldable t) => (Base t (t,a) -> a) -> t -> a 
para' = gcata' distPara 

A oto przykład, jak z niego korzystać:

eval' (depth (depth unit unit) (depth (depth unit unit) unit) 
-- 3 
eval (depth (depth unit unit) (depth (depth unit unit) unit)) 
-- 3 

Jak widać, obie funkcje zrobić to samo, obliczania maksymalnej głębokości drzewa (nie licząc najbardziej zewnętrzną depth połączenia się)

Answer 1

para to bardzo szczególny przypadek.

W szczególności używa (,) (Mu f) jako wyboru z Comonad.

Ta Comonad ma o wiele więcej konstrukcji niż większość.

Należy zauważyć, że jest on złączony jako (,) e -| (->) e.

Dlaczego to ma znaczenie? Cóż, (,) e zachowuje kolimacje, a więc ma tylko jeden wewnętrzny element.

Dzięki czemu można uciec z g x <$ k x - ponieważ zastępujesz tylko jedną rzecz!

Dla każdego bardziej interesującego Comonad twoje gcata' powinno zawieść.

Gdy masz więcej niż jeden a do zastąpienia w w a, wyrzucasz informacje, więc nie będzie to uniwersalny schemat rekursji.