需要多少张fmap? [英] How many fmaps does it take?

问题描述

A

A comment by Daniel Wagner led me to this question. Let's start with an over-simplification. Suppose you have a type

data Foo a = Foo [a]

然后您可以编写Functor实例

instance Functor Foo where
  fmap f (Foo l) = Foo (fmap f l)

您可以将右侧重写为

Foo . fmap f $ l

认识到对于(->) a，fmap = (.)，您可以编写

Recognizing that for (->) a, fmap = (.), you can write it

fmap Foo (fmap f) l

重复，您得到

fmap (fmap Foo) fmap f l

所以，最后，

fmap f (Foo l) =
  fmap fmap fmap Foo fmap f l

---

如果您选择一个稍微复杂些的函子怎么办?

---

What if you pick a slightly more complex functor?

data Bar = Bar [Maybe a]

instance Functor Bar where
  fmap f (Bar l) = Bar (fmap (fmap f) l)

我开始手动执行此操作，但是它开始失去控制，所以我切换到自动.

I started doing this by hand, but it started to get out of control, so I switched to automatic.

infixl 9 :@
data Expr
  = BAR | F | L | FMap | Expr :@ Expr
  deriving (Show)

rewrite :: Expr -> Expr
rewrite (p :@ (q :@ r))
  = rewrite $ FMap :@ p :@ q :@ r
rewrite (p :@ q) = rewrite p :@ q
rewrite e = e

main = print $ rewrite $
  BAR :@ (FMap :@ (FMap :@ F) :@ L)

不幸的是，这似乎产生了巨大的结果.我什至无法在合理的时间内计算出树的最左边的叶子.这个表情到底有多大?随着更多函子的层叠，它会以多快的速度增长?

Unfortunately, this seems to produce an utterly enormous result. I couldn't even calculate the leftmost leaf of the tree in a reasonable amount of time. Just how big an expression does this make? How quickly does it grow as more functors are layered on?

推荐答案

无限.以下术语循环您的重写器:

Infinite. The following term loops your rewriter:

FMap :@ ((FMap :@ (FMap :@ FMap)) :@ FMap)

它只需三个步骤即可完成操作，

It does so in just three steps, which are:

((FMap :@ FMap) :@ (FMap :@ (FMap :@ FMap))) :@ FMap
(((FMap :@ (FMap :@ FMap)) :@ FMap) :@ (FMap :@ FMap)) :@ FMap
(((FMap :@ ((FMap :@ (FMap :@ FMap)) :@ FMap)) :@ FMap) :@ FMap) :@ FMap

这最后一个字是原始术语. (原始循环术语本身是在重写BAR :@ (FMap :@ (FMap :@ F) :@ L)的六个步骤之后产生的.)

This last has the original term at its head. (The original looping term itself arises after six steps of rewriting your BAR :@ (FMap :@ (FMap :@ F) :@ L).)

这篇关于需要多少张fmap?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！