MapA hoạt động như thế nào với một mũi tên chức năng luồng trong Haskell?

Question

nền

Tôi đã trải qua John Hughes Programming with Arrows, và tôi cảm thấy rằng tôi đã có tất cả mọi thứ thẳng trong đầu tôi cho đến ví dụ sau sử dụng MAPA:

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

đâu runSF chiết xuất chức năng suối từ StreamFunction mũi tên định nghĩa là:

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

Và chậm trễ được định nghĩa là:

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

SF là một thể hiện của ArrowChoice (khai báo mapA) và do đó là một thể hiện của Arrow.

Hiểu My

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

mà delay đơn giản prepends số thứ hai của mình với lần đầu tiên của nó.

Như vậy, mapA (delay 0) nên trả lại chúng tôi một mũi tên SF mà sẽ đưa [[a]] và trả [[b]]

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

Tôi hy vọng rằng các "mạch" rằng điều này sẽ gây ra là:

Trong đó các con số gắn nhãn các phần của quy trình:

1. Đối với bất kỳ ô trống nào list x, listcase sẽ phát ra Right(x, xs). Đối với danh sách trống, listcase sẽ phát ra Left(), vỏ thiết bị đầu cuối.
2. Giá trị được gắn thẻ Right sẽ được chuyển đến phần dưới. Giá trị được gắn thẻ Left sẽ được chuyển đến const[], về cơ bản dừng lặp lại.
3. Với đầu vào (x, xs), x sẽ được chuyển đến (delay 0), trong khi xs sẽ được chuyển ngược lại đến listcase.
4. Kết quả đầu ra của 3 sẽ là (z, zs), được chuyển đến uncurry (:), kết hợp bộ túp trở lại danh sách.

Dưới đây là sự hiểu biết của tôi về dòng chảy, với đầu vào [[1,2,3],[4,5,6],[7,8,9]]:

• Đầu tiên vượt qua

  1. Right ([1,2,3],[[4,5,6],[7,8,9]])
  2. ([1,2,3], [[4,5,6],[7,8,9]]) được truyền cho phần dưới
  3. (delay 0) được kêu gọi [1,2,3], res ulting in [0,1,2].[[4,5,6],[7,8,9]] được chuyển trở lại listcase

• Thứ hai vượt qua

  1. Right ([4,5,6], [[7,8,9]])
  2. ([4,5,6], [[7,8,9]]) được thông qua để phần dưới
  3. (delay 0) được kêu gọi [4,5,6], dẫn đến [0,4,5]. [[7,8,9]] được chuyển trở lại listcase

• Thứ ba đường chuyền

  1. Right ([7,8,9], [])
  2. ([7,8,9], []) được thông qua để phần dưới
  3. (delay 0) được kêu gọi [7,8,9], dẫn đến [0,7,8]. [] được trả về listcase.

• Thứ tư đường chuyền

  1. Left(), giảm trên sàn nhà.

Tại thời điểm này, chúng tôi nhận đến phần 4, trong đó có sản lượng 3 và concats nó tất cả cùng nhau. Chúng tôi về cơ bản xây dựng của một hoạt động của:

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

nào sẽ cung cấp cho chúng tôi [[0,1,2],[0,4,5],[0,7,8]].

Lẫn lộn của tôi

Rõ ràng, lưu lượng trên của tôi sai.

Làm thế nào để gọi runSF (mapA (delay 0)) [[1,2,3],[4,5,6],[7,8,9]] kết quả trong [[0,0,0],[1,2,3],[4,5,6]]?

Answer 1

Tôi thấy các ví dụ này khó hiểu. Có hai danh sách trong ví dụ này, danh sách bên ngoài là luồng mà mũi tên của bạn hoạt động trên, trong khi các danh sách bên trong là những gì mapA ánh xạ. Hãy xem xét một ví dụ đơn giản hơn vì vậy chúng tôi có thể bỏ qua trường hợp đệ quy ngay bây giờ. Với

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

Chúng tôi nhận thấy rằng bước đầu tiên

1. Piping đầu vào thông qua listcase mũi tên cho chúng ta kết quả [Right (1, []), Right (2, [])]. Các phần tử đầu tiên của mỗi cặp được cấp cho mũi tên delay 0, trong khi các phần tử thứ hai được cấp quay lại mapA f.
2. Vì vậy, chúng tôi có [1, 2] => delay 0 và [[], []] => mapA f. Ăn [1,2] vào delay 0 cho kết quả [0, 1] và cho các danh sách trống vào mapA f cho ra nhiều danh sách trống hơn [[], []].

3. Hai kết quả này được cấp cho arr (uncurry (:)), hoạt động như zipWith (:), vì các chức năng này được ánh xạ trên danh sách, vì vậy nó tham gia hai đầu vào liệt kê thành phần.

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

Điều quan trọng là phải nhận ra rằng tất cả những thứ được xây dựng với arr hoạt động trên bộ bên trong các danh sách, vì vậy chạy đầu vào ban đầu của bạn thông qua arr listcase không sản xuất Right ([1,2,3],[[4,5,6],[7,8,9]]), nhưng [Right (1, [2, 3]), Right (4, [5,6]), Right (7, [8,9])]. Đây là nỗ lực của tôi để vẽ nó ra trong một sơ đồ.

 [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 

Rất tiếc, tôi không thể vẽ điều này tốt hơn. Trong thực tế, mapA cho một cái nhìn hoán của danh sách đầu vào, vì vậy bạn có thể nghĩ đến mapA (delay 0) như hoạt động như transpose . map (init . (0:)) . transpose, vì init . (0:) là định nghĩa của delay.