Arrow로 함수 컴비네이션 (작성 중)

Posted on September 14, 2023

함수형은 여러 개의 함수들을 합성compose해서 프로그램을 만들어 갑니다. Arrow는 타입에 상관없이(a -> b형태는, a -> m b 형태든…), 합성하는 인터페이스를 통일하자는 것이니, 함수형의 근간을 이루는 구조, 패턴이 아닌가 싶은데, 실상은 모나드만큼 인기리에 쓰이고 있는 것처럼 보이진 않습니다. (제 기준으론 외모도 모나드의 do만큼 깔끔하게 똑 떨어지진 않습니다.) 이론들이 단 몇 년만에 도입되어 폭발적으로 쓰이거나 그러진 않으니, 아직도 서서히 성장 중인 걸지도 모르겠습니다. FRP 라이브러리나(Yampa), GUI 라이브러리(Fruit)등, 도입한 라이브러리가 꽤 있고, 다른 언어에서도 FRP 구현에선 중요한 역할을 하고 있는 이론인가 봅니다. 모나드를 대체하거나 하는 구조가 아니라, 특정 조건하에서는, 모나드보다 더 적합한 경우가 있다고 합니다.

공부하면서 계속 원문과 노트를 같이 넣다보니 글이 많이 길어졌습니다. 아마도 보실 분들은 거의 없을텐데요. Arrow를 공부하다 막히는 부분이 있을 때, 다른 관점은 없나 궁금할 때 Ctrl-F로 찾아보면 좋을 듯 합니다.

전체적인 글은 다음 순서로 흘러 갑니다.

모나드를 일반화하자.
(>>>), arr 로 모나딕 작업과 아닌 작업을 인터페이스를 같게 만든다.
위 두 개만으론, 바인드처럼 작업하는데 부족함이 있다.
first 를 추가한다. 2-튜플의 앞에 것에만 작업을 한다는 것만으로 어찌 중간 단계의 값에 접근 할 수 있을까?
모나드가 할 수 있는 일은 다 할 수있고, 모나드가 못하는 일도 할 수 있다.
(꼭 그렇지는 않다고 합니다. List 모나드나 Cont 모나드 같은 건 Arrow로 표현하기 어렵다고 합니다.)

Programming with Arrows - John hughes
위 텍스트를 읽으면서 가졌던 의문들과 알게된 답을 같이 적었습니다.

모나드의 일반화? Arrow에 join이 있나?
없습니다.
Arrow >>> Arrow >>> Arrow 이런 식이면, 모나드처럼 동적인 Arrow는?
Arrow를 위한 모나드 인스턴스를 만들 수 있습니다.
Arrow는 클로저를 안 쓰는데, 체인에서 각 단계의 결과를 개 별 접근하려면?
튜플을 이용해서 중간 단계의 값을 저장할 수 있습니다.

생각 스트레칭

타입이 할 수 있는 일(검증 안된 혼자 상상입니다.)

수학이 강한 분들은, 아래 같은 얘기를 별로 안 좋아하는 경우가 있습니다. 너무 “인문학”스럽게 접근하는 걸로 보이나 봅니다. 전, 논리적으로 딱 맞아 떨어져도, 아래 같은 이해를 하지 못하면 현실을 모델링할 때 써먹질 못합니다. 여하튼, 그다지 환영 받는 얘기는 아니니, 적당히 한 귀로 흘리시면서 보세요.

Int, Char같은 프리미티브 타입이 아니라, 프로그래머가 만들어내는 타입들에 관한 얘기입니다.

data Some a = Some a

Some 타입같은 것을 볼 때, Some a가 아니라 Some _으로 보는게 편합니다. Some을 벗겨 보기 전엔 안에 뭐가 들어 있을지 알 수 없습니다. 또는 다른 시각에서 보면, a에 접근하려면 반드시 특정 절차가 필요할 경우 Some a로 만들면 됩니다. 죽었다 깨나도 Some을 열어 보기 전에는 a에 도달할 수 없습니다. 제가 눈여겨 보는 속성은, 값에 도달하려면 반드시 거쳐야 하는 한 단계 절차 를 가지고 있다는 것입니다. 타입 생성자로 쌓여 있는 것은, 말 그대로 언젠가 생성construct한다는 동작이 들어가 있습니다.

이런 저런 함수들을 붙여가며 작업을 하게 되는데, 따로 함수를 두지 않고, 타입으로 만들고, 함수로 할 일을 생성자나 메소드로 작성 해 놓으면, 해당 타입에서 값을 뽑아낼 때 마치 반드시 일어날 수 밖에 없는 디폴트 작업을 추가해 놓는 것과 비슷합니다. 또 다른 효과로, 타입으로 가려 두면(감싸 놓으면), 실행을 미루는 효과도 납니다. 나중에 타입을 벗겨내면서 예정했던 동작은 반드시 일어나니, 그 전에 신경쓰면서 잊지 않고 필요한 동작을 빠뜨리지 않았는지 신경 쓸 필요도 없습니다.

코드 조립할 때 단순히 조각들이 만나는 부분들이, 아귀(타입 매칭)가 잘 맞는지 보는 간단한 용도를 넘어, 타입은 볼 수록 여러 능력들을 가지고 있습니다.

타입이 표현력이 좋을까? 함수가 표현력이 좋을까?

A가 하는 일을 포함해서 B가 더 많은 일을 할 수 있다면, A보다 B가 표현력이 좋다는 뜻에서 표현력이 좋다라는 문장을 썼습니다.

a -> b 와 data SomeType a b = SomeType (a -> b)를 비교하면,
applySome (SomeType f) a = f a라는 함수나 메소드를 준비해 놓으면, a -> b가 할 수 있는 일은 모두 할 수 있으며, 추가로 연계된 메소드를 둘 수도 있고,
specialApplySome (SomeType f) a = 추가 작업 후 f a 등으로 함수를 적용할 때 항상 해야만 하는 일을 심어 둘 수도 있습니다. 이런 의미에서 전 타입이 더 표현력이 좋다 생각합니다.

타입이 함수의 일반화가 아닌가 생각한 적이 있는데요, 텍스트도 그리 말하는 곳이 없고, 가끔 저와 대화를 하는 분들 모두 “일반화”라고까지 말할 순 없다라고들 합니다. 저는 Int 타입이라고 하면 Class DoNothing의 인스턴스이거나, 특별한 메소드를 갖고 있지 않거나, 생성자 자체도 특별한 일을 하진 않는 함수로, Value에 접근 할 때 “아무것도 안하는 함수”를 실행하는 함수의 확장 정도로 보는 경우를 상상해 봤습니다. 그다지 그럴싸한 생각은 아닌가 봅니다. 이런 잡스러운 생각이, Arrow 인터페이스가 왜 모나드 인터페이스보다 표현력이 좋을까를 생각할 때 전 도움이 됐습니다.

함수를 타입으로 감싸서 얻는 이득

함수를 래핑해서 별도의 인터페이스(컴비네이터)를 만들어 두면 얻을 수 있는, 기능 예시를 보겠습니다.

하스켈은 순수 함수만 있어, 인자로 넘어 오지 않으면 쓰질 못합니다. 전역 변수를 쓸 수 있는 순수하지 않은 상황에서, 함수를 합성해서 체인을 만들어 두는데, 각 함수들이 만들어 낸 결과들을 모두 개별로 유지할 필요가 있는 경우를 생각해 보면,

globalRes1;
globalRes2;
globalRes3;

chain init {
  globalRes1 = func1 init 
  globalRes2 = func2 globalRes1
  globalRes3 = func3 globalRes2
}

another {
  globalRes1 + globalRes2 + globalRes3  
}

(억지스럽긴 하지만) 대비 되게 보면 이런 식의 코드도 가능하겠지만, 순수 함수만 있는 동네에선 불가능합니다. 순수 함수로만 해결하려면,

“결국, 필요한 정보는 다 가지고 다니는 수밖에 없습니다.”

단, 결과값에만 신경쓸 수 있도록, 추가적인 정보(컨텍스트)를 가지고 다니는 건 눈에 잘 안 보이게 해주는 패턴이 필요합니다. 모나드 바인드에선 람다 함수의 클로저가 이 역할을 합니다.

\x -> \y -> x + y
            ^^^^^
            이 식에서 x를 쓸 수 있어야 편하게 구현할 수 있습니다.

