2

当我不了解 Haskell 中的表达式如何工作时，我经常发现将其分解为更基本的形式会有所帮助。

使用以下定义

sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs

instance Applicative ((->) r) where
    pure x = (\_ -> x)
    f <*> g = \x -> f x (g x)

我改写sequenceA [(+3),(+2)] 3为

(\_ -> (:)) <*> (+3) <*> ((\_ -> (:)) <*> (+2) <*> (\_-> [])) $ 3

然后把它变成（请原谅格式；我不确定分割线的约定是什么）

(\d ->(\c->(\b -> (\a -> (\_ -> (:)) a (+3) a) b (\_ -> (:)) b) c (+2) c) d (\_ -> []) d) 3

当我手动完成它时，这似乎是正确的，但我无法让 GHCi 接受它。我在这里做错了什么？我的第二个问题是如何从这种形式转换为功能组合。我试过用各种组合替换点，但 GHCi 拒绝所有这些....

4

3 回答 3

7

作为一个无所事事的闲人，我想我会做一台电脑来为我做扩展。所以进入 GHCi，我输入

let pu x = "(\\_ -> " ++ x ++ ")"
let f >*< a = "(\\g -> " ++ f ++ " g (" ++ a ++ " g))"

所以现在我有了有趣的版本，pure哪些<*>将看起来像表达式的字符串映射到看起来像更复杂的表达式的字符串。然后，我类似地定义了sequenceA用字符串替换函数的类似物。

let sqa [] = pu "[]" ; sqa (f : fs) = (pu "(:)" >*< f) >*< sqa fs

然后我能够生成示例的扩展形式，如下所示

putStrLn $ sqa ["(+3)","(+2)"] ++ " 3"

正式印刷

(\g -> (\g -> (\_ -> (:)) g ((+3) g)) g ((\g -> (\g -> (\_ -> (:)) g ((+2) g)) g  ((\_ -> []) g)) g)) 3

最后，复制到提示符，产生

[6,5]

将我的“元程序”的输出与问题中的尝试进行比较，发现 lambda 的初始前缀较短，这是由于<*>操作嵌套较浅而引起的。记住，是

(pure (:) <*> (+3)) <*> ((pure (:) <*> (+2)) <*> pure [])

所以外部(:)应该只有三个 lambdas 深。我怀疑提议的扩展可能对应于上述不同括号中的版本，也许

pure (:) <*> (+3) <*> pure (:) <*> (+2) <*> pure []

确实，当我评估

putStrLn $ pu "(:)" >*< "(+3)" >*< pu "(:)" >*< "(+2)" >*< pu "[]" ++ " 3 "

我明白了

(\g -> (\g -> (\g -> (\g -> (\_ -> (:)) g ((+3) g)) g ((\_ -> (:)) g)) g ((+2) g)) g ((\_ -> []) g)) 3

看起来它与（更新）匹配

(\d -> (\c -> (\b -> (\a -> (\_ -> (:)) a ((+3) a)) b ((\_ -> (:)) b)) c ((+2) c)) d ((\_ -> []) d)) 3

我希望这种机器辅助调查有助于澄清发生了什么。

于 2012-08-10T18:05:01.813 回答
4

您重写(\_ -> (:)) <*> (+3)为\a -> (\_ -> (:)) a (+3) a，这是重写f <*> g为f x g x而不是f x (g x)。我想你每个人都犯了这个错误<*>。

于 2012-08-10T17:25:57.200 回答
2

可能更容易使用组合符，例如_Sand _K，象征性地，而不是它们作为 lambda 表达式的定义，

_S f g x = f x (g x)
_K x y   = x

正如其他人已经提到的，对于函数，fmapis(.)和<*>is 。_S所以，

sequenceA [(+3),(+2)] 3 ==
    ( ((:) <$> (+3)) <*> sequenceA [(+2)]        ) 3  ==
    _S ((:).(+3))   ( ((:) <$> (+2)) <*> pure [] ) 3  ==
    _S ((:).(+3))   ( _S ((:).(+2))   (_K [])    ) 3  ==
       ((:).(+3)) 3 ( _S ((:).(+2))   (_K [])  3 )    ==
       ((:).(+3)) 3 (    ((:).(+2)) 3 (_K [] 3)  )    ==
    (6:) ( (5:) [] ) ==
    [6,5]

因此，将表达式分解为基本函数和组合子并停在那里（即不将它们分解为它们的 lambda 表达式）可能会更容易，使用它们的“重写规则”来操纵表达式以找到其更易于理解的形式。

如果你愿意，你现在可以为自己写下一个更抽象、更非正式的重写sequenceA规则

sequenceA [f,g,..., z] ==
    _S ((:).f) . _S ((:).g) . _S ..... . _S ((:).z) . _K []

所以

sequenceA [f,g,..., z] a ==
    ((:).f) a $ ((:).g) a $  ..... $ ((:).z) a $ _K [] a ==
    (f a:)    $ (g a:)    $  ..... $ (z a:)    $ []      ==
    [f a, g a, ..., z a]

因此

sequenceA fs a == map ($ a) fs == flip (map . flip ($)) fs a

以机智，

Prelude Control.Applicative> flip (map . flip ($)) [(+3),(+2)] 3
[6,5]
于 2012-08-11T19:51:31.417 回答