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