함수를 그냥 합성하지 않고, 합성할 때마다 모나드의 바인드처럼 추가 정보를 잃어버리지 않게 차곡 차곡 챙기려면 어떻게 할까요? 순수 함수만 있는 동네에선 2-튜플이 중요한 수단입니다. (결과값, 추가 정보) 형태로 추가 정보를 잃어버리지 않게 넣어 놓는 방법이 있습니다. 2-튜플을 쓰지 않는다면, 별도의 프로덕트 타입을 만들어서 해결해도 되는데, 이미 준비되어 있는 가장 단순한 2-튜플이 있으니, 이 걸 쓰면 됩니다. 아래 의사 코드를 보겠습니다.

chain init {
  res1 = Arrow1 init
  res2 = Arrow2 res1 (혹은 init)
  return (res1, res2)
}

원래는 res1 하나, res2 하나 이렇게 단일 값을 반환하던 함수를 두 개 묶어서 실행한다면, 두 개의 결과를 언제든 다시 분리할 수 있는 튜플로 (res1, res2) 결과를 반환합니다. 만일, 이 상태에서 또 Arrow를 추가한다면,

chain2 init {
  (res1, res2) = chain1 {
    res1 = Arrow1 init
    res2 = Arrow2 res2
    return (res1, res2)
  }
  res3 = Arrow3 (res2만 뽑아내기)
  return ((res1, res2), res3)
}

또 Arrow를 추가한다면 (((res1, res2), res3), res4) 이렇게 계속 2-튜플의 2-튜플로 유지한다면, 각 개별 결과에 언제든 접근할 수 있는 “가능성”이 생깁니다. 콕 찝어 “가능성”이라 한 이유는, 이 걸 인간이 계속 관리하면서 쓰기엔 사실 가능성만 있을 뿐, 실용적으로 쓰기는 힘들 겁니다.

그냥 함수와 함수를 (.)으로 합성하지 않고, Arrow로 래핑해서 합성하면, Arrow가 제공하는 컴비네이터들을 이용해 이 2-튜플들을 프로그래머가 신경쓰지 않아도, 알아서 안보이게 잘 가지고 다니게 할 수 있습니다. Arrow의 컴비네이터 내부에서는 합성하려던 함수가 a -> b이면, (.)을 쓰고, a -> m b이면 >>을 쓰면 됩니다.

이제, 마지막으로 이렇게 2-튜플의 2-튜플로 만든, 어떻게 보면 우악스러워 보이는 ((((...)...)...)...) 형태의 각 각에 접근하는 방법을 모나드의 do표기처럼 쉽게 해 주는 뭔가가 필요합니다.
m1 >>= \r1 -> m2 >>= \r2 -> m3 >>= \r3 -> m4...로 쓰면 복잡하지만,

do
  r1 <- m1
  r2 <- m2
  r3 <- m3
  ...

이렇게 이쁘게 쓸 수 있게 됐듯이, Arrow를 쓰기 편하게 해주는 확장이 있습니다. 아래에서 이어가도록 하겠습니다.

물론, Arrow의 특 장점이 이게 전부는 아닙니다. 체인을 만들면서, 병행 길을 만들기도, 조건에 따라 분기를 만들기도 할 수 있습니다. 위 스트레칭은 그냥 합성composition하지 않고, 타입으로 래핑해서 얻을 수 있는 능력의 일부를 보이려고 든 예시입니다.

모든 분들에게 어울리는 접근 방법은 아니겠지만, 저는 이렇게 뭘 위해 개념을 도입, 혹은 만들어 내고 있는 지 알면 텍스트를 쫓아가기가 편합니다.

Arrow

입,출력 타입에 의존하는 클래스

출력 타입에만 의존하지 않고, 입,출력 모두에 의존하도록, 입출력 타입을 타입 매개 변수로 가진 클래스를 정의해, 출력뿐만이 아니라 입력이 달라질 때도 명시적인 리프팅 없이 작업을 할 수 있습니다.

실제 정의는 Category 클래스와 Arrow 클래스로 나누어져 있습니다.

class Category cat where
  id :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

class Category arr => Arrow arr where
  arr :: (a -> b) -> arr a b -- 메소드명 arr과 타입인자 arr는 다르다.
                             -- 모나드 코드 m a에서 m에 해당하는데
                             -- (b -> c) -> a b c로 표기하기도 한다.
  first :: a b c -> a (b,d) (c,d)
  first = (*** id)

  (***) :: a b c -> a b' c' -> a (b,b') (c,c')
  f *** g = first f >>> arr swap >>> first g >>> arr swap
    where swap ~(x,y) = (y,x)
  ...
-- 최소 정의 arr, (first | (***))
-- 아래는 메소드가 아닌 별도 함수로 Category 모듈에 정의되어 있다.
(>>>) :: Category arr => arr a b -> arr b c -> arr a c
f >>> g = g . f -- dot의 방향때문에 사람 버벅거리게 만든다. f가 먼저냐 g가 먼저냐.

실제 정의는 위와 같이 되어 있지만, 단순하게 보기 위해 텍스트에선 아래 정의에서 설명을 시작합니다.

class Arrow arr where
  arr :: (a -> b) -> arr a b -- 메소드명 arr과 타입인자 arr는 다르다.
                             -- 모나드 코드 m a에서 m에 해당하는데
      -- (b -> c) -> a   b c 로 표기하기도 한다.
  (>>>) :: arr a b -> arr b c -> arr a c

함수 타입을 위한 인스턴스를 만들면,

instance Arrow (->) where
  arr = id
  (>>>) = flip (.)

위 (>>>)는 함수 합성 (.)과 비슷하게 arrow를 합성하는데, 인자 순서만 (.)과 거꾸로입니다. 특별히 개별 함수들의 결과값을 튜플로 남긴다거나 하지 않고, 보통의 함수 체인처럼 이전 함수의 결과를 다음 함수의 입력으로 넣어주기만 합니다.

Effect가 있는 Kleisli 타입을 위한 인스턴스를 만들면,

newtype Kleisli m a b = Kleisli {runKleisli :: a -> m b}

instance Monad m => Arrow (Kleisli m) where 
  arr :: Monad m => (a -> b) -> Kleisli m a b -- (a -> m b)가 아님
  arr f = return . f
  (>>>) :: Monad m => Kleisli m a b -> Kleisli m b c -> Kleisli m a c
  (f >>> g) a = do b <- f a 
                 g b

Kleisli 타입은 내부에서 이미 존재하는 m이 가지고 있는 바인드를 써서 (>>>)를 구현합니다. (->)와 Kleisli의 arr이나 (>>>)가 별다른 일을 하지 않고 있지만, Arrow 인스턴스가 되면서 &&&, ***, first, second등을 쓸 수 있게 됩니다.

arr, (>>>)만 있으면 return, (>>=)를, 즉 모나드를 대체할 수 있을까?

Kleisli 타입을 가진 Arrow가 모나드와 같은 동작을 하고 있을까요? (>>>)의 구현을 보면 바인드가 돌고 있습니다. (>>>)는 그대로 바인드와 대응하는 것으로 보입니다. 텍스트를 보면, (>>=)는 두 번째 인자로 a -> m b 함수를 받기 때문에, 두 개의 Effectful Computation을 순차적으로 실행(계산)하는 동안 어떤 하스켈 코드all of Haskell든 실행할 수 있는 기회가 있다고 얘기합니다. 반면, Arrow는 Arrow타입과 Arrow 타입을 합성하니, Arrow여야만 한다는 제약이 있고요.

그런데, 위에서 보듯 (>>>)가 함수가 아닌 Arrow값 두개를 받긴 해도, 안에서 (>>=)가 도는데 차이가 없을 것처럼 보입니다. 원문에는 아래 같은 내용이 있습니다. (Programming with Arrows - John Hughes 발췌)

In the case of monads, the second argument of (>>=) is a Haskell function, which permits the user of this interface to use all of Haskell to map the result of the first computation to the computation to be performed next. Every time we sequence two monadic computations, we have an opportunity to run arbitrary Haskell code in between them. But in the case of arrows, in contrast, the second argument of (>>>) is just an arrow, an element of an abstract datatype, and the only things we can do in that arrow are things that the abstract data type interface provides. Certainly, the arr combinator enables us to have the output of the first arrow passed to a Haskell function — but this function is a pure function, with the type b -> c, which thus has no opportunity to perform further effects. If we want the effects of the second arrow to depend on the output of the first, then we must construct it using operations other than arr and (>>>)

