Как mapA работает с функцией Stream Arrow в Haskell?

Фон

Я проходил через John Hughes Программирование со стрелками, и я чувствовал, что у меня все прямо в голове, пока следующее пример использования 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]]

Я ожидал бы, что "схема", в которой это приведет:

Diagram of Control Flow of mapA (delay 0)

В тех случаях, когда цифры обозначают части процесса:

  • Для любого непустого list x, listcase будет выдавать Right(x, xs). Для пустого списка listcase будет выдавать Left(), терминал.
  • Значения с тегами Right будут переданы в нижнюю часть. Значения с тегами Left будут переданы в const[], что существенно остановит итерацию.
  • При вводе (x, xs), x будет передан в (delay 0), а xs будет передан обратно на listcase.
  • Результат 3 будет (z, zs), который передается в uncurry (:), который присоединяет кортеж к списку.

Вот мое понимание потока, с входом [[1,2,3],[4,5,6],[7,8,9]]:

  • Первый проход

    • Right ([1,2,3],[[4,5,6],[7,8,9]])
    • ([1,2,3], [[4,5,6],[7,8,9]]) передается в нижнюю часть
    • (delay 0) вызывается на [1,2,3], что приводит к [0,1,2]. [[4,5,6],[7,8,9]] возвращается к listcase

  • Второй проход

    • Right ([4,5,6], [[7,8,9]])
    • ([4,5,6], [[7,8,9]]) передается в нижнюю часть
    • (delay 0) вызывается на [4,5,6], что приводит к [0,4,5]. [[7,8,9]] возвращается к listcase

  • Третий проход

    • Right ([7,8,9], [])
    • ([7,8,9], []) передается в нижнюю часть
    • (delay 0) вызывается на [7,8,9], что приводит к [0,7,8]. [] возвращается к listcase.

  • Четвертый проход

    • 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]]?

Ответы

Ответ 1

Я нахожу эти примеры хитрыми рассуждениями. В этом списке есть два списка Например, внешний список - это поток, который ваша стрелка работает, в то время как внутренние списки - это mapA карты. Рассмотрим более простой пример, чтобы мы на данный момент может игнорировать рекурсивный случай. Учитывая,

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

Мы видим, что первый шаг

  • Проводящий вход через стрелку listcase дает нам вывод [Right (1, []), Right (2, [])]. Первые элементы каждой пары подаются на стрелку delay 0, а вторые элементы подаются вернуться к mapA f.
  • Итак, мы имеем [1, 2] => delay 0 и [[], []] => mapA f. Подача [1,2] в delay 0 дает результат [0, 1] и загрузка пустых списков на mapA f дает больше пустых списков [[], []].

  • Эти два результата подаются на 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.