cyclic list - ugly numbers (leetcode #264)

리트코드 문제를 풀다보면 cyclic list 문제를 더러 만난다. 이 문제도 마찬가지.
먼저 문제를 보자.

2,3,5만을 소인수(prime factor)로 가지는 수를 ugly number라고 했을때 n번째 ugly number를 구하라!

prime number 수열을 계산하는 에라토스테네스의 체(sieve)와 비슷한 문제다. 이미 계산된 ugly number에 다시 2를 곱하고, 3을 곱하고, 5를 곱해서 뒤에 나오는 ugly number가 구해진다.

맨 앞에 1이 있고, 여기에 2,3,5를 각각 곱하여 2,3,5가 구해진다.

1 -> 2,3,5

그 다음 ugly number는 2가되고, 2에 다시 2,3,5를 곱하면 4,6,10이 되는데, 이미 구했던 3이 더 작으니 3이 그 다음 ugly number가 된다.

1,2 -> 3,5   4,6,10

1,2,3 -> 5  4,6,10   6,9,15

1,2,3,4 -> 5   6,10    6,9,15    8,12,20

1,2,3,4,5 -> 6,10   6,9,15   8,12,20   10,15,25


이렇게 ugly number가 하나씩 결정될 때마다 그 뒤에 이어질 ugly number들을 계산할 수 있다.

이런 문제는 Haskell의 cyclic list로 풀면 딱이다.

ugly = 1 : merge (map (2*) ugly)  (map (3*) ugly)  (map (5*) ugly)

여기서 merge는 각 리스트에서 최소값을 꺼내고, 그 값을 뺀 나머지에 대해 같은 과정을 반복한다.

merge as bs cs =
   let next = minimum (map head [as,bs,cs])
   in next : merge (skip next as) (skip next bs) (skip next cs)

skip x (a:as) = if x == a then as else (a:as)

-- UPDATE

하스켈 같은 취미 언어는 금새 까먹는다.  2년 전에 이미 풀어본 거다. 그런데 이전에 푼 게 더 낫네. ㅠ.ㅠ

Go - io.Pipe()

Go 인터페이스 중 가장 흔히 쓰이는 것이 io.Reader/Writer 일 거다.

그런데 여기에 Go의 강점인 goroutine 이 결합되어서 빛을 발하게 되는 것이 io.Pipe() 아닐까 싶다.

r,w := io.Pipe()

호출하면 Reader/Writer 를 얻어내는데, 이 둘은 파이프로 연결된 양쪽 끝이다. w(Writer)로 쓰는 내용을 r(Reader)에서 읽을 수 있다.

Reader가 필요한 코드와 Writer가 필요한 코드를 연결시킬 때 쓰면 좋다.

예를 들어 multipart/form-data 로 파일을 POST 한다고 보자.

요청 객체는 아래처럼 Reader를 요구한다.

http.NewRequest("POST", url, bodyReader)

보낼 파일은 os.Open(path) 로 열어서 얻을 수 있는데, *File 은 Reader 인터페이스를 만족한다.

그렇다고 NewRequest(... file) 처럼 바로 전달할 수 없는 것이, "multipart/form-data" 형식을 맞춰줘야 하기 때문이다. 그리고 이 형식 맞추기를 도와주는 것이 multipart.Writer 타입이다.

multipart.NewWriter(w) 로 만들 수 있으며, 다른 io.Writer w를 래핑하여 "multipart/form-data" 형식으로 데이터를 쓸 수 있게 해준다.

앞서 얘기한 것처럼, 우리가 필요한 것은 (body)Reader인데 multipart.Writer는 다른 Writer를 필요로 한다. io.Pipe()를 쓰기 딱 좋은 순간이다.

그런데,

구글에 "golang request multipart file" 로 검색해보면 몇가지 예제들을 볼 수 있다.

대부분은 bytes.Buffer 를 만들고 이를 multipart.Writer 로 래핑한다. bytes.Buffer는 Writer 인터페이스를 통해 데이터를 기록할 수도 있지만 동시에 Reader이기도 해서 Reader와 Writer가 필요한 이 상황에 쓰일 수 있다. 우선 Writer 인터페이스를 이용하여 버퍼를 채우고, Reader 인터페이스로 다시 읽으면 된다.

var buf bytes.Buffer
w := multipart.NewWriter(&buf)
~~~
req := http.NewRequest(...,&buf)

이 방법은 단점이 있다. 바로 보내려는 데이터 크기만큼 bytes.Buffer에 쌓아야 해서 메모리 부담이 커진다는 것이다.

io.Pipe()를 사용하면 어떨까? io.Pipe()로 생성되는 io.Reader와 io.Writer를 bytes.Buffer 처럼 사용하면 된다.

pr, pw := io.Pipe()
w := multipart.NewWriter(pw)
req := http.NewRequest(...,pr)

앞에서 bytes.Buffer의 경우는 Reader를 사용하기 전에 Writer로 내용을 채워야 했다.
그런데 io.Pipe()는 Consumer/Producer 처럼 동기화되어 동작하기 때문에 미리 채우고 나중에 읽고, 이런식으로 동작할 수 없다.

goroutine이 필요한 순간이다. Reader 를 사용하는 코드와 Writer 를 사용하는 코드는 서로 다른 고루틴에서 실행되어야 한다. io.Pipe()는 사실 채널 몇개를 만들어 줄 뿐이다. 각 Reader/Writer는 이 채널에 데이터를 쓰고, 채널에서 데이터를 읽는 것이다.

pr, pw := io.Pipe()
w := multipart.NewWriter(pw)
go ~~~
req := http.NewRequest(...,pr)

이제, 파일이 크다고 하더라도 조금씩 읽어서 (Read) 읽은 만큼 쓰기 (Write) 를 반복하면 메모리 부담 없이 전송할 수 있다.

io.Pipe() 가 Writer ---> Reader 를 연결하는 채널을 만들어 주는 것이라면 반대로 Reader ---> Writer 의 연결은 io.Copy(w,r) 가 처리한다.

Go - sort / reverse

Go는 generics 혹은 parametric polymorphism 을 지원하지 않아서 generic collection 같은 걸 만들기가 어렵다.

container/list 패키지를 보면 아래처럼 interface{} 타입을 써서 어떤 값이든 담을 수 있게 했다.

sort 패키지를 보면 1) 크기 비교 가능하고, 2) 랜덤 액세스를 통해 swap 연산이 되며, 3) 전체 길이가 알려진 경우를 인터페이스로 정의하여 정렬 알고리즘을 일반화하였다.