이 부분이 스윽 넘어가지지 않아, 아래와 같이 Maybe모나드로 풀어 봤습니다.

첫 컴퓨테이션 값이 Nothing이면, 다음 이어지는 컴퓨테이션에서 a -> m b가 무슨 동작을 하든 Nothing 결과가 나옵니다. 타입을 눈에 보는 그대로 읽으면, m(the effect)도, b도 a에 의존합니다. 어떤 일을 하든지, 해당 타입의 함수만 들어오면 됩니다. 하지만, 바인드와 다르게 (>>>)는 이미 결정된 Arrow 컴퓨테이션 두 개만 받습니다. 이미 정해진 Arrow 컴퓨테이션에 할 수 있는 일은 Arrow가 제공하는 인터페이스를 이용해서 할 수 있는 일만 가능합니다. (Applicatives도 결정된 컴퓨테이션만 받으니, 둘이 연결되는 개념이 있지 않을까 합니다.) 만일, 지금 손에 쥔 인터페이스가 arr과 (>>>)만 있다면, 어떤 일을 할 수 있는지 보겠습니다.

Mon Feb 5 01:04:47 PM KST 2024 작성 중…

아래는 @Ailrun 님의 설명을 옮겼습니다.
예를 들어 State를 다음처럼 모나드 인터페이스를 쓰는 것과, Arrow 인터페이스를 쓰는 것을 비교하면
-- Monad
get :: State Int Int
set :: Int -> State Int ()

-- Arrow
getA :: StateArr Int Int
setA :: Int -> StateArr Int ()

λ> getA >>> setA 5 -- 가능
λ> get >>= (\x -> set (x + 1)) -- 가능
λ> getA >>> (\x -> set (x + 1)) -- 불가능
a b c 와 a c d 를 섞는 것 뿐만 아니라
a b c 와 c -> a d e 도 섞을 수 있냐를 얘기하는 겁니다.

arr과 (>>>)만으론 다음처럼이 한계입니다.
mix :: a b c -> (c -> a d e) -> a b (a d e)
mix p q = p >>> arr q -- q를 Arrow로 만들어야 하니 arr q
first나 app 등이 추가되어야 비로소 (a가 중첩되어 있는 a b (a d e)가 아닌) a (b,d) e를 얻을 수 있게 됩니다.

Arrow가 모나드 동작을 할 수 있는가는, “언제 Uncurrying이 가능한 a를 얻을 수 있는가?”라고 볼 수도 있습니다.

Monad의 핵심이
join :: m (m a) -> m a이니, 이와 비교하기 좋게 바꿔서 보면,
joinLikeArr :: a b (a c d) -> a (b, c) d를 구현할 수 있냐 없냐가 Arrow a로 Monad가 하던 일을 할 수 있냐 없냐를 결정한다고 볼 수도 있겠습니다.
a b c에서 a가 (->)인 경우 joinLikeArr은 uncurry와 같습니다.
uncurry :: (b -> c -> d) -> ((b, c) -> d)

위 설명을 풀어 보겠습니다. Arrow의 모나드 인스턴스에 있는 (>>>)는 잘 보면, 내부에서 바인드가 돌도록 되어 있습니다. do를 풀어 바인드가 보이게 하면

(f >>> g) a = f a >>= \b -> g b

