6

我是 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]
4

3 回答 3

3

我认为它令人困惑的原因是因为你正在处理这个由内而外的工作，试图将内部绑定视为生成部分应用函数的列表。它没有：a并且b被关闭，而不是等待应用的参数。相反，从表达式的外部开始向内工作：

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

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

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

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

... return $ b * 10 + a

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

你问为什么 type of 与 type ofreturn $ b * 10 + a不同[40 + a, 50 + a, 60 + a]，但它们不是：两者都是 type [Int]。都不涉及任何功能。相反，它们都是数字列表，通过引用已经封闭的变量来构建。并且确实(>>=)具有它应该的类型：它需要一个 int 列表，以及一个用于从单个 int 生成 int 列表的函数，并返回一个不同的 int 列表：

(>>=) :: [Int] -> (Int -> [Int]) -> [Int]
于 2018-12-14T19:46:05.673 回答
2

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

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的定义：>>=returnpure

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

我们可以分解concatMap成concatand map：

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

现在我们可以减少它，我认为这就是你遇到困难的地方：减少是从外到内发生的，在这种情况下不会产生部分应用的函数；相反，它捕获 a内部 lambda 的闭包(\b -> …)。(\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
]

A case where you will see a list of partially applied functions is when using the Applicative instance of lists, for example, the equivalent to your code:

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

The definition of <$>/fmap for lists is just map, so we partially apply the first argument of the lambda, producing a list of type [Int -> Int], then (<*>) :: (Applicative f) => f (a -> b) -> f a -> f b, here at type [Int -> Int] -> [Int] -> [Int], applies each function in its left operand to each value in its right operand.

于 2018-12-15T07:20:33.110 回答
1

请记住这一点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]

没有部分应用的函数，只有一个函数使用其参数 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]
于 2018-12-14T19:46:52.840 回答