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)];

do-while one-liner

List<E> cached = new ArrayList<E>();
do
  cached.add(persistableResource.loadFrom(cursor));
while (cursor.moveToNext());
return cached;

GitHub Android Client 코드 중에서 do-while의 중괄호마저 빼버린 코드를 봤다. 나름 잘 읽힌다. cursor를 Collection으로 보고 mapping한 것 같기도 하고.
이 코드에서 특히한 또다른 점은 try-finally 짝을 적극적으로 사용한다는 점이다.

list_entry 매크로

#define list_entry(ptr, type, member) \
  ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

리눅스 커널에 사용된 링크드리스트에서 제공하는 매크로. list_node 포인터로부터 원래 구조체의 포인터를 얻기 위해 사용한다.