(State sa) >>= f = State $ \s ->
    let (a, s') = sa s
        State sb = f a
    in sb s'

체이닝을 하려면 Arrow여야 하니, 일단 Arrow로 만들기 위해 arr (\x -> setA(x + 1))을 생각해 보면,

  arr :: (b -> c) -> a b c

c 부분에 a d e를 넣으면, 결과는 a b (a d e)가 됩니다. getA >>> arr(\x -> setA(x+1))을 타입을 보면,

a b c >>> a b (a d e)

첫 번째 함수 getA에 s0를 넣어 돌려 (r1, s1)이 나오고, 결과 r1을 b로 받아 \x -> setA(x + 1)를 b에 적용하면, setA(r1 + 1) 작업을 하고, 결과는 State $\s -> let ... in (State $ \s-> ...)이 됩니다. 이어지는 \x -> ...State ...가 받을 수 없는 State가 중첩된 값이 돼버렸습니다. 이대로는 바인드처럼 체이닝을 할 수 없습니다.

StateArr Int (StateArr Int a)의 의미는 뭘까요? Int -> StateArr Int a인 함수인데, Arrow 인터페이스를 가지고 있다는 뜻입니다. 이 함수와 이어질 함수는 StateArr을 하나 벗긴 StateArr Int a을 받을 수 있어야 하는데, 액션 모양은 Int -> ...로 StateArr을 받질 못합니다.

여기까지 (>>>)와 arr 만으론 모나드가 하는 일을 표현할 수 없다를 봤습니다.

(※ 모나드와 Applicatives의 차이를 고민할 때, 모나딕한 동작을 하려면 a -> m b 형태가 반드시 있어야 하고, m b 만으론 부족하다고 틀리게 생각했던 것과 약간 비슷한 요소가 보입니다. )

※ 모나드는 3개의 법칙만 있지만, Arrow는 20개가 있습니다. 여기에 Paterson이 추가한 것까지 합치면 27개입니다. 텍스트에서도 너무 정교한 설명말고 사용법 위주로 설명한다고 되어 있습니다.

@bgl gwyng 님의 “정적인 정보를 가지고 있을 때 유용한 Arrow”에 대한 예시를 옮겨 왔습니다.
newtype WeigthedValue a = WeighteValue { value:: a, weight:: Int }

f :: a -> WeightedValue b
g :: b -> WeightedValue c
h :: c -> WeightedValue d

f >>> g >>> h :: a -> WeightedValue d -- (가)

newtype WeigthedFunction a b = WeigthedFunction { f:: a -> b, weight:: Int }
f = WeightedFunction fImpl 10
g = WeightedFunction gImpl 5
h = WeightedFunction hImpl 7

f >>> g >>> h :: WeightedFunction a d -- (나)
함수들이 실행 비용(실행 시간이라든가)을 정적인 정보로 가지고 있을 때,
해당 타입의 모나드 체인 (가)의 경우 실행을 해 보기 전엔 알 수 없지만,
Arrow 체인 (나)의 경우는 간단히 weight (f >>> g >>> h)로 실행전에 알 수 있습니다.

Applicatives와 Arrow 비교

@todo

모나드가 하는 일을 할 수 있도록 인터페이스를 확장해 보자

Arrow가 모나드와 비슷한 동작을 할 수 있게 만드는 인터페이스입니다.

class Arrow a => ArrowApply a where
  app :: a (a b c, b) c

instance ArrowApply (StateArr s) where
  app = \(arr, x) -> arr x

지금부터 2-튜플의 2-튜플…로 함수들의 결과들을 각 각 기억하는 방법을 위해 필요한 도구(&&&,***,first,second)들을 보겠습니다.

모나드에 들어 있는 두 값을 더하는 것을 보면

addM a b = do x <- a
              y <- b
              return (x + y)
-- 바인드가 보이게 하면
a >>= \x -> b >>= \y -> return (x + y)

위를 읽을 때, a 계산식의 결과를 b가 받는 것으로 읽는 게 아닙니다. a 계산식의 결과를 x로 받고, (이 경우는) a의 결과와 상관 없이 b계산식의 결과를 y로 받아, 마지막에 둘을 +하는 작업입니다. 어떤 M이 들어왔냐에 따라, 숨어 있는 바인드 인스턴스가 알아서 Effect 작업을 담당합니다.

함수형에서는 스코프가 넒은 변수를 쓸 수가 없어, 여러 개의 정보를 “유통”시키려면 인자를 늘리거나 튜플을 씁니다.

addA :: Arrow arr => arr a Int -> arr a Int -> arr a Int
addA f g = f_and_g >>> arr (uncurry (+))
-- uncurry는 인자를 두 개 받는 함수를 2-튜플 하나를 받는 함수로 바꿔줍니다.

f,g 계산을 튜플로 묶은 후 다음으로 넘기면 됩니다. 여기서 f_and_g는 f, g, (>>>), arr만으론 구현할 수 있을까요?

... >>> f >>> ...로 체인을 만들어 두면 f가 나온 뒤에는 f의 결과값 말고는 다 잃어버립니다. 위에 모나드 예시로 보면 x를 기억시키지 못합니다. g의 출력도, 제일 처음에 입력으로 받았던 값도 모두 잃어버립니다.

Q. 어차피 타입에 따른 인스턴스를 만들어야 하는데, 이 때 메소드를 잘 만들면 가능하지 않을까요?
A. (>>>)를 “자유”롭게 만들 수 있는 건 아닙니다. 서명이 Arrow.. -> Arrow.. -> Arrow..으로 정해져 있습니다.

(&&&)

그래서 2-튜플을 이용해 각 각의 결과를 유지하기 위해 Arrow에 다음 컴비네이터를 추가합니다. 2-튜플은 두 개의 값을 담아 둘 수 있으니, (&&&)를 적절히 구현해서 두 Arrow의 결과가 각각 2-튜플에 담기도록 하면, 일단 필요한 정보는 살릴 수 있습니다.

class Arrow arr where
  ...
  (&&&) :: arr a b -> arr a c -> arr a (b, c)
                                       ^^^^^^
                                        2-튜플

Arrow 두 개를 받아 각 각의 Computation을 실행하고, (>>>)처럼 이어지는 Computation에 결과를 넘기는 게 아니라, 결과를 2-튜플로 만드는 컴비네이터입니다. 이제, 이를 이용하면 f_and_g를 구현할수 있습니다.

addA f g = f &&& g >>> arr (uncurry (+))

위에서 봤던 함수와 Kleisli 타입을 위한 인스턴스를 다음과 같이 구현할 수 있습니다.

instance Arrow (->) where
  (f &&& g) a = (f a, g a)

instance Monad m => Arrow (Kleisli m) where
  Kleisli f &&& Kleisli g = Kleisli $ \a -> do b <- f a
                                               c <- g a
                                               return (b, c)
-- stream 함수 `SF`의 경우는 `f`와 `g`의 출력을 `zip`하면 된다.
instance Arrow SF where
  SF f &&& SF g = SF (f &&& g >>> uncurry zip)

각각의 Arrow에 들어 있는 함수들의 결과를 튜플에 넣게만 만들면 됩니다.
※ “각각” 돌기 때문에 &를 쓴 것 같은데, 네이밍에 관한 설명은 따로 안 보입니다.

※ (&&&)의 결과를 머릿속에서 단순한 모양으로 reduce하려 하지 말아야 합니다.

Kleisli $ \a -> do b <- f a
                   c <- g a
                   return (b, c)

이 자체가 가장 단순한 모양입니다.

(***)

다음으로 할 일은, 최대한 타입에 따라 바뀌지 않는 부분을 분리해기 위해 다음처럼 생각해 볼 수 있습니다. 위 구현을 보면 a를 한 번 받아 f에 한 번, g에 한 번씩 쓰고 있습니다. a를 복사duplicate하는 성질(\x -> (x,x))을 빼내면 다음 처럼 볼 수 있습니다.

f &&& g = arr (\x -> (x, x)) >>> f *** g
--              a ->   b     >>> b -> c
-- b가 2-튜플 타입이고, (f *** g)는 2-튜플을 받는 함수를 가지고 있는 Arrow다.

class Arrow arr where
  (***) :: arr a b -> arr c d -> arr (a,c) (b,d)
-- 따로 받던 a, c를 같이 튜플로 묶어서 받고, 결과값도 튜플로 묶는다. 그냥, 각각 동작할 함수들의 입력을 짝 짓고, 출력을 짝지어 묶어놨을 뿐이다.
-- a, b는 같을 필요 없다. 이 경우는 duplicate해서 들어오고 있다.

(***)는 두 개의 Arrow를 받아 2-튜플을 받고 뱉는 하나의 Arrow로 만듭니다. 이 건 하나의 Arrow를 2-튜플을 가진 Arrow로 리프팅해서 얻을 수도 있습니다. 저는 이 아이디어가 금방 눈에 들어오지 않았습니다.
현재 목표는 값 하나를 넣어주면, 두 개로 만들어 (이 작업은 이미 (***)전에 이루어집니다.),
(***)이 2-튜플로 결과를 반환 할 수 있어야 합니다.((***)가 하는 일)

그런데, 이 전 구현보다 더 단순해진 것도 아니고, 굳이 이렇게 구현해야 하는 생각이 잠깐 들었습니다. 뒤에 보면, 2-튜플로 저글링을 많이 합니다. 아마도 이를 위한 컴비네이터 아닌가 싶습니다.

first

처음 봤을 때는, 이 것도 왜 필요한지 금방 눈에 들어오지 않았습니다.
왜 모나딕한 동작을 위해서, first가 필요할까요? 텍스트에선 친절하게 말해주지 않습니다. (제가 못찾거나요)

class Arrow arr where
  first :: arr a b -> arr (a,c) (b,c)

first를 함수, Kleisli arrow, Stream function을 위한 구현을 보면

instance Arrow (->) where
-- 클래스에 있는 서명을 보면 first는 인자를 하나만 받고 있지만,
-- arr에 (->)를 넣으면
-- ((->) a b) -> ((->) (a,c) (b,c))
-- 아래와 같이 2개의 인자를 받는 모양이 된다.
--      (a -> b) -> (a,c) -> (b  ,c)
  first     f       (a,c) =  (f a,c) 

instance Monad m => Arrow (Kleisli m) where
  first (Kleisli f) = Kleisli (\(a,c) -> do b <- f a
                                            return (b,c))

instance Arrow SF where
  first (SF f) = SF (unzip >>> first f >>> uncurry zip)

눈여겨 볼 부분은 현재 계산식에 영향을 미치지 않는 정보를 얹힐 ( ,c)가 있는 겁니다.
구현을 말로 읽어 보면, 당장은 필요 없는 c를, 지금 필요한 a와 묶어서 넘기면 a에만 작업을 해주는 단순한 일을 하는 컴비네이터입니다. 물론 컨텍스트는 유지해 주면서요. 값 하나를 받아 하나만 반환하던 Arrow를 first로 변환하면, 튜플을 받고 튜플을 내뱉는 함수로 바뀝니다.

Arrow클래스의 최소 정의를 보면 first또는 (***) 둘 중 하나만 구현하면, 구현된 걸로 나머지 하나를 구현할 수 있다고 되어 있습니다. first로 (***)을 구현하려면 우선 second를 정의합니다.

second

second :: Arrow arr => arr a b -> arr (c,a) (c,b)
second f = arr swap >>> first f >>> arr swap
  where swap (x,y) = (y,x)

역시 눈여겨 볼 부분은 현재 계산식에 영향을 미치지 않는 정보를 얹힐 (c, )가 있는 겁니다.

second는 first로 구현되기 때문에 따로 구현할 필요 없이, 위 디폴트 구현으로 어디든 쓰면 됩니다. first만 있다면 말입니다.

(***) 다시 정의

이제, first, second를 써서 (***)를 정의할 수 있습니다.

f *** g = first f >>> second g

왜 이렇게 될까요?

-- 비교하기 좋게 constraint는 생략하고 보면
first  :: arr a b -> arr (a,c) (b,c)
second :: arr x y -> arr (d,x) (d,y)

(>>>)  :: arr a b         -> arr b c         -> arr a c
          arr (a,c) (b,c) -> arr (d,x) (d,y) -> arr (a,c) (d,y) 
                 -- (b,c) = (d,x) 가 같아야만 합니다.
                 -- d = b 이고, c = x 입니다.
                                             -> arr (a,x) (b,y)

최종 결과 타입만 보면 arr (a,x) (b,y)에
처음 액션 혹은 함수인 f의 결과 값 b가 살아 있어야 하고,
다음 액션 혹은 함수인 g의 결과 값 y가 살아 있어야 합니다.
마지막 (b,y)에는 둘 다 살아 있으니 목표 달성인 건 맞을 것 같긴 합니다. 역시나 텍스트는 친절하지 않습니다.

first f >>> second g는 현재 목적에 맞는지 말로 읽어보면, 언젠가 값을 duplicate한 2-튜플을 받아 f에 한 번 넣어주고, g에 한 번 넣어줘서 각 결과값을 다시 튜플로 묶습니다. 두 번의 액션(혹은 함수)의 결과가 모두 살아 있으니 목표 달성입니다.

아이디어를 정리하면 f도 a가 필요하고, g도 a가 필요합니다.

a를 (a,a)로 만듭니다.
f로 앞에 a만 바꿉니다. (f a, a)
g로 뒤에 a만 바꿉니다. (f a, g a)

만일 (***)가 먼저 위와 같은 동작을 하도록 정의되어 있다면,

first f = f *** arr id
-- (***) :: arr a b -> arr c d -> arr (a,c) (b,d)
-- arr a b *** arr b b = arr (a,b) (b,b)
-- 2-튜플을 받아 앞에 것에만 작업 할 수 있게 했을 뿐, 별다른 작업은 없습니다.

f는 a -> b 함수고, first f는 (a,dontTouch) -> (b,dontTouch)함수 입니다.
second도, (***)도 first만 있으면 구현할 수 있습니다. 이제 first만 있으면 합성하며, 이전 액션(혹은 함수)의 결과를 다음에 넘기는 일을 할 수 있습니다.

그 외, (^>>), (>>^), (<<^), (^<<) 들은 순수 함수들을 합성compose할 때 arr을 매 번 쓰는 귀찮음을 덜어주는 편의 컴비네이터들입니다.

(***), first, second 모두 어떤 함수가 들어오든 상관없이 튜플 구조에만 관여하는 컴비네이터들로, 이들 중 하나만 구현되어 있으면, 그 걸로 나머지를 구현할 수 있습니다.

조건부로 Arrow 컴비네이션하기

지금부턴 Arrow를 막강하게 해주는 특징, 다이내믹한 흐름을 위한 도구(|||, mapA, +++, left, right)들을 보겠습니다.

If Then Else - ifte

ifte :: Arrow arr => arr a Bool -> arr a b -> arr a b -> arr a b

ifte p f g는 불린값 p가 참이면 f, 거짓이면 g

-- (&&&) :: arr a b -> arr a c -> arr a (b, c)
ifte p f g = p &&& arr id >>> f ||| g
             ^^^^^^^^^^^^
        -- 왜 이렇게 할까요?

p &&& arr id는 왜 해주는 걸까요? p는 조건에 맞는지 검사 후 Bool값을 반환하는 함수입니다.
arr a Bool &&& arr a a = arr a (Bool, a)
원래의 함수는 Bool만 돌려주는데, 변환한 함수는 결과에 Bool값과 처음 입력한 값을 같이 2-튜플에 남겨 둘 수 있습니다.

(|||)

p &&& arr id :: arr a (불린값, f나g에 넣어줄 입력값)
f ||| g :: arr (a, b) c

(|||)는 불린값에 따라 f 혹은 g를 고르고 입력값을 넣어줍니다.

입력값을 2-튜플이 아닌 Either를 받도록 하면 좀 더 매끄러울 수 있습니다. (True, a)를 Left a로, (False, a)를 Right a로 하면 Left일 때와 Right일 때 다른 타입을 갖고 있게 할 수 있어 표현력이 늘어 납니다.

class Arrow arr => ArrowChoice arr where
  (|||) :: arr a c -> arr b c -> arr (Either a b) c
                                     ^^^^^^^^^^^^
                    -- 여기를 2-튜플이 아닌 Either로 바꾼다.

아직 duality에 대한 지식이 없어 정확한 “감탄”은 못하지만, 위 서명에서 arr의 인자 순서를 바꾸고, Either a b를 (a, b)로 대체하면 (&&&)가 나옵니다.

  (|||) :: arr a c -> arr b c -> arr (Either a b) c
  (&&&) :: arr a b -> arr a c -> arr a (b, c)

conditional을 쓴 예시로 mapA 함수를 보겠습니다.

mapA

mapA :: ArrowChoice arr => arr a b -> arr [a] [b]

mapA는 choice가 필요합니다. 왜 필요할까요?

map _ []     = [] -- base case 혹은 edge case
map f (x:xs) = f x : map f xs -- recursive case

map은 보통 base, recursive를 구분해야 합니다. 다음처럼 표현할 수 있습니다.
base case ||| recursive case

우선 입력을 Either 타입으로 바꿔주는 보조 함수를 만들고,

listcase [] = Left ()
listcase (x:xs) = Right (x,xs)

이제 mapA를 구현하면

mapA f = arr listcase >>>
         arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))
