5

para以下は、 fromを使用するための練習として私が書いたコードですrecursion-schemes(この縮小された例はcata、 だけを使用して解決できることはわかっていますが、この質問ではこれを無視しましょう)。

これを行っているときに、コンストラクターparaへの引数のいずれかの式ツリーにアクセスしたい場合は、使用時に非網羅的なパターン マッチを行う必要があることに気付きました。Depth

この問題がなく、 を必要とせず、 のインスタンスだけを必要とするgcata'andの代替実装を見つけました。なぜこのバージョンが の実装に使用されなかったのか? 何か問題がありますか、それとも私が探しているものを達成するためのより良い方法がありますか?para'ComonadFunctorwrecursion-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保存されるため、その中に 1 つしかありませんa。

だからあなたは逃げることができますg x <$ k x- あなたは1つのものだけを交換しているので!

さらに興味深い場合は、失敗Comonadする必要があります。gcata'

aで置換するものが複数ある場合w a、情報を捨てているため、これは普遍的な再帰スキームにはなりません。

于 2014-07-12T21:17:22.950 に答える