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 에서도 이미 적용되어 있습니다.