--                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
--                      map의 f x : map f xs 와 비슷한 동작을 한다.
--            uncurry는 인자 두 개를 받던 함수를 2-튜플 하나 받는 걸로 바꾼다.

컴비네이터 스타일의 우아함이 폭발하는데, 저는 금방 우아할 수가 없습니다. 어렵습니다.

(+++)

f ||| g는 f와 g가 같은 타입의 출력이어야 하는데, Either를 쓰면 다른 타입도 가능합니다.

class Arrow arr => ArrowChoice arr where
  (+++) :: arr a b -> arr c d -> arr (Either a c) (Either b d)

(+++)과 (|||)의 관계는 (***)과 (&&&)의 관계와 비슷합니다. (|||)를 직접 구현하는 것 보다는 (+++)를 먼저 구현하고, (+++)을 써서 (|||)를 구현하는 게 편합니다.

(+++)는 (***)와 dual입니다. Either 타입을 2-튜플로 바꾸고, arr의 인자 순서를 바꾸면 (|||)의 정의는

f ||| g = f +++ g >>> arr join -- 라이브러리에선 join대신 untag란 이름을 쓴다.
  where join (Left b)  = b
        join (Right b) = b

(***)를 first로 표현하듯, (+++)는 Either의 left로 리프팅하는 단순한 컴비네이터로 정의할 수 있습니다.

(***)는 두 개의 Arrow를 받아 2-튜플로 묶는 작업을 했고,(두 Arrow 모두 실행)
(+++)는 두 개의 Arrow를 받아 Either로 묶는 작업을 했습니다. (두 Arrow 중 하나만 실행하기 위한 사전 동작?)

left

class Arrow arr => ArrowChoice arr where
  left :: arr a b -> arr (Either a c) (Either b c)

left f는 Left라고 태깅된 입력은 f에 넣어주고, Right라고 태깅된 입력은 그냥 통과시킵니다.

right

first로 second를 정의하듯 left로 right를 정의할 수 있습니다.

right f = arr mirror >>> left f >>> arr mirror
  where mirror (Left a) = Right a -- swap을 정의하 듯
        mirror (Right a) = Left a

…작성 중

(+++) 다시 정의

f +++ g = left f >>> right g

사용 예시

Arrow 쓰는 방법

Arrow 확장

확장 Arrows

마치 함수를 일반 수처럼 여러 연산자들로 식을 만드는 것 같이 보입니다. Arrow 대수라고 불러도 되지 않을까 싶은데요. 따로 대수라고 부르는데는 못 봤습니다. 컴비네이터 패턴이란게 다 대수와 같은 것들 아닌가 싶습니다.

참고
시간과 머리가 허락한다면, wiki.haskell.org - Arrow 사이트에 있는 링크를 쫓아다니며 공부하면 Arrow 마스터!가 될 수도 있겠습니다만, 분량이 너무 많습니다.

2025.2 추가

아래는 모두 Programming with Arrows - John hughes에서 발췌한 소스입니다.

a -> b 와 a -> m b 모양 함수들을 체이닝

단어 w가 몇 번 나타나는지 찾는 작업

-- count :: String -> String -> Int
λ> let count w = length . filter (==w) . words --(가)
λ> count "ab" "ab bc ab"
2

만일 파일에서 읽어와 화면에 출력하려면 print와 readFile을 합성해야 합니다.

count w = print . length . filter (==w) . words . readFile -- 타입 불일치
--        액션                   함수              액션

하지만 이펙트가 있는 IO액션과 함수를 이렇게 합성할 수 없습니다. (가)를 리프팅해서 IO 컨텍스트로 들어가야 합니다.

count w = (>>=print) . liftM (length . filter (==w) . words) . readFile

둘이 합칠 때, 좀 더 이쁘게 보이도록 함수 타입을 위한 인스턴스를 만들고,

instance Arrow (->) where
  arr = id
  (>>>) = flip (.)

액션(Kleisli)을 위한 인스턴스를 만들면,

newtype Kleisli m a b = Kleisli {runKleisli :: a -> m b}

