하스켈에서 mapA는 스트림 함수 화살표로 어떻게 작동합니까?

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는 (mapA를 선언하는) ArrowChoice의 인스턴스이며 따라서 Arrow의 인스턴스입니다.

delay 단순히 첫 번째와 두 번째 인자를 앞에 추가

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

있도록 내 이해.

따라서, mapA (delay 0)은 우리에게 [[b]]

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

나는이 초래하는 "회로"이라고 기대를 [[a]]를 받아 반환하는 SF 화살표를 반환해야합니다 :

숫자가 프로세스의 일부에 레이블을 붙이는 곳 :

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 (:)으로 전달되며, 튜플을 다시 목록에 조인합니다. 아래 부분
5. (delay 0)에 전달
   1. Right ([1,2,3],[[4,5,6],[7,8,9]])
   2. ([1,2,3], [[4,5,6],[7,8,9]]) 가져가 호출됩니다

      • 첫 번째 패스 :

   여기에 입력 [[1,2,3],[4,5,6],[7,8,9]]으로, 흐름에 대한 이해의 [1,2,3], res ulting in [0,1,2].[[4,5,6],[7,8,9]]는 [0,4,5] 결과 [4,5,6]에서 호출 하부

6. (delay 0)에 전달되는 listcase

번째 패스

1. Right ([4,5,6], [[7,8,9]])
2. ([4,5,6], [[7,8,9]])로 다시 전달된다. [[7,8,9]]는 [0,7,8] 결과 [7,8,9]에서 호출 하부
3. (delay 0)에 전달되는 listcase

번째 패스

1. Right ([7,8,9], [])
2. ([7,8,9], [])로 다시 전달된다. []은 listcase으로 다시 전달됩니다.
   1. Left()

3. 네 번째는, 바닥에 떨어 뜨렸다. 이 시점에서

, 우리는 (3)의 출력을 소요하고 모두 함께 concats 제 4 부에 도착. 우리는 본질적으로의 동작의 구축 :

[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가 매핑하는 대상입니다. 더 간단한 예제를 고려하면 은 지금 재귀 적 케이스를 무시할 수 있습니다. 우리는 listcase 화살표를 통해 입력을 배관 첫 번째 단계

1. 우리에게 출력 [Right (1, []), Right (2, [])]을주는 것을 볼

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

   을 감안할 때. 각 쌍의 첫 번째 요소 은 delay 0 화살표로 보내지 만 두 번째 요소는 을 mapA f으로 다시 입력합니다.
2. 그래서 우리는 [1, 2] => delay 0과 [[], []] => mapA f입니다.delay 0에 [1,2] 먹이 는 mapA f 수율 이상의 빈리스트 [[], []]에 빈리스트를 공급하는 결과 [0, 1] 및 을 준다. 그 두 개의 입력 리스트 엘리먼트 와이즈 결합되도록

3. 그 두 결과,이 기능은 모든 목록에 매핑되므로 zipWith (:), 같은 역할을하는 arr (uncurry (:))에 공급된다.

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

의 핵심은 너무 Right ([1,2,3],[[4,5,6],[7,8,9]])하지만 [Right (1, [2, 3]), Right (4, [5,6]), Right (7, [8,9])]을 생성하지 않습니다 arr listcase 를 통해 초기 입력을 실행 arr로 구성 모든 물건 에 목록의 내부 세트를 운영하고 있다는 것을 인식하는 것입니다. 이것은 다이어그램에서 그려 내 시도입니다.

 [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 입력 목록의 전치보기 을 제공하므로 init . (0:)이 delay의 정의이기 때문에 당신은 transpose . map (init . (0:)) . transpose 같은 동작으로 mapA (delay 0) 생각할 수 있습니다.