避免在使用对递归方案时进行非穷举模式匹配

Question

下面是我编写的一些代码，作为使用来自recursion-schemes的recursion-schemes的练习(我知道这个简化的示例也可以使用cata来解决，但是对于这个问题，让我们忽略这一点)。

在执行此操作时，我注意到，如果要访问para构造函数的任何参数的表达式树，则必须在使用Depth时进行非穷尽模式匹配。

我找到了一个gcata'和para'的替代实现，它们没有这个问题，也不需要Comonad，而只需要w上的Functor实例。这让我不禁纳闷:为什么recursion-schemes的实现不使用这个版本？它有什么问题吗，还是有更好的方法来实现我想要的？

{-# 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

下面是一个如何使用它的例子：

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

如您所见，这两个函数执行相同的操作，计算树的最大深度(不包括最外层的depth调用本身)。

Answer 1

para是一个非常特殊的情况。

值得注意的是，它使用(,) (Mu f)作为Comonad的选择。

这个Comonad有比大多数更多的结构。

值得注意的是，它是与(,) e -| (->) e相伴的。

这有什么关系？好的，(,) e保存结肠，因此它只有一个a在里面。

这样你就可以不用使用g x <$ k x了--因为你只替换了一件东西！

对于更有趣的Comonad，您的gcata'应该会失败。

当要在a中替换多个w a时，就会丢弃信息，因此这将不是一个通用的递归方案。