5

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

在执行此操作时，我注意到para如果我想访问Depth构造函数

我找到了 and 的替代实现，gcata'它para'没有这个问题，也不需要，Comonad而只是Functor. w这让我想知道：为什么没有在实现中使用这个版本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调用本身）

4

1 回答 1

8

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

值得注意的是，它(,) (Mu f)使用Comonad.

这Comonad比大多数结构都多。

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

为什么这很重要？很好(,) e地保留了colimits，因此它里面只有一个a。

所以你可以逃脱g x <$ k x- 因为你只更换一件事！

对于任何更有趣的事情，Comonad您gcata'都应该失败。

当您有多个a要替换 in 时w a，您会丢弃信息，因此这不是通用递归方案。

于 2014-07-12T21:17:22.950 回答