instance Monad m => Arrow (Kleisli m) where 
  arr :: Monad m => (a -> b) -> Kleisli m a b -- (a -> m b)가 아님
  arr f = return . f
  (>>>) :: Monad m => Kleisli m a b -> Kleisli m b c -> Kleisli m a c
  (f >>> g) a = do b <- f a 
                   g b

다음처럼 쓸 수 있습니다. (순서가 바뀌긴 했는데, (.)이 수학쪽 관습을 맞춘 것입니다. 먼저 작업해야 하는 걸 먼저 써주는 게 좋으니, 아래처럼 바뀌게 됩니다.)

λ> let count w = Kleisli readFile 
             >>> arr words 
             >>> arr (filter (== w)) 
             >>> arr length 
             >>> Kleisli print 
λ> runKleisli (count "aa") "some.txt"  -- some.txt 내용: aa bb aa
2

함수a -> b와 액션c -> m d 모양을 합성하는데, 어느 정도 통일된 모양으로 써줄 수 있게 됐습니다.
arr은 함수를 리프팅하는데, 함수를 먼저 합성한 후 리프팅해도 되니(자세하게는 Arrow 법칙을 봐야 하는데, 여기선 넘어 가겠습니다.) 다음처럼 써도 있습니다.

count w = Kleisli readFile >>>    arr (words >>> filter (==w) >>> length)    >>> Kleisli print

arr안에 있는 >>>는 함수의 인스턴스고, 바깥에 있는 >>>는 Kleisli의 인스턴스입니다.

Arrow는 입, 출력에 매개 변수화 되어 있다

“The way monadic programs take input cannot be varied by varying the monad”

모나딕 프로그램은 모나드를 변경하는 것만으로 다양한 입력을 받을 수 없다? 무슨 뜻일까요?
출력에만 매개 변수화parameteriezed 되어 있는 것과, 입, 출력 둘에 매개 변수화 되어 있는 것의 차이는 뭘까요?

Maybe는 출력 타입 하나를 인자로 받고, Arrow는 입력, 출력 두 개를 인자로 받습니다.

  Maybe a >>= a -> Maybe b >>= b -> Maybe c
  arr a b >>>      arr b c >>>      arr c d

텍스트에선 스트림(리스트) 인스턴스를 모나드가 표현하지 못하는 방식이라고 합니다.

instance Arrow SF where
  arr f = SF (map f)
  SF f >>> SF g = SF (f >>> g)

arr f에서 f가 스트림(리스트)을 받게 할 수 있는데, 모나드는 그러지 못한다고 합니다. 왜?

a -> m b  >=>  b -> m c

위 체인의 결과는 모나드 m이 표현할 수 있는 것들이 되고, 입력 a는 모나드 m과는 상관 없는 상태입니다.

arr  a b  >>>  arr  b c

위 체인의 결과는 arr이 표현할 수 있는 것들이고, 입력도 arr이 표현할 수 있는 것들로 되어 있습니다. 당연히, 모나드는 m을 뭘로 바꾸든 a를 바꿀 수 없지만, arr은 원하는 타입에 맞는 arr 인스턴스를 만들면 됩니다.

f :: a -> b란 함수가 있을 때 arr f와 return . f의 차이를 보겠습니다.
arr f = SF (map f)를 하면 SF가 안에 [a] -> [b]를 가진 상태가 됩니다. 입력 a를 [a]로 바꿀 수 있습니다.
하지만 return@[] . f(@[]는 리스트의 인스턴스란 말입니다.)는 a -> [b]가 됩니다. a를 스트림으로 바꾸지 못했습니다.

모나드만으론 a -> b 함수의 입력을 변형variation하는 작업은 할 수 없습니다.

설명은 이해한 듯 한데, 이로 인해 얻는 이점은 사용해 봐야 알 것 같습니다.

체이닝 되어 있는 함수 각 각의 결과에 접근

다음 절차형 코드와 같이 각 함수의 결과에 개별 접근 작업을 순수 함수로 하려면 어떻게 할까요?

init = 0
a = add1 init
b = add2 init
return a + b

마지막에 add1함수의 결과와 add2함수의 결과에 각 각 접근하고 있습니다. 그냥 (+2).(+1)같이 합성하면, 각 각의 결과에 접근할 수 없습니다. 이럴 때 모나드 구조를 이용해 다음처럼 해결할 수 있습니다.

add1 = (+1)
add2 = (+2)
comp = do
  a <- add1 
  b <- add2 
  return $ a + b

λ> comp 0
3

Arrow로 하려면 arr과 (>>>)만으론 할 수 없습니다.

2-튜플(순서쌍)

일단 함수 두 개의 경우만 보겠습니다. 두 함수를 실행해서 두 함수의 결과를 모두 가지고 있어야 합니다. 두 개의 정보를 묶는데 가장 단순한 구조인 2-튜플(순서쌍)을 떠올릴 수 있습니다. 지금부터는 2-튜플이라 안 쓰고, 그냥 튜플이라 쓰겠습니다.

(&&&)

두 개의 함수를 받아서 가지고 있다가, 인자를 넣어 주면 각 함수에 인자를 넣어 주고, 각 실행 후 결과를 튜플로 묶으면 됩니다.

f &&& g = \x -> (f x, g x)

위 예시처럼 두 값을 더하려면, 인자 두 개를 받는 (+)를, 인자를 튜플로 묶어서 받도록 uncurry해서 이어 주면 됩니다.

f &&& g >>> uncurry (+)

텍스트에선 여기서부터 기능을 단계별로 해부(기능을 잘게 쪼개기)하는데, 컴비네이터를 설계하는 예시를 볼 수 있는 기회이기도 합니다.

(***)

&&&보다 좀 더 프리미티브한 조각이 되도록 f와 g의 조합이 각 함수가 필요한 인자를 튜플로 받게 할 수 있습니다. (그럼, 나중에 같은 인자를 f와 g에 넣어주는 게 아니라, 다른 값을 넣어 주는 곳에서도 쓸 수 있습니다.)

인자 하나를 받으면, 인자를 복사해서 튜플로 만들고,
f와 g를 조합해서 튜플을 받으면,
첫 번째 원소는 f에, 두 번째 원소는 g에 넣어주고, 결과값을 모아 다시 튜플로 만든다.

f &&& g = arr (\x -> (x,x)) >>> f *** g

&&&에서 인자를 하나 복사해서 튜플로 만들던 기능을 빼냈습니다.
여기서 좀 더 해부를 합니다. 3번, 튜플의 각 각의 원소에 함수를 적용하던 것을 둘로 나눌 수 있습니다. 1. 첫 번째 원소에 f 적용 1. 두 번째 원소에 g 적용

first

-- (->)의 인스턴스를 예로 보면
first f (a, c) = (f a, c)

***로 first을 표현한다면,

first f = f *** arr id

거꾸로 first를 프리미티브하게 잡으면, ***는 첫 번째 적용과, 두 번째 원소에 적용이 필요하니

second

-- second f (a, c) = (a, f c) 로 해도 되지만, 프리미티브를 많이 만들지 않기 위해
second f = arr swap >>> first f >>> arr swap
  where swap (x, y) = (y, x)

이렇게 정의하고 나면

f *** g = first f >>> second g

덤으로 실행 순서도 잘 보이는 모양이 됐습니다. 텍스트에선 여기서 바로 모나드 구조를 대신하는 모습을 보여 주지 않고, 조건에 따라 실행하는 컴비네이터를 정의합니다.

ifte

if (x = 1) then f else g 
--    p

p의 결과에 따라 f 또는 g를 선택합니다. 우선 두 부분으로 나누어, 1. p가 True인지 False인지 보는 부분 1. f와 g 중 선택 으로 나눌 수 있습니다. 1번 부터 표현하면,

p &&& arr id

f &&& g는 f와 g를 묶어, 하나의 인자를 각 함수에 넣어서 실행 후 튜플을 내뱉는 함수로 바꿔 줍니다.
p :: x -> Bool 와 id :: x -> x 둘을 묶으면, (Bool, 입력값 x) 결과를 뱉는 함수가 됩니다. 여기엔 Bool값과 입력값 두 개의 정보가 고스란히 담겨 있습니다. 이를 첫 번째 Bool에 따라 함수를 선택해서 입력값 x를 넣어주도록 만들면 됩니다.

(|||)

p &&& arr id >>> f ||| g

