Asymptotic Improvement of Computations over Free Monad - Janis Voigtländer

Leaf에 label을 붙인 binary tree는 ..

data F a = B a a deriving (Show, Functor)
type T a = Free F a

(이를 위해서는 DeriveFunctor 확장을 켜야함)

leaf a = return a
node a b = warp (B a b)

(여기서 wrap은 Free 생성자를 한번더 추상화한 것. MonadFree 에 선언)

fullTree :: (MonadFree F m) => Int -> m String
fullTree 0 = leaf ""
fullTree n = do
  s <- fullTree (n-1)
  node (leaf (s ++ "1")) (leaf (s ++ "0"))

> (fullTree 3) :: T String

Free (N (Free (N (Free (N (Pure "111") (Pure "110"))) (Free (N (Pure "101") (Pure "100"))))) (Free (N (Free (N (Pure "011") (Pure "010"))) (Free (N (Pure "001") (Pure "000"))))))

root부터 지그재그(왼쪽오른쪽왼쪽..)로 내려가서 맨끝 leaf찾는 함수 zigzag

zigzag :: T a -> a
zigzag = zig
  where zig (Pure a) = a
        zig (Free (N a b)) = zag a
        zag (Pure a) = a
        zag (Free (N a b)) = zig b


사실 fullTree n의 n에 linear하게 동작해야겠지만 zigzag (fullTree n)은 quadratic 복잡도로 동작한다. 이유는 fullTree로 생성되는 트리 구조가 leaf노드를 확장해나가는 방식이 painter 알고리즘과 같기 때문이다.

그림에서처럼 leaf노드가 확장될 때마다 루트까지의 부모 노드를 모두 새로 생성한다.

반면 zigzag (improve (fullTree n)) 은 linear하게 동작한다.

improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a

이때 fullTree가 선택하는 m은 Free F가 아니라 Codensity (Free F) 이다. 

이에 따라 zigzag (fullTree N)과 zigzag (improve (fullTree N))의 실행속도를 비교해보면 다음과 같다.

링크 http://www.janis-voigtlaender.eu/papers/AsymptoticImprovementOfComputationsOverFreeMonads.pdf

improve m = lowerCodensity m

[a]는 a가 무엇이든 Monoid가 됩니다.
Free Monad(Free f a)는 Functor f가 무엇이든 Monad가 됩니다. 말하자면 Free f a 는 f a의 리스트입니다. ([]에 해당하는 것이 return a)입니다.

(++) :: [a] → [a] → [a] 는 Monoid append입니다. 즉 두 개의 리스트를 이어붙입니다.
m >>= k :: Free f a → (a → Free f b) → Free f b 는 f a 리스트를 이어붙이는 것과 같습니다(append). 앞부분이 f f (return a) 로 끝나는 리스트이면, k a로 얻어지는 f f f (return b)응 이어붙여서 f f f f f (return b)가 됩니다.

a ++ b ++ c ++ d ... 는 O(n²) 의 시간복잡도를 가집니다. 왼쪽 우선 결합때문입니다.
m >>= f >>= g ... 역시 마찬가지입니다.

newtype DList a = DL { unDL:: [a] → [a] } 는 (a++) 형식으로 리스트를 표현하여 append를 상수 시간에 처리하고(함수합성), 누적 append의 결과를 최종 O(n)으로 구할 수 있습니다. (DList는 앞서 John Hughes의 difference list)

fromList = DL . (++) -- fromList as = DL (as ++)
append xs ys = DL (unDL xs . unDL ys)
toList = ($[]) . unDL

newtype Codensity m a = Codensity { runCodensity :: forall b. (a → m b) → m b} 는 (m >>=) 형식으로 Free monad를 표현하여 append(실제는 >>=)를 뒤쪽(오른쪽) 우선으로 합성하여 최종 결과를 O(n)으로 얻을 수 있습니다.

lift m = Codensity (m >>=)
m >>= k = Codensity (\c → runCodensity m (\a → runCodensity (k a) c)) -- k a 뒤에 c를 이어붙이고, 그 앞에 m을 prepend한다고 볼 수 있음
lowerCodensity a = runCodensity a return -- toList처럼 원래의 타입(모나드)로 돌아가려면 그냥 끝내기(return)하면 됨

Codensity의 장점은 Free Monad의 성능을 개선하기 위해 정말 짧은 코드만 필요하다는 것입니다. 컴파일러 지원이 필요하지도 않고 추가 구현도 필요없이.. 아래와 같은 한줄짜리 improve 만 끼워넣으면 된다는!!!

improve :: Functor f => (forall m. MonadFree f m => m a) → Free f a
improve m = lowerCodensity m

여기서 m은 Free f a 인데, 정확히는 Free f a 처럼 동작하는 Codensity (Free f) a입니다. 이것을 다시 lowerCodensity로 Free f a로 변환하는 것입니다.  Free f a는 왼쪽우선 >>=로 연결된 리스트지만 Codensity (Free f) a는 모두 오른쪽 우선 결합된 >>= 리스트가 되어서 결과적으로 >>=리스트를 순회하는(interpreting) 복잡도가 linear로 개선되는 것이죠.

(이를 위해서는! improve의 첫번째 타입처럼 MonadFree f m => m a, 즉 loose하게 생성되어야 합니다. 명시적으로 Free/Pure를 사용하는 대신 wrap/return으로 생성되어야 한다는 얘기입니다. 그래야 improve를 도입함으로써 wrap/return이 Free대신 Codensity로 적용되면서 improve가 동작할 수 있게 됩니다)

