做符号和绑定签名

Question

我是 Haskell 和函数式编程的新手，我想知道为什么这样的示例（"nested loop"）有效：

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

我认为它令人困惑的原因是因为您正在从内到外处理这个问题，方法是尝试将内部绑定视为生成部分应用函数的列表。它不会：a 和 b 被关闭，而不是等待应用的参数。相反，从表达式的外部开始向内工作：

[1, 2, 3] >>= \a -> (...)

对于列表中的每个项目，以某种方式生成一个列表，可以访问 a 作为原始列表中项目的名称

... [4, 5, 6] >>= \b -> (...)

要生成上一步所需的列表，请生成一个可以访问 a 和 b 的新列表，两个编号列表各取一个。

... return $ b * 10 + a

要生成上一步所需的列表，请创建单个项目的列表，其值为b * 10 + a。

你问为什么 return $ b * 10 + a 的类型与 [40 + a, 50 + a, 60 + a] 的类型不同，但它们不是：两者都是 [Int] 类型。两者都不涉及任何功能。相反，它们都是数字列表，通过引用已经关闭的变量来构造。事实上 (>>=) 具有它应有的类型：它接受一个 int 列表和一个从单个 int 生成 int 列表的函数，并返回一个不同的 int 列表：

(>>=) :: [Int] -> (Int -> [Int]) -> [Int]

Answer 2

请记住列表 monad 中的 return x = [x] 和 xs >>= f = concatMap f xs。于是

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

变成

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

变成（a作为b函数中的自由变量）

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

没有部分应用的函数，只有一个函数 returns 一个列表值使用其参数 3 次不同的时间。然后减少到

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

或

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

Answer 3

以下是它的脱糖和运作方式。你说得对：

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

脱糖：

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

反过来使用 Monad 的列表实例，我们可以内联 >>= 和 return（或 pure）的定义：

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

我们可以将 concatMap 分解为 concat 和 map:

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

现在我们可以减少它了，我认为这里是你遇到困难的地方：减少是从外到内发生的，在这种情况下不会产生部分应用的功能；相反，它 在内部 lambda (\b -> …) 的闭包中捕获 a。首先，我们将 (\a -> …) 映射到 [1, 2, 3]:

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

==

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

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

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

==

concat
  [ let a = 1
    in concat
      [ let b = 4 in [b * 10 + a]
      , let b = 5 in [b * 10 + a]
      , let b = 6 in [b * 10 + a]
      ]
  , let a = 2
    in concat
      [ let b = 4 in [b * 10 + a]
      , let b = 5 in [b * 10 + a]
      , let b = 6 in [b * 10 + a]
      ]
  , let a = 3
    in concat
      [ let b = 4 in [b * 10 + a]
      , let b = 5 in [b * 10 + a]
      , let b = 6 in [b * 10 + a]
      ]
  ]

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

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

并减少对 concat 的调用：

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

==

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

当然还有个人表达：

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

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

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

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

做符号和绑定签名

do notation and bind signature

monads

haskell

do-notation