3

http://blog.sumtypeofway.com/recursion-schemes-part-2/の一部を読んだ (および実装した) 後 でも、関数の型がどのようにcata機能するのか疑問に思っています。cata関数は次のように定義されます。

mystery :: Functor f => (f a -> a) -> Term f -> a
mystery f = f . fmap (mystery f) . unTerm

のようなものがありTerm Exprます。開梱後、Expr (Term Expr). 代数 ( f) は、たとえば として定義されf :: Expr Int -> Intます。以下を簡単に呼び出すことができることはわかっています。

x = Literal "literal" :: Expr a
f :: Expr Int -> Int
f x :: Int

私はまた想像することができます：

x = Literal "literal" :: Expr (Term Expr)
f :: Expr a -> Int
f x :: Int

しかし、次のことはうまくいかないと思います：

x = Literal "literal" :: Expr (Term Expr)
f :: Expr Int -> Int
f x :: ???

ただし、cata関数でどのように機能するかはまだわかりませExpr (Term Expr)んExpr a。値が機能することは理解していますが、型がわかりません。ツリーの葉で何が起こるのでしょうか? これは確かにmystery...

編集：理解できないことをより明確に述べようとします。

精神的には、次のcataように機能するようです。

  • fmap f葉に適用します。
  • これで、持っているノードをExpr Int呼び出して、上に行くことができます。fmap f

私が申請しているので、明らかにこのようには機能しませんfmap (cata f)。ただし、最終的に関数は引数として (リーフで)f呼び出されます。Expr IntこのタイプExpr (Term Expr)は以前のものからどのように作られたのですか？

4

1 に答える 1

2

これはcata、葉でどのように動作するかです。

と仮定しf :: Expr Int -> Intます。それで：

cata f :: Term Expr -> Int
fmap (cata f) :: Expr (Term Expr) -> Expr Int

さて、任意の関数 に対してg :: a -> b、

fmap g :: Expr a -> Expr b
fmap g (Literal n) = Literal n
...

したがって、リテラルでgは重要ではありません。これは、 を選択a ~ Term Exprするとb ~ Int、g = cata f

fmap (cata f) (Literal n) = Literal n  :: Term Int
f (fmap (cata f) (Literal n)) = f (Literal n) :: Int

したがって、大まかに言えば、葉の上fmap (cata f)は何もしませんが、タイプを からExpr (Term Expr)に変更しExpr Intます。これは自明な変換Literal n :: Expr aですa。

于 2015-11-12T12:17:58.960 に答える