做符号和绑定签名

Question

我是Haskell和函数式编程的新手,我想知道为什么这样的例子("嵌套循环")有效:

do
  a <- [1, 2, 3]
  b <- [4, 5, 6]
  return $ a * 10 + b

下面的一些东西是一种伪Haskell语法,但我希望它能说明我的理解.

这是我的理解,它变成了这样的东西

[1, 2, 3] >>= \a -> 
          ([4, 5, 6] >>= \b -> 
                     return $ b * 10 + a)

我想这个表达方式

[4, 5, 6] >>= \b -> return $ b * 10 + a

生成部分应用函数的列表

[[40 + a], [50 + a], [60 + a]]

连接到

[40 + a, 50 + a, 60 + a]

最后一步,看起来像这样

[1, 2, 3] >>= \a -> [40 + a, 50 + a, 60 + a]

变

[41, 51, 61, 42, 52, ... ]

我的困境是因为类型return $ b * 10 + a似乎与类型不同[40 + a, 50 + a, 60 + a].

绑定签名不应该像这样吗？

 (>>=)  :: m a -> (a -> m b) -> m b

在这个例子中似乎是这样的

[int] -> (int -> [int -> int -> int]) -> [int -> int]

和

[int] -> (int -> [int -> int]) -> [int]

Answer 1

Here\xe2\x80\x99是它如何脱糖和运行的。你\xe2\x80\x99是对的：

\n\n

do\n  a <- [1, 2, 3]\n  b <- [4, 5, 6]\n  return $ a * 10 + b\n

\n\n

对此进行脱糖：

\n\n

[1, 2, 3] >>= \\a -> \n  [4, 5, 6] >>= \\b -> \n    return $ b * 10 + a\n

\n\n

依次使用 的列表实例，我们可以内联其和（或）Monad的定义：>>=returnpure

\n\n

concatMap\n  (\\a -> concatMap\n    (\\b -> [b * 10 + a])\n    [4, 5, 6])\n  [1, 2, 3]\n

\n\n

我们可以分解concatMap为concat和map：

\n\n

concat\n  (map\n    (\\a -> concat\n      (map\n        (\\b -> [b * 10 + a])\n        [4, 5, 6]))\n    [1, 2, 3])\n

\n\n

现在我们可以减少这个，我认为这就是您遇到困难的地方：减少是从外向内发生的，并且在这种情况下不会产生部分应用的函数；相反，它捕获 a内部 lambda 的闭包(\\b -> \xe2\x80\xa6)。首先，我们(\\a -> \xe2\x80\xa6)映射[1, 2, 3]：

\n\n

concat\n  [ (\\a -> concat\n      (map\n        (\\b -> [b * 10 + a])\n        [4, 5, 6])) 1\n  , (\\a -> concat\n      (map\n        (\\b -> [b * 10 + a])\n        [4, 5, 6])) 2\n  , (\\a -> concat\n      (map\n        (\\b -> [b * 10 + a])\n        [4, 5, 6])) 3\n  ]\n\n==\n\nconcat\n  [ let a = 1\n    in concat\n      (map\n        (\\b -> [b * 10 + a])\n        [4, 5, 6])\n  , let a = 2\n    in concat\n      (map\n        (\\b -> [b * 10 + a])\n        [4, 5, 6])\n  , let a = 3\n    in concat\n      (map\n        (\\b -> [b * 10 + a])\n        [4, 5, 6])\n  ]\n

\n\n

然后我们可以减少内部maps：

\n\n

concat\n  [ let a = 1\n    in concat\n      [ (\\b -> [b * 10 + a]) 4\n      , (\\b -> [b * 10 + a]) 5\n      , (\\b -> [b * 10 + a]) 6\n      ]\n  , let a = 2\n    in concat\n      [ (\\b -> [b * 10 + a]) 4\n      , (\\b -> [b * 10 + a]) 5\n      , (\\b -> [b * 10 + a]) 6\n      ]\n  , let a = 3\n    in concat\n      [ (\\b -> [b * 10 + a]) 4\n      , (\\b -> [b * 10 + a]) 5\n      , (\\b -> [b * 10 + a]) 6\n      ]\n  ]\n\n==\n\nconcat\n  [ let a = 1\n    in concat\n      [ let b = 4 in [b * 10 + a]\n      , let b = 5 in [b * 10 + a]\n      , let b = 6 in [b * 10 + a]\n      ]\n  , let a = 2\n    in concat\n      [ let b = 4 in [b * 10 + a]\n      , let b = 5 in [b * 10 + a]\n      , let b = 6 in [b * 10 + a]\n      ]\n  , let a = 3\n    in concat\n      [ let b = 4 in [b * 10 + a]\n      , let b = 5 in [b * 10 + a]\n      , let b = 6 in [b * 10 + a]\n      ]\n  ]\n

\n\n

然后我们可以通过用变量的值替换变量来简化：

\n\n

concat\n  [ concat\n    [ [4 * 10 + 1]\n    , [5 * 10 + 1]\n    , [6 * 10 + 1]\n    ]\n  , concat\n    [ [4 * 10 + 2]\n    , [5 * 10 + 2]\n    , [6 * 10 + 2]\n    ]\n  , concat\n    [ [4 * 10 + 3]\n    , [5 * 10 + 3]\n    , [6 * 10 + 3]\n    ]\n  ]\n

\n\n

并减少对以下内容的调用concat：

\n\n

concat\n  [ [ 4 * 10 + 1\n    , 5 * 10 + 1\n    , 6 * 10 + 1\n    ]\n  , [ 4 * 10 + 2\n    , 5 * 10 + 2\n    , 6 * 10 + 2\n    ]\n  , [ 4 * 10 + 3\n    , 5 * 10 + 3\n    , 6 * 10 + 3\n    ]\n  ]\n\n==\n\n[ 4 * 10 + 1\n, 5 * 10 + 1\n, 6 * 10 + 1\n, 4 * 10 + 2\n, 5 * 10 + 2\n, 6 * 10 + 2\n, 4 * 10 + 3\n, 5 * 10 + 3\n, 6 * 10 + 3\n]\n

\n\n

当然还有个人的表达方式：

\n\n

[ 41, 51, 61\n, 42, 52, 62\n, 43, 53, 63\n]\n

\n\n

您将看到部分应用函数的列表的情况是在使用Applicative列表实例时，例如，相当于您的代码：

\n\n

(\\a b -> b * 10 + a) <$> [1, 2, 3] <*> [4, 5, 6]\n

\n\n

<$>列表的/的定义fmap只是map，因此我们部分应用 lambda 的第一个参数，生成类型 的列表[Int -> Int]，然后(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b，此处的类型[Int -> Int] -> [Int] -> [Int]，将其左操作数中的每个函数应用于其右操作数中的每个值。

\n