36

我相信我对fmap . fmapFunctor 有所了解,但在功能上,这几个月来一直让我头疼。

我已经看到您可以只应用(.)to的定义(.) . (.),但我忘记了如何做到这一点。
当我自己尝试时,结果总是错误的:

(.) f g = \x -> f (g x)
(.) (.) (.) = \x -> (.) ((.) x)
\x f -> (.) ((.) x) f
\x f y  -> (((.)(f y)) x)
\x f y g-> (((.)(f y) g) x)
\x f y g-> ((f (g y)) x)
\x f y g-> ((f (g y)) x):: t2 -> (t1 -> t2 -> t) -> t3 -> (t3 -> t1) -> t

如果“仅应用定义”是这样做的唯一方法,那么有人是怎么想出的(.) . (.)
我必须缺少一些更深层次的理解或直觉。

4

5 回答 5

38

想出(.) . (.)实际上非常简单,它所做的事情背后的直觉很难理解。

(.)|在将表达式重写为“管道”样式计算(想想在 shell 中)时让你走得很远。但是,一旦您尝试将一个接受多个参数的函数与一个只接受一个参数的函数组合在一起,使用起来就会变得很尴尬。例如,让我们定义concatMap

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f xs = concat (map f xs)

摆脱xs只是一个标准的操作:

concatMap f = concat . map f

但是,没有摆脱f. 这是由一个事实引起的,它map需要两个参数,我们想应用concat它的最终结果。

您当然可以应用一些无点技巧并摆脱困境(.)

concatMap f = (.) concat (map f)
concatMap f = (.) concat . map $ f
concatMap = (.) concat . map
concatMap = (concat .) . map

但是很可惜,这段代码的可读性几乎没有了。相反,我们引入了一个新的组合器,它完全符合我们的需要:将第二个函数应用于第一个函数的最终结果

-- .: is fairly standard name for this combinator
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(f .: g) x y = f (g x y)

concatMap = concat .: map

好吧,这就是动力。让我们开始点免费业务。

(.:) = \f g x y -> f (g x y)
     = \f g x y -> f ((g x) y)
     = \f g x y -> f . g x $ y
     = \f g x   -> f . g x

现在,有趣的部分来了。这是另一个在您遇到困难时通常会有所帮助的无点技巧:我们将.其重写为前缀形式并尝试从那里继续。

     = \f g x   -> (.) f (g x)
     = \f g x   -> (.) f . g $ x
     = \f g     -> (.) f . g
     = \f g     -> (.) ((.) f) g
     = \f       -> (.) ((.) f)
     = \f       -> (.) . (.) $ f
     =             (.) . (.)

至于直觉,你应该阅读这篇非常好的文章。我将解释以下部分(.)

让我们再想想我们的组合器应该做什么:它应该应用于f结果结果g一直在故意使用最终结果,当你完全应用时,这真的是你得到的 - 模统一类型变量与另一个函数类型 -g函数,这里的结果只是g x一些应用程序x)。

应用于结果f对我们意味着什么?好吧,一旦我们应用了某个值,我们就会把结果应用到它上面。听起来很熟悉:就是这样。ggf(.)

result :: (b -> c) -> ((a -> b) -> (a -> c))
result = (.)

现在,事实证明这些组合器的组合(我们单词)只是一个函数组合,即:

(.:) = result . result -- the result of result
于 2013-02-22T18:12:02.663 回答
20

您也可以使用您对fmap . fmap.

如果你有两个Functorsfoobar,那么

fmap . fmap :: (a -> b)  ->  foo (bar a)    ->   foo (bar b)

fmap . fmapFunctor接受一个函数并为两个s的合成产生一个诱导函数.

现在,对于任何类型t,(->) t是 a Functor,而fmapfor thatFunctor(.)

对于两个s 是(.) . (.)and的情况也是如此,因此fmap . fmapFunctor(->) s(->) t

(.) . (.) :: (a -> b) -> ((->) s) ((->) t a) -> ((->) s) ((->) t b)
          =  (a -> b) -> (s -> (t -> a))     -> (s -> (t -> b))
          =  (a -> b) -> (s ->  t -> a )     -> (s ->  t -> b )

它“组合”了f :: a -> b一个具有两个参数的函数的函数g :: s -> t -> a

((.) . (.)) f g = \x y -> f (g x y)

该观点还清楚地表明,该模式以及如何扩展到接受更多参数的函数,

(.)             :: (a -> b) -> (s ->           a) -> (s ->           b)
(.) . (.)       :: (a -> b) -> (s -> t ->      a) -> (s -> t ->      b)
(.) . (.) . (.) :: (a -> b) -> (s -> t -> u -> a) -> (s -> t -> u -> b)