이 경우는 interface{} 타입을 사용하는대신 '인덱스'만으로 알고리즘을 전개할 수 있게 했다.

대개 다른 언어들이 '비교 가능한 요소'들을 대상으로 비교 함수가 만들어지는데, 인덱스를 사용한 것이 특이하다. 비교 함수를 뒤집어서 역순 정렬을 하려면?

Reverse 함수로 interface 값을 한번더 래핑하면 된다.

Reverse 함수의 반환값을 보면 &reverse{data} 인데, 여기서 data 도 sort.Interface 타입이고함수의 반환타입 역시 sort.Interface다. (즉, sort.reverse 구조체는 decorator 나 wrapper 같은 역할을 한다.)

여기서 특이한 점은, 1) Reverse 함수가 왜 포인터를 반환하느냐? 2) Less 메쏘드의 리시버 타입은 왜 밸류 타입인가?

사실 Reverse 함수를 밸류로 반환해도, 이미 reverse 구조체가 sort.Interface 인터페이스를 구현하기 때문에 (임베드하면서 Less만 오버라이드) 정렬 기능에는 문제가 없다. 혹은, 포인터를 반환하여 (sort.Interface로) 래핑하기 때문에 Less 함수의 리시버가 *reverse 타입이어도 문제없다.

왜 이것도 되고, 저것도 되는데 위의 모양을 가지게 되었을까?

추측컨데,

1) Reverse 함수의 반환 값이 인터페이스이므로 포인터를 반환함으로써 어떠한 리시버도 가능할 뿐 아니라 인터페이스 값을 만드는 비용이 저렴하다.

