我几周前刚开始学习Haskell,看到了这个:
moves = do
f <- [(+), subtract]
g <- [(+), subtract]
(x, y) <- [(1, 2), (2, 1)]
[f x *** g y]
我以前没见过以 list
结尾的 do
代码块,这是解决骑士巡游问题的一部分。有人能解释一下它的工作原理吗?
您需要将符号写成解释性的形式。首先,从类型开始:
import Control.Arrow
moves :: [(Integer, Integer) -> (Integer, Integer)]
moves = do
f <- [(+), subtract]
g <- [(+), subtract]
(x, y) <- [(1, 2), (2, 1)]
[f x *** g y]
所以我们在 []
(列表)单子中。
查找 Monad [] 的定义:
instance Monad [] where
m >>= k = foldr ((++) . k) [] m
m >> k = foldr ((++) . (\ _ -> k)) [] m
return x = [x]
将do表示法翻译为bind和return:
moves =
[(+), subtract] >>= \f ->
[(+), subtract] >>= \g ->
[(1, 2), (2, 1)] >>= \(x,y) ->
[f x *** g y]
通过在列表上使用return
。
moves =
[(+), subtract] >>= \f ->
[(+), subtract] >>= \g ->
[(1, 2), (2, 1)] >>= \(x,y) ->
return (f x *** g y)
>>= 的定义
moves =
foldr ((++) . (\f ->
[(+), subtract] >>= \g ->
[(1, 2), (2, 1)] >>= \(x,y) ->
return (f x *** g y)
)) [] [(+), subtract]
Definition of >>=
moves =
foldr ((++) . (\f ->
foldr ((++) . (\g ->
[(1, 2), (2, 1)] >>= \(x,y) ->
return (f x *** g y))
) [] [(+), subtract]
)) [] [(+), subtract]
Definition of >>=
moves =
foldr ((++) . (\f ->
foldr ((++) . (\g ->
foldr ((++) . (\(x,y) -> return (f x *** g y))
) [] [(1, 2), (2, 1)]
)) [] [(+), subtract]
)) [] [(+), subtract]
moves =
foldr ((++) . (\f ->
foldr ((++) . (\g ->
foldr ((++) . (\(x,y) -> [f x *** g y])
) [] [(1, 2), (2, 1)]
)) [] [(+), subtract]
)) [] [(+), subtract]
因此,您可以看到这是两个元素列表上的嵌套折叠。展开折叠留给读者练习 :)
foldr
展开后的版本难以理解。我不明白它如何帮助那些不知道发生了什么的人。 - amalloy(++) . (\f -> ...)
,最多也只会引发这样的问题:“为什么这不会触发类型错误?” - chiconcatMap f
而不是foldr ((++) . f) []
可能会更容易理解。 - David Young
moves = [f x *** g y | f <- [(+), subtract], g <- [(+), subtract], (x, y) <- [(1, 2), (2, 1)]]
。 - Johannes Kuhn[x] = return x
。 - felix-eku