等等

于 2013-02-22T18:38:32.313 回答
5

当您引入y. 它应该是

\x f y -> ((.) ((.) x) f) y     :: (c -> d) -> (a -> b -> c) -> a -> b -> d
\x f y z -> ((.) ((.) x) f) y z :: (c -> d) -> (a -> b -> c) -> a -> b -> d
\x f y z -> ((.) x (f y)) z     :: (c -> d) -> (a -> b -> c) -> a -> b -> d
-- Or alternately:
\x f y z -> (x . f y) z         :: (c -> d) -> (a -> b -> c) -> a -> b -> d
\x f y z -> (x (f y z))         :: (c -> d) -> (a -> b -> c) -> a -> b -> d

与原始类型签名匹配:(.) . (.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d

(在 ghci 中进行扩展是最简单的,您可以在其中检查每个步骤:t expression

编辑:

更深层次的直觉是:

(.)被简单地定义为

\f g -> \x -> f (g x)

我们可以简化为

\f g x -> f (g x)

因此,当您为其提供两个参数时,它会被柯里化,并且仍然需要另一个参数来解决。每次使用(.)2 个参数时,都会为另一个参数创建一个“需要”。

(.) . (.)当然只是(.) (.) (.),所以让我们扩展它:

(\f0 g0 x0 -> f0 (g0 x0)) (\f1 g1 x1 -> f1 (g1 x1)) (\f2 g2 x2 -> f2 (g2 x2))

f0我们可以对and进行 beta-reduce g0(但我们没有x0!):

\x0 -> (\f1 g1 x1 -> f1 (g1 x1)) ((\f2 g2 x2 -> f2 (g2 x2)) x0) 

将第二个表达式替换为f1...

\x0 -> \g1 x1 -> ((\f2 g2 x2 -> f2 (g2 x2)) x0) (g1 x1) 

现在它“倒转”了!(beta-reduction on f2):
这是一个有趣的步骤 -x0被替换f2- 这意味着x原本可能是数据的 ,而是一个函数。
就是(.) . (.)提供额外参数的“需要”。

\x0 -> \g1 x1 -> (\g2 x2 -> x0 (g2 x2)) (g1 x1) 

这开始看起来很正常......让我们最后一次(on g2)进行beta-reduce:

\x0 -> \g1 x1 -> (\x2 -> x0 ((g1 x1) x2))

所以我们只剩下简单的

\x0 g1 x1 x2 -> x0 ((g1 x1) x2)

,其中论点仍然井然有序。

于 2013-02-22T17:59:29.383 回答
3

最简单的方法是写equationscombinators-style,而不是 lambda-expressions:a b c = (\x -> ... body ...)等价于a b c x = ... body ...,反之亦然,前提是x没有出现在{a,b,c}. 所以,

-- _B = (.)  

_B f g x = f (g x)
_B _B _B f g x y = _B (_B f) g x y
                 = (_B f) (g x) y
                 = _B f (g x) y
                 = f ((g x) y)
                 = f (g x y)

f (g x y)如果你想将它转换为组合形式(去掉所有括号和变量重复) ,你会发现这一点。然后你应用与组合器的定义相对应的模式,希望向后追溯这个推导。不过,这要少得多机械/自动。

于 2013-02-22T18:02:18.210 回答
3

所以,这就是我进行稍微增量扩展时得到的结果

(.) f g   = \x -> f (g x)
(.) . g   = \x -> (.) (g x)
          = \x -> \y -> (.) (g x) y
          = \x -> \y -> \z -> (g x) (y z)
          = \x y z -> (g x) (y z)
(.) . (.) = \x y z -> ((.) x) (y z)
          = \x y z -> \k -> x (y z k)
          = \x y z k -> x (y z k)

其中,根据 ghci 具有正确的类型

Prelude> :t (.) . (.)
(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c
Prelude> :t \x y z k -> x (y z k)
\x y z k -> x (y z k)
  :: (t1 -> t) -> (t2 -> t3 -> t1) -> t2 -> t3 -> t
Prelude> 

虽然我不知道这个组合器的起源,但它很可能是为组合逻辑而开发的,在组合逻辑中你严格使用组合器,所以你不能使用更方便的 lambda 表达式来定义事物。可能有一些直觉可以解决这些问题,但我还没有找到。最有可能的是,如果你必须做得足够多,你会发展出某种程度的直觉。

于 2013-02-22T17:58:09.077 回答