10

背景

我一直在阅读 John Hughes 的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)应该返回给我们一个接受[[a]]和返回的 SF 箭头[[b]]

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

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

mapA的控制流程图（延迟0）

数字标记过程部分的地方：

  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. Right ([1,2,3],[[4,5,6],[7,8,9]])
    2. ([1,2,3], [[4,5,6],[7,8,9]])被传递到下部
    3. (delay 0)被调用[1,2,3]，导致[0,1,2]. [[4,5,6],[7,8,9]]被传回listcase

  • 第二遍

    1. Right ([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. Right ([7,8,9], [])
    2. ([7,8,9], [])被传递到下部
    3. (delay 0)被调用[7,8,9]，导致[0,7,8]. []传回给listcase.

  • 第四关

    1. Left ()，掉在地上。

在这一点上，我们进入第 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]]？

4

1 回答 1

8

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

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

我们看到第一步

  1. listcase通过箭头 管道输入给我们输出[Right (1, []), Right (2, [])]。每对的第一个元素被反馈给delay 0箭头，而第二个元素被反馈给箭头mapA f。
  2. 所以，我们有那个[1, 2] => delay 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]])，而是 [Right (1, [2, 3]), Right (4, [5,6]), Right (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给出了输入列表的转置视图，因此您可以将其mapA (delay 0)视为类似 的操作 transpose . map (init . (0:)) . transpose，因为init . (0:)是 的定义delay。

于 2014-04-14T02:19:18.800 回答