사이트내 검색
여기 글들은 일종의 질문입니다. 용어 선택도 학계, 업계에서 쓰는 걸로 되어 있지 않고, 틀린 내용이 있을 수도 있습니다.
함수형은 여러 개의 함수들을 합성compose해서 프로그램을 만들어 갑니다. Arrow는 타입에 상관없이, 합성하는 인터페이스를 통일하자는 것이니, 함수형의 근간을 이루는 구조, 패턴이 아닌가 싶은데, 실상은 모나드만큼 인기리에 쓰이고 있는 것처럼 보이진 않습니다. (제 기준으론 외모도 모나드의 do만큼 깔끔하게 똑 떨어지진 않습니다.) 이론들이 단 몇 년만에 도입되어 폭발적으로 쓰이거나 그러진 않으니, 아직도 서서히 성장 중인 걸지도 모르겠습니다. FRP 라이브러리나(Yampa), GUI 라이브러리(Fruit)등, 도입한 라이브러리가 꽤 있고, 다른 언어에서도 FRP 구현에선 중요한 역할을 하고 있는 이론인가 봅니다.
공부하면서 계속 원문과 노트를 같이 넣다보니 글이 많이 길어졌습니다. 아마도 보실 분들은 거의 없을텐데요. Arrow를 공부하다 막히는 부분이 있을 때, 다른 관점은 없나 궁금할 때 Ctrl-F로 찾아보면 좋을 듯 합니다.
전체적인 글은 다음 순서로 흘러 갑니다.
(>>>), arr 로 모나딕 작업과 아닌 작업을 인터페이스를 같게 만든다.first 를 추가한다. 2튜플의 앞에 것에만 작업을 한다는 것만으로 어찌 모나드스러울 수 있을까?Programming with Arrows - John hughes
위 텍스트를 읽으면서 가졌던 의문들과 알게된 답을 같이 적었습니다. 늘 그렇듯, 읽는 이가 스스로 감수자가 되어 읽어주셔야 합니다.
수학이 강한 분들은, 아래 같은 얘기를 별로 안 좋아하는 경우가 있습니다. 너무 “인문학”스럽게 접근하는 걸로 보이나 봅니다. 전, 논리적으로 딱 맞아 떨어져도, 아래 같은 이해를 하지 못하면 현실을 모델링할 때 써먹질 못합니다. 여하튼, 그다지 환영 받는 얘기는 아니니, 적당히 한 귀로 흘리시면서 보세요.
Int, Char같은 프리미티브 타입이 아니라, 프로그래머가 만들어내는 타입들에 관한 얘기입니다.
data Some a = Some aSome 타입같은 것을 볼 때, 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하지 않고, 타입으로 래핑해서 얻을 수 있는 능력의 일부를 보이려고 든 예시입니다.
모든 분들에게 어울리는 접근 방법은 아니겠지만, 저는 이렇게 뭘 위해 개념을 도입, 혹은 만들어 내고 있는 지 알면 텍스트를 쫓아가기가 편합니다.
출력 타입에만 의존하지 않고, 입,출력 모두에 의존하도록, 입출력 타입을 타입 매개 변수로 가진 클래스를 정의해, 출력뿐만이 아니라 입력이 달라질 때도 명시적인 리프팅 없이 작업을 할 수 있습니다.
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 bKleisli 타입은 내부에서 이미 존재하는 m이 가지고 있는 바인드를 써서 (>>>)를 구현합니다. (->)와 Kleisli의 arr이나 (>>>)가 별다른 일을 하지 않고 있지만, Arrow 인스턴스가 되면서 &&&, ***, first, second등을 쓸 수 있게 됩니다.
Kleisli 타입을 가진 Arrow가 모나드와 같은 동작을 하고 있을까요? (>>>)의 구현을 보면 바인드가 돌고 있습니다. (>>>)는 그대로 바인드와 대응하는 것으로 보입니다. 텍스트를 보면, (>>=)는 두 번째 인자로 a -> m b 함수를 받기 때문에, 두 개의 Effectful Computation을 순차적으로 실행하는 동안 어떤 하스켈 코드all of Haskell든 실행할 수 있는 기회가 있다고 얘기합니다.
그런데, 위에서 보듯 (>>>)가 함수가 아닌 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과 (>>>)만 있다면, 어떤 일을 할 수 있는지 보겠습니다.
arr의 서명은 (b -> m c) -> a b c가 아니라 (b -> c) -> a m b c 입니다.
Kleisli Maybe Arrow를 생각해 보면, arr f는 Just . f입니다. Just일지 Nothing일지 고르는 절차 없이 바로 Just 값 생성자를 쓸 뿐입니다. arr로 리프팅하여 만든 컴퓨테이션엔 이미 Just로 고정되어 있지, 바인드의 두 번째 인자 a -> m b처럼, a에 따라 m이 Just인지 Nothing인지 결정하는 절차가 파고 들어갈 기회가 없습니다.
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가(->)인 경우는 다음처럼 됩니다.
uncurry :: (b -> c -> d) -> ((b, c) -> d)
(※ 모나드와 Applicatives의 차이를 고민할 때, 모나딕한 동작을 하려면 a -> m b 형태가 반드시 있어야 하고, m b 만으론 부족하다고 틀리게 생각했던 것과 약간 비슷한 요소가 보입니다. )
※ 모나드는 3개의 법칙만 있지만, Arrow는 20개가 있습니다. 여기에 Paterson이 추가한 것까지 합치면 27개입니다. 텍스트에서도 너무 정교한 설명말고 사용법 위주로 설명한다고 되어 있습니다.
@재경 님의 예시 @todo 정리 중에 있습니다.
@todo
지금부터 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가 필요할까요? 텍스트에선 친절하게 말해주지 않습니다. (제가 못찾거나요)
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 :: 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를 막강하게 해주는 특징, 다이내믹한 흐름을 위한 도구(|||, mapA, +++, left, right)들을 보겠습니다.
If Then Else - ifte
ifte :: Arrow arr => arr a Bool -> arr a b -> arr a b -> arr a bifte 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 :: 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 casemap은 보통 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 중 하나만 실행하기 위한 사전 동작?)
class Arrow arr => ArrowChoice arr where
left :: arr a b -> arr (Either a c) (Either b c)left f는 Left라고 태깅된 입력은 f에 넣어주고, 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 대수라고 불러도 되지 않을까 싶은데요. 따로 대수라고 부르는데는 못 봤습니다. 컴비네이터 패턴이란게 다 대수와 같은 것들 아닌가 싶습니다.
참고
시간과 머리가 허락한다면, wiki.haskell.org - Arrow 사이트에 있는 링크를 쫓아다니며 공부하면 Arrow 마스터!가 될 수도 있겠습니다만, 분량이 너무 많습니다.