즉 run fa 라고 할 곳에 run (improve fa) 라고 하면 자동으로 속도가 빨라진다는 얘기!!! 놀랍죠. improve는 사실상 identity이지만 side-effect로 속도가 빨라지는 구조로 변환하는 역할을 합니다.

참고 http://www.janis-voigtlaender.eu/papers/AsymptoticImprovementOfComputationsOverFreeMonads.pdf

newtype DList a = DL { unDL :: [a] -> [a] }

newtype DList a = DL { unDL :: [a] -> [a] }

https://hackage.haskell.org/package/dlist-0.7.1.2/docs/Data-DList.html

Difference list는 List append를 O(1)에 할 수 있는 리스트 표현법이다.

append       :: DList a -> DList a -> DList a
append xs ys = DL (unDL xs . unDL ys)

DList는 prefix로 append할 내용을 함수 형태로 저장하기 때문에 두 DList를 합친다는 것은 함수 합성에 불과하다. 함수 합성은 당연히 상수시간.

write/append only. 

--

하스켈의 Difference list 

하스켈의 기본 리스트는 single linked list라서 a ++ b는 a의 길이만큼 시간이 걸리는데, 이 자체는 크게 문제가 안됩니다만 (a ++ b) ++ c 와 같이 왼쪽 우선 합성이기 때문에 여러개를 이어붙여야 하는 경우 처음에 a 만큼, 두번째는 a + b 만큼.. 이런식으로 prefix를 계속 반복하는 문제가 생깁니다. 일부러 a ++ (b ++ c)라고 우선순위를 조절할 수 있다면 모를까.. ㅠ.ㅠ 

Difference list는 (a++) . (b++) . (c++) 식으로 append가 되기 때문에 append 자체는 O(1)(함수합성)로 끝나고, append가 모두 끝난다음 한번에 []를 인자로 넘겨서 a ++ b ++ c(원하는 리스트)를 만들어냅니다. 이 과정은 맨 뒤 함수부터 적용되므로 앞서와 같은 a가 불필요가하게 반복되는 문제가 없습니다. 

이런 방법은 문자열에 특화된 type ShowS = String -> String 에서도 이미 적용되어 있습니다. 

scheduleFetches fetches = asyncs syncs (HAXL)

scheduleFetches :: [PerformFetch] → IO ()
scheduleFetches fetches = asyncs syncs
where
asyncs = foldr (.) id [f | AsyncFetch f ← fetches]
syncs = sequence_ [io | SyncFetch io ← fetches]

Haxl을 소개하는 There is no fork 페이퍼에 나오는 코드.
이 코드에 감탄한 사람들이 있다.

data PerformFetch = SyncFetch (IO ()) | AsyncFetch (IO() -> IO())

이 타입을 이해하기도 조금 헷갈린다. IO() -> IO() 부분이 그런데..이는 fetch::[BlockedRequest] -> PerformFetch 함수의 일반적인 구현을 봐야 이해가 된다.

myFetch reqs =
AsyncFetch $ \inner -> do
asyncs <- mapM fetchAsync reqs
inner
mapM_ wait async

async/await 패턴을 사용할 때 그 사이를 채우기 위한 인자를 받을 수 있다.
사실상 SyncFetch는 거의 없을 것 같긴 하다.

하나씩 따져보자.
fetches = [Async (\inner -> async f1 >> inner >> await f1), Sync f2, Sync f3, Async (\inner -> async f4 >> inner >> await f4)] 로 주어지면, (async/await은 우선 개념적으로만)

scheduleFetches는 async f1 >> async f4 >> f2 >> f3 >> await f4 >> await f1 처럼 동작하는 IO()를 만들어준다! (그러니 scheduleFetches라는 이름이 나오는 것)

asyncs = foldr (.) id [f | AsyncFetch f <- fetches]
= foldr (.) id [\inner -> async f1 >> inner >> await f1, \inner -> async f4 >> inner >> await f4]
= (\inner -> async f1 >> inner >> await f1) . (\inner -> async f4 >> inner >> await f4)
= \inner -> (\inner -> async f1 >> inner >> await f1) ((\inner -> async f4 >> inner >> await f4) inner)
= \inner -> (\inner -> async f1 >> inner >> await f1) (async f4 >> inner >> await f4)
= \inner -> async f1 >> (async f4 >> inner >> await f4) >> await f1

syncs = sequence_ [io | SyncFetch io <- fetches]
= sequence_ [f2, f3]
= f2 >> f3

asyncs syncs = (\inner -> async f1 >> (async f4 >> inner >> await f4) >> await f1) (f2 >> f3)
= async f1 >> (async f4 >> (f2 >> f3) >> await f4) >> await f1

AsyncFetch 를 위해서는 async 패키지 같은 걸 쓴다고 봐야한다. (이 패키지 만든 사람이 Simon Marlow다)

g(f input)

g (f input)

-- Why Functional Programming Matters by John Hughes

 부연설명이 필요하다.

f는 input을 output으로 .. output은 다시 g의 input이 된다. Haskell은 f와 g를 함께 실행할 수 있다. 즉, f와 g의 실행이 overlap되는 것. 그럼에도 input/output으로 엄격히 동기화된다. 

g가 입력을 읽을 때 비로소 f가 시작되고, f는 출력을 만들고 나면 suspend된다. g가 또 입력을 읽으려 하면 f는 resume하여 또 출력을 만들 수 있다. 

g와 f는 코루틴으로 동작하는 셈이다!