haskell - mapA 如何与 Haskell 中的流函数 Arrow 配合使用？

Question

背景

我一直在浏览约翰休斯的Programming with Arrows ，我觉得我脑子里一切都很清楚，直到下面使用 mapA 的例子:

>runSF (mapA (delay 0)) [[1,2,3],[4,5,6],[7,8,9]]
[[0,0,0],[1,2,3],[4,5,6]]

其中 runSF 从 StreamFunction 箭头中提取流函数，定义为:

newtype SF a b = SF {runSF :: [a]->[b]}

延迟定义为:

delay x = SF (init . (x:))

SF 是 ArrowChoice 的一个实例(它声明了 mapA)，因此也是 Arrow 的一个实例。

我的理解

mapA :: arr a b -> arr [a] [b]
delay :: SF a b

这样delay只需在其第二个参数前面加上第一个参数即可。

因此，mapA (delay 0)应该返回一个SF箭头，它接受[[a]]并返回[[b]]

mapA (delay 0) :: SF [[a]] [[b]]

我希望这会导致的“电路”是:

其中数字标记流程的各个部分:

1. 对于任何非空 list x，listcase 将发出 Right(x, xs)。对于空列表，listcase 将发出 Left()，即终端情况。
2. 标记为Right的值将传递到下部。标记为 Left 的值将传递给 const[]，这实际上会停止迭代。
3. 输入 (x, xs) 时，x 将传递给 (delay 0)，而 xs > 将被传回 listcase。
4. 3 的输出将是 (z, zs)，它会传递给 uncurry (:)，后者将元组重新连接到列表中。

这是我对流程的理解，输入[[1,2,3],[4,5,6],[7,8,9]]:

• 第一遍

  1. 右 ([1,2,3],[[4,5,6],[7,8,9]])
  2. ([1,2,3], [[4,5,6],[7,8,9]]) 传递到下部
  在 [1,2,3] 上调用
  3. (delay 0)，生成 [0,1,2]。 [[4,5,6],[7,8,9]] 被传回 listcase

• 第二遍

  1. 右([4,5,6], [[7,8,9]])
  2. ([4,5,6], [[7,8,9]]) 传递到下部
  3. (delay 0) 在 [4,5,6] 上调用，结果为 [0,4,5]。 [[7,8,9]] 被传回 listcase

• 第三遍

  1. 右([7,8,9], [])
  2. ([7,8,9], []) 被传递到下部
  在 [7,8,9] 上调用
  3. (delay 0)，生成 [0,7,8]。 [] 被传回 listcase。

• 第四遍

  1. 向左 ()，掉在地板上。

此时，我们进入第 4 部分，它获取 3 的输出并将其连接在一起。我们本质上构建了以下操作:

[0,1,2] : [[0,4,5] : [[0,7,8] : []]]

这将为我们提供[[0,1,2],[0,4,5],[0,7,8]]。

我的困惑

显然，我的上述流程是错误的。

调用 runSF (mapA (delay 0)) [[1,2,3],[4,5,6],[7,8,9]] 会产生什么结果 [[0,0,0],[1,2,3],[4,5,6]]？

Answer 1

我发现这些例子很难推理。这里面有两个列表例如，外部列表是您的箭头操作的流，而内部列表是mapA 映射的内容。考虑一个更简单的例子，所以我们现在可以忽略递归情况。鉴于

runSF (mapA (delay 0)) [[1], [2]]

我们看到第一步

1. 通过 listcase 箭头输送输入即可得到输出[右(1，[])，右(2，[])]。每对的第一个元素被馈送到delay 0箭头，而第二个元素被馈送到返回mapA f。
2. 因此，我们有 [1, 2] => 延迟 0 和 [[], []] => mapA f。将 [1,2] 送入 delay 0 给出结果 [0, 1]，并且将空列表输入 mapA f 会产生更多空列表[[], []].

3. 这两个结果被输入到 arr (uncurry (:))，其作用类似于 zipWith (:)，由于这些函数都映射到列表上，因此它连接了两个输入按元素列出。

   [0,  1]
      |
      v
   arr (uncurry (:)) => [ 0:[], 1:[] ] == [[0], [1]]
      ^
      |
   [[], []]
   

关键是要认识到所有用 arr 构造的东西都可以在内部列表集，因此通过 arr listcase 运行初始输入不会产生 Right ([1,2,3],[[4,5,6],[7,8,9]])，但是[右(1, [2, 3])，右(4, [5,6])，右(7, [8,9])]。这是我尝试将其绘制在图表中。

     [Right (1, [2, 3]), Right (4, [5,6]), Right (7, [8,9])]
     =======================================================
                 |        [1, 4, 7]      +-----------+ [0, 1, 4]
  +----------+   |       +----=--------->|   delay   |-----=------|
  | listcase |---=------>|               +-----------+            |   +-------------------+
  +----------+           |                                        +-->| arr (uncurry (:)) |---> [[0,0,0],[1,2,3],[4,5,6]]
                         |                                        |   +-------------------+
                         |               +-----------+            |
                         +-------=------>|   mapA f  |------=-----|
                                 |       +-----------+      |
                                 |                          |
                          [[2,3],[4,5],[6,7]]         [[0,0], [2,3],[4,5]]
                                                      * what will be
                                                        returned if you
                                                        trace it through

抱歉，我无法画得更好。实际上，mapA 给出了转置 View 输入列表的，因此您可以将 mapA (delay 0) 视为如下操作转置 . map (初始化。(0:))。转置，因为 init 。 (0:) 是延迟的定义。