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는 코루틴으로 동작하는 셈이다!

non-deterministic calculation

며칠전 '별다방손코딩'을 다른 이들에게 소개하며 같이 풀어본 문제다. 쉬워보여서.. https://www.hackerrank.com/challenges/manasa-and-stones

0에서 시작하여 (a 혹은 b)를 (n-1)번 더했을 때 나올 수 있는 값을 모두 찾으라는 것인데, 문제 자체는 매우 간단해서 a만 (n-1)번 더한 것과 b만 (n-1)번 더한 것을 n개의 등차수열로 만들면 된다.

하지만 문제가 말하는 바 그대로를 살펴보면 non-deterministic calculation이다. 즉 0에 x를 n번 더한 결과는? 당연히 x*n이지만.. x가 (a 혹은 b)라면 그 결과가 어느 한 값이 아니라 위처럼 여러 가능한 값을 가진다. 심지어 n이 (c 혹은 d)라면? x가 세 값 중 어느 값이라면? .. 더하기 뿐 아니라 연산이 더 복잡하다면?

Haskell에서는 non-deterministic value를 List로 표현하였을 때 (+) 연산을 lifting해주는 것만으로 쉽게 답을 구할 수 있다.

iterate (+ x) 0 == [0, x, 2*x, 3*x, ...]  -- 0에 '더하기 x'를 반복 적용하는 것이다.
[a,b,c] !! 2 == c    -- (!!)는 index 연산자다.
iterate (+ x) 0 !! (n-1)  --  0에 x를 n-1번 더한 값을 얻을 수 있다.

(+)는 Num -> Num -> Num 이지만, x 가 [1,2] 가 된다면 바로 적용할 수 없으므로 lift해줘야 한다.

iterate (liftA2 (+) x) [0] !! (n-1)

여기엔 중복된 값이 있으므로 마지막에 nub(유일 값만 추출하기)을 적용하면 된다.

lastStone n a b = nub $ iterate(liftA2 (+) [a,b]) [0] !! (n-1)

(.:) = (.) (.) (.) -- concatMap

Haskell의 함수중 (.)만큼 많이 쓰이는 것이 있을까? compose 연산자다.

f . g = f (g x) 

그런데 (.)의 두번째 인자는 입력을 하나만 처리한다. concat xss 와 map f xs 의 concat 과 map 을 합성하려면?

concat . map -- 성립하지 않는다.

map 을 인자 하나면 처리하면 여전히 함수이며, 이는 concat의 입력타입([[x]])과 일치하지 않기 때문이다. 그래서...

concatMap f = concat . map f

map의 첫 인자를 적용한 상태로 합성하면 된다.  하지만 f를 제거하여 합성하고 싶다면???

concatMap = concat .: map

여기서 (.:)는 외우기 참 쉬운데, 정의는 모양 그대로 점셋(.:)을 펼쳐놓은 것 (.)(.)(.) 이며, 타입 역시 모양 그대로 왼쪽점 하나(왼쪽항이 인자 하나), 오른쪽 점 둘(오른쪽 항이 인자 둘을 처리)의 합성이다.

(.:) :: (c->d) -> (a->b->c) -> a->b->d
(.:) = (.)(.)(.)

length(intersect(friendsOf x)(friendsOf y))

Facebook의 HAXL소개에 늘 나오는 대표적 예제

iterate(group>=>(sequence[length,head]))[1]

국내엔 개미수열로 알려진 'look and say' 수열

#define BITS_TO_BYTES(bits) ((bits)/8 + !!((bits)%8))

C에서 비트필드배열 만들 때 쓸만할 것 같음.

#define BITS_A 5
#define BITS_B 3
#define BITS_C 2
char bitfield[BITS_TO_BYTES(BITS_A + BITS_B + BITS_C)];