2) Less 메쏘드는 리시버 (reverse 구조체) 내부를 건드리지 않는다. 즉, 포인터를 사용할 이유가 없는 것이다. (만일 메쏘드 리시버가 밸류로 선언되어 호출 시 리시버 값이 복사되는 것이 부담된다면 포인터 타입으로 리시버를 사용할 수 있겠지만 reverse 구조체는 sort.Interface 인터페이스만 임베드하고 있어서 two-word 크기를 가진다. 복사 비용이 부담되지 않으므로 일부러 포인터 타입의 리시버로 정의할 필요가 없다.

Go - random initialization vector

crypto/cipher 패키지의 NewCBCEncrypter 예제를 보자.

encryption을 하려면 아래처럼 Block 과 iv 를 이용하여 BlockMode encrypter를 만들고, 여기에 CryptBlocks(dst,src []byte) 메쏘드를 불러야 한다.

mode := cipher.NewCBCEncrypter(block, iv)
mode.CryptBlocks(ciphertext[aes.BlockSize:], plaintext)

여기서 iv 는 secure 할 필요는 없지만 무작위여야 하는데...

아래처럼 간단히 처리할 수 있다.

io.ReadFull(rand.Reader, iv)

혹은 더 간단히,

rand.Read(iv)

type List[A] = Free[({type λ[+α] = (A, α)})#λ, Unit]

Stackless Scala With Free Monads
Rúnar Óli Bjarnason <-- to type 'ú' : Option e + u
2014


문제: State 모나드가 있다.

def zipIndex[A](as: List[A]): List[(Int, A)] = ...

List[A]를 Index와 pair로 만들어주는 zipIndex를 구현하는데...
여기 굳이 State 모나드를 사용할 필요는 없다.

하지만 여기선.. 문제 상황을 만들기 위해 굳이 State 모나드를 사용할 수 있다.

case class State[S,+A](runS: S => (A, S)) {
  def map
  def flatMap
}

def get[S]: State[S,S] = State(s => (s,s))
def put[S](s:S): State[S,Unit] = State(_ => ((),s))
def pure[S, A](a:A): State[S,A] = State(s => (a,s))

index를 상태로 본다면, 0에서 시작, 1씩 증가시키면서 설정하면 된다. State[Int, List[Int,A]]인 셈.

def zipIndex[A](as: List[A]): List[(Int, A)] =
 as.foldLeft(pure[Int, List[(Int,A)]](List()))((acc,a) => for {
  xs <- acc
  i <- get
  _ <- put(i+1)
} yield (i, a) :: xs).runS(0)._1.reverse

foldLeft는 tailrec이지만, 여기서는 그 결과가 State[Int, List[(Int,A)]]의 연산 과정. runS(0)에서 비로소 전체 List를 순회하면서 0,1,2,...상태가 바뀌고 List를 만들어낸다. 이 과정은 State.flatMap의 체인으로 진행.

그런데.. flatMap 구현을 보면..

case class State[S,+A](runS: S => (A, S)) {
  def flatMap[B](f: A => State[S,B]): State[S,B] =
    State[S,B](s => { val (a,s') = runS(s); f(a).runS(s') })
}

runS를 부르면 flatMap을 부르고, flatMap은 runS를 부르고, 다시 flatMap을 부르고... 그래서 List가 크면 금방 StackOverflowError가 뜬다.

이 문제는.. 사실 Scala에서 좀더 엄격하게 함수형 프로그래밍을 하고자 할 때 발생한다. 함수형 프로그래밍을 널리 전파하려는 Rúnar 입장에서는 이 문제를 해결해줘야 사람들 불만이 없을 거다.

해결책:

1. TailRec보다 좀더 일반화된 Trampoline(monad)
2. Trampoline에서 StackOverflowError를 회피하고 -- flatMap을 타입으로 표현한 것이 주요 방법
3. 이를 일반화시켜 Free Monad를 완성

그래서 Haskell Free Monad와 다른 모양이 나오게 되었다.

data Free f a = Pure a | Free f (Free f a)

sealed trait Free[S[+_], +A] {
 private case class FlatMap[S[+_],A,+B](a: Free[S,A], f: A => Free[S,B]) extends Free[S,B]
}

case class Done[S[+_],+A](a: A) extends Free[S,A]
case class More[S[+_],+A](k: S[Free[S,A]]) extends Free[S,A]

Done/More는 각각 Pure/Free에 매핑되는데, FlatMap은 스택 문제로 추가된 것이다.

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