|||는 받은 튜플의 첫 번째를 보고, f 또는 g를 고르는 함수입니다. 지금은 f와 g가 같은 인자를 받는 모양입니다. 좀 더 일반적으로 만들어 보겠습니다. p의 결과는 (True, x) 아니면 (False, x)입니다. 두 가지 옵션만 있는 타입이니 Either를 써서 (True, x)를 Left x, (False, x)를 Right x로 표현할 수 있습니다.

|||는 Either 타입을 받아서 f 또는 g를 고르면 되는데, Either를 썼기 때문에 f와 g가 받는 인자 타입을 달리할 수 있게 됩니다.

(|||) :: arr a c -> arr b c -> arr (Either a b) c

그런데 여기서 arr에 있는 인자를 뒤집고, Either를 튜플로 바꾸면

(&&&) :: arr c a -> arr c b -> arr c (a, b)

바로 &&&와 같습니다. 텍스트에선 |||와 &&&가 듀얼 관계에 있다고 말합니다. 이 게 어떤 인사이트를 주는 결과인 것 같은데, 어떤 인사이트인지는 특별히 설명하지 않고 있습니다. 흐름이 분기되는 |||과 병렬 흐름을 만드는 &&&입니다. AND와 OR이 듀얼이고, 튜플과 Either가 듀얼입니다.

조건부 분기Conditionals의 예시로, mapA를 들고 있습니다. 왜 매핑에 조건부 표현이 필요할까라고 생각할 수 있는데, 매핑은 엣지 조건이냐 아니냐를 구분해서 동작합니다.

listcase [] = Left () -- 엣지 조건
listcase (x:xs) = Right (x, xs)

로 볼 수 있습니다. 이를 써서 Arrow로 mapA를 표현하면,

mapA f = arr listcase >>>  -- 엣지 조건 검사를 Either로 바꿔 아래 |||로 만든 컴비네이션에 넘긴다.
         arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))

[1,2]에 let f = (+10)을 적용하는 걸 mapA로 작성해 보겠습니다. 엣지 조건 말고, 재귀 되는 부분을 살펴 보겠습니다. (f *** mapA f >>> arr (uncurry (:)))는 (x, xs)를 받습니다.

((+10) 1, mapA (+10) [2]) >>> arr (uncurry (:))
(+10) 1 : mapA (+10) [2]
(+10) 1 : ((+10) 2, []) >>> arr (uncurry (:))
(+10) 1 : (+10) 2 : []
11 : 12 : []
[11, 12]

(+++)

(&&&)에서 인자를 튜플로 만드는 작업을 빼내고 (***)를 정의한 것처럼,
(|||)에서 Either값을 단일 값으로 바꾸는 작업을 빼낼 수 있습니다.

f ||| g = f +++ g >>> arr join
  where join (Left b)  = b
        join (Right b) = b

(+++) :: arr a b -> arr c d -> arr (Either a c) (Either b d)

(***)을 first, second로 쪼갰듯이, (+++)도 쪼갤 수 있습니다. first는 함수(->) 인스턴스를 보면 a -> b인 함수를 (a, c) -> (b, c)로 만들고, second는 (c, a) -> (c, b)로 만드는 컴비네이터였습니다. first와 비슷하게

left

left :: arr a b -> arr (Either a c) (Either b c)

를 정의하고, second를 first와 swap으로 정의했던 것과 비슷하게

right

right f = arr mirror >>> left f >>> arr mirror
  where mirror (Left a) = Right a
        mirror (Right a) = Left a

를 정의하면 다음처럼 써 줄 수 있습니다.

f +++ g = left f >>> right g

그럴 거라 예측은 가지만, 자세한 동작이 금방 눈에 보이지 않습니다. 말로 풀면 쉽게 이해가 갑니다.
left는 Arrow를 Left값일 때만 반응하게 만들고,
right는 Arrow를 Right에만 반응하게 만듭니다.

스트림 인스턴스의 예시를 보겠습니다.

dalay x = SF (init . (x:)) -- init은 끝 원소 제거

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

SF 인스턴스 동작

왜 [[0,1,2],[0,4,5],[0,7,8]]이 아니라 위와 같은 결과가 나올까요?

mapA f = arr listcase >>>
         arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))
         --------------     ------------------------------------
               g'                             h'

(delay 0) [1,2,3] : mapA (delay 0) ...으로 해석되는 게 아닌 걸까요? 그리 간단하지 않습니다.
f *** mapA f = (\(xs,yss) -> ((init .(0:)) xs, mapA (delay 0) yss))에 >>> arr (uncurry (:))를 이어 붙이면, 얼핏 보면 엣지 조건으로 수렴하지 않는 모양으로 보일 수 있습니다. 놓친 게 있습니다. listcase (z:zs)를 Right (z, zs)로 첫 원소를 떼어 내면서 이미 엣지 조건을 향해가는 작업을 합니다.(혼동하지 않도록 z, zs로 바인드명만 바꿨습니다.)

단순화 하기 위해 [[1,2]]를 넣어 보겠습니다.

g' ||| h' = left g' >>> right h' >>> arr join

[Right (1, [2])]가 들어 왔으니, h'만 반응합니다. h'에 (1,[2])을 그냥 적용하는 것이 아니라, right로 [Right (1,[2])]을 h'에 넣어 주게 됩니다. h'은 튜플을 받고 리스트로 내보내는 함수입니다.

λ> runSF (right (delay 0)) [Left 1, Right 1]
[Left 1, Right 0]
λ> runSF ( (delay 0) *** mapA (delay 0) ) [(1,[2]), (3,[4])]
[(0,[0]), (1,[2])]

delay 0 = SF (init . (0:))으로 리스트를 받아야만 할 것 같은데, 튜플이 먼저 들어와서 타입 불일치가 일어날 것만 같이 보입니다. ***이 튜플을 해체해서 각 각의 리스트로 만들어 준다면 말이 될 것처럼 보입니다. SF의 first 정의는 역시나 unzip을 포함한 SF (unzip >>> first f >>> uncurry zip)입니다.

λ> unzip [(1,[2]),(3,[4])]
([1,3], [[2],[4]])

이제 눈에 보입니다. h' = \(xs, ys) -> (f xs : mapA f ys)을 적용하기 전에 unzip이 포함된 ***을 거치니 ([1],[[2]])에 h'을 적용하면, (0,[0])를 uncurry (:)한 것들의 리스트, 즉 [[0,0]]이 나옵니다.

한참 헤맸는데, 결국은 각 인스턴스들의 구현을 대충 봐서 생긴 오해였습니다. 아래 코드를 GHCi에서 불러 와서 테스트해 보세요.

class Arrow arr where
  arr :: (a -> b) -> arr a b
  (>>>) :: arr a b -> arr b c -> arr a c
  first :: arr a b -> arr (a,c) (b,c)
  (&&&) :: arr a b -> arr a c -> arr a (b, c)
  f &&& g = arr (\x -> (x,x)) >>> (f *** g)

  second :: arr a b -> arr (c,a) (c,b)
  second f = arr swap >>> first f >>> arr swap
    where swap (x,y) = (y,x)

  (***) :: arr a b -> arr c d -> arr (a,c) (b,d)
  f *** g = first f >>> second g

class Arrow arr => ArrowChoice arr where
  (|||) :: arr a c -> arr b c -> arr (Either a b) c
  f ||| g = f +++ g >>> arr join
    where join (Left b) = b
          join (Right b) = b

  left :: arr a b -> arr (Either a c) (Either b c)
  right :: arr a b -> arr (Either c a) (Either c b)
  right f = arr mirror >>> left f >>> arr mirror
    where mirror (Left a) = Right a
          mirror (Right a) = Left a
  (+++) :: arr a b -> arr c d -> arr (Either a c) (Either b d) 
  f +++ g = left f >>> right g
  
instance Arrow (->) where
  arr = id
  (>>>) = flip (.)
  (f &&& g) a = (f a, g a)
  first f (a,c) =  (f a,c) 

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

instance Arrow SF where
  arr f = SF (map f)
  SF f >>> SF g = SF (f >>> g)
  SF f &&& SF g = SF (f &&& g >>> uncurry zip)
  first (SF f) = SF (unzip >>> first f >>> uncurry zip)

instance ArrowChoice (->) where
  left f (Left a) = Left (f a)
  left f (Right b) = Right b

instance ArrowChoice SF where
  left (SF f) = SF (\xs -> combine xs (f [y | Left y <- xs]))

-- 주의: Left (y:xs) 가 아니라, 첫 원소가 Left y
combine (Left y:xs) (z:zs) = Left z: combine xs zs
combine (Right y:xs) zs = Right y: combine xs zs
combine [] zs = []

listcase :: [a] -> Either () (a,[a])
listcase [] = Left ()
listcase (x:xs) = Right (x, xs)

mapA f = arr listcase >>> 
         (arr (const []) ||| (f *** mapA f >>> arr (uncurry (:))))

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

고차 Arrow

다른 Arrow를 입력으로 받는 Arrow를, 위에서 언급한 컴비네이터들만으론 만들 수 없다고 합니다.
Q. 왜 그럴까요? 그냥 arr (arr a, b) c 라는 Arrow가 있을 수 없다는 말일까요?
Arrow가 되려면, 최소한 arr과 first를 만들 수 있어야 합니다.

class Category cat where
  id :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

class Category arr => Arrow arr where
  arr :: (a -> b) -> arr a b
  first :: a b c -> a (b,d) (c,d)

arr메소드는 (a -> b)를 ((arr a' a) -> b)쯤 될 것 같고,
first메소드는 a (a b' c') c -> a ((a b' c'), d) (c,d)쯤 될텐데,
이들이 프리미티브한 요소들인데, 이들을 정의할 수 없다는 얘기일까요?

지금은 답을 먼저 알고 있으니, 답에서 들어가 보겠습니다. app이 어떤식으로 쓰이는지를 보면 보일지도 모릅니다.

class Arrow arr =>  ArrowApply arr where
  app :: arr (arr a b, a) b

instance ArrowApply (->) where
  app (f, x) = f x

instance Monad m => ArrowApply (Kleisli m) where
  app = Kleisli (\(Kleisli f, x) -> f x)

app정의의 안 쪽을 보면 arr a b와 a를 가지고 있습니다.

app을 가지고 있는 Arrow는 모나드로 동작할 수 있습니다.

newtype ArrowMonad arr a = ArrowMonad (arr () a)

instance ArrowApply a => Monad (ArrowMonad a) where
  return x = ArrowMonad (arr (const x))
  ArrowMonad m >>= f =
    ArrowMonad (    m 
                >>> arr (\x -> let ArrowMonad h = f x in (h, ()))
                >>> app)

app은 그저, (함수, 인자)를 받아 적용시켜주는 uncurry된 $처럼 보입니다. 이런 함수가 뭐 그리 대단한 일을 해낼까요?

Arrow를 ArrowMonad로 감싸고, ArrowMonad를 모나드 인스턴스로 만들고 있습니다. 아무 Arrow나 다 되는 건 아니고, ArrowApply 인스턴스인 경우만 됩니다. 바인드>>=는 이펙트를 join하는 동작이 있어야 합니다. ArrowMonad의 이펙트는 무엇이고, 어떤 모양으로 join 동작을 하고 있을까요? 텍스트에는 따로 언급이 없어 직접 찾아 봤습니다.

Maybe 모나드의 바인드에서 이펙트 찾기
펑터는, 실무에서 코드로 보면, a까지 도달하는데 반드시 실행해야 되는 절차를 fmap으로 구현한 구조를 말합니다. (좀 더 정화히는 pure도 있고, 펑터 법칙도 따라야 합니다만) 예를 들어,
Just (Just a)
이러면, a에 도달할 때까지 Nothing인지 검사해서 하나를 통과하고, 또 Nothing인지 검사해서 a에 도달하게 됩니다. 더 나아가서 Just 1과 Just (Just 1)이 의미적으로 차이가 없다고 “결정”하고, Just (Just 1)은 Just 1로, Just Nothing은 Nothing으로 join하는 동작을 가지도록 한 구조를 Maybe 모나드라 합니다.
(Just x) >>= f = f x
Nothing >>= _ = Nothing
“Just일 경우만 f를 적용하고, Nothing일 때는 적용하지 않는다”는 이펙트만 “함수 패턴 매칭Function Pattern Matching”으로 나타나고, join은 잘 안보입니다. f는 결과가 Just로, Just x에 적용하면 Just (Just f x)가 될텐데, (Just x) >>= f에서 Just x 패턴 매칭으로 Just 하나를 없애고 있습니다. ※ “값 생성자 패턴 매칭Constructor Pattern”이라 부르고, 해체Deconstructor, 구조 분해Destructuring라 부르기도 합니다. x는 Just안에 있는 값과 바인딩됩니다.

ArrowMonad (arr () a)에서 a에 도달하려면 어떤 작업을 해야 할까요? 입력으로 ()를 받아 a를 돌려주는 함수를 가지고 있으니, 여기에 ()를 줘서 a를 얻은 후 f를 적용합니다. 그러면,
ArrowMonad (arr () (ArrowMonad (arr () a)))
상태가 됩니다. 깊숙히 안에 있는 a에 도달하기 위해 어떤 절차를 거쳐야 할까요?

                    m
                >>> arr (\x -> let ArrowMonad h = f x in (h, ()))
                >>> app)

위 체인의 결과가 () -> ArrowMonad (arr () a)인데, 바깥에서 ArrowMonad 값 생성자가 한 번 더 적용되도록 되어 있습니다. 내부 Arrow가 가진 함수 () -> a는 Reader env와 비슷하고, 입력 값이 ()로 고정되어 있습니다. 두 번째 Arrow를 보면 (h, ()) 튜플을 반환합니다. 왜 바로 h ()로 a를 만들지 않고 튜플로 반환할까요? h는 Arrow입니다. 바로 ()에 적용할 수 없습니다.

비슷하게 생긴 Reader 모나드 바인드 구현입니다.

newtype Reader r a = Reader { runReader :: r -> a }

(Reader ra) >>= f = Reader $ \r -> runReader (f (ra r)) r

함수 형태 _ -> a에서 a에 도달하기 위해선, 적용apply 동작이 반드시 필요함을 알 수 있습니다. 나중에 runArrow 같은 것들을 붙였을 때, 해석되게 하려고 (함수, 인자)를 바깥 Arrow 컨텍스트에 넣어 놓는다고 볼 수 있습니다.

왜 이런 구현을 해 놓았는지는 알겠는데, 써먹기까진 좀 더 훈련이 필요하겠습니다.

Maybe 모나드가 하는 일을 Arrow로 표현한다면?

safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)

chain init = do
  r1 <- safeDiv 10 init
  safeDiv 4 r1

λ> chain 5
Just 2
λ> chain 11
Nothing

위와 같은 동작을 하는 Arrow를 만들어 보겠습니다. 1. 나눌 수와 나누는 수를 튜플로 받습니다.
결과는 Left () 이거나 Right Int 입니다.
(Int, Int) -> Either () Int 1. Just와 Nothing으로 분기해야 하니 ArrowChoice 인스턴스여야 합니다. 1. Just는 Right로, Nothing은 Left에 대응 시킵니다.

safeDivA :: ArrowChoice a => a (Int, Int) (Either () Int)
safeDivA = proc (x, y) ->
  if y == 0
    then returnA -< Left ()
    else returnA -< Right (x `div` y)

(->)의 Arrow 인스턴스에 있는 >>>에는 Maybe 모나드처럼 흐름을 끊는 동작은 없습니다. |||를 이용해 Left와 Right에 따라 분기하게끔 합니다.

전체 소스

{-# LANGUAGE Arrows #-}

import Control.Arrow
import Control.Category
import Prelude hiding ((.), id)

safeDivA :: ArrowChoice a => a (Int, Int) (Either () Int)
safeDivA = proc (x, y) ->
  if y == 0
    then returnA -< Left ()
    else returnA -< Right (x `div` y)

bindA :: ArrowChoice a => a (Int, Int) (Either () Int) -> a (Int, Int) (Either () Int) ->Int -> a (Int, Int) (Either () Int)
bindA ar1 ar2 z = proc (x,y) -> do
  r1 <- ar1 -< (x,y)
  arr (\_ -> Left ()) ||| (arr (\n -> (z,n)) >>> ar2) -< r1

이런 경우에는 그다지 쓸모 있어 보이진 않습니다. (제가 잘 못 구현해서 그럴 수도 있습니다.)

Github 계정이 없는 분은 메일로 보내주세요. lionhairdino at gmail.com