Understanding Clojure transducers through types

transducer.hs

-- http://conscientiousprogrammer.com/blog/2014/08/07/understanding-cloure-transducers-through-types/

-- Transducer의 자료형을 만들기 위해서는 Rank-2 type이 필요하다.
{-# LANGUAGE RankNTypes #-}

-- 함수형 프로그래밍에서 함수는 1급 시민이다. 함수를 조합하고 변환하는 것은 매우 평범한 것이다.
-- h = (f . g)라면 f (g x) = h x 이다.
-- reducer는 reduce에서 사용되는 함수에서 다양한 how를 제거하고 일반화하여 정의한 것이다.
-- 그리고 transducer는 reduce를 새로운 reducer로 변환시키는 함수이다.
-- haskell의 type system은 새로운 것에 대한 명확한 이해에 도움을 준다.

-- reducer는 r형과 a형을 받아서 r형을 반환하는 함수이다.
-- foldl (\s i -> s ++ (show i)) "" [1..10] 이라면
-- \s i -> s ++ (show i)는 String -> Integer -> String 형을 가지는 Reducer이다. 
type Reducer a r = r -> a -> r
-- transducer는 reducer를 변환시키는 함수이다. 함수를 입력받아 반환하는 함수이므로 고차함수라고 할 수 있다.
--type Transducer a b = Reducer a r -> Reducer b r
type Transducer a b = forall r . Reducer a r -> Reducer b r

-- reducer의 장점이라면 reducer의 조합을 통해서 중간 결과물 없이 연속적인 처리가 가능하다는 것이다.
-- 보통 프로그래밍언어에서 f 랑 g함수를 사용하려면 f를 실행하고 나온 결과에 g를 다시 실행해야 한다.
-- 그러나 reducer를 사용하면 (g . f)로 조합된 함수를 한번에 실행시켜버려서 더 효율적으로 동작하게 된다.
-- 이보다 중요한 것은 associative한 속성을 가졌다면 이것을 분할하여 병렬처리하는 것도 가능하다.
-- monoid라는 것을 들어본 적이 있을 것이다. monoid의 조건을 만족시키면 monoid의 특징을 사용할 수 있다.
-- 이는 병렬처리를 가능하게 해주는 중요한 특징이다.

--class Foldable f where
--  fold :: Transducer a (f a)

-- fold와 conj를 지원하는 Conjable과 Foldable typeclass를 만든다.
class Conjable f where
  empty :: f a
  conj :: Reducer a (f a)

--instance Foldable [] where
--  fold = foldl

-- 여기서는 예제를 위해서 List에 대해서 Foldable과 Conjable을 instance화 한다.
instance Conjable [] where
  empty = []
  conj xs x = xs ++ [x]

-- reducer를 받아서 map을 합성해주는 transducer를 보자
-- a를 받아 b를 반환하는 함수의 map을 합성해주는 transducer를 만들어준다.
-- 주석처리한 좀 더 저수준의 정의를 참고하면 이해가 쉬울 것이다.
--mapping :: (a -> b) -> (r -> b -> r) -> (r -> a -> r)
-- 아래 함수정의랑 입력인자수가 안 맞는 것처럼 보일텐데
--mapping :: (a -> b) -> (r -> b -> r) -> r -> a -> r
-- 처럼 하면 이해가 쉬울것이다.
-- 별거 없다. reducer로 들어가는 입력값에 f함수를 적용한 값을 넣게 한다.
mapping :: (a -> b) -> Transducer b a
mapping f xf r a = xf r (f a)

-- 필터도 간단
-- p는 pred의 참/거짓 여부에 따라서 필터링을 한다.
filtering :: (a -> Bool) -> Transducer a a
filtering pred xf r a = if pred a then xf r a else r

-- 요거는 Foldable을 반환하는 함수에 대해서 fold를 하는 것인데..
-- n을 입력받아 [0..n]을 반환하는 함수가 있을때 flatmap을 [1..3]적용하면 [0,1,0,1,2,0,1,2,3]이 나온다.
flatmapping :: Foldable f => (a -> f b) -> Transducer b a
flatmapping f xf r a = foldl xf r (f a)


-- 이제 우리는 mapping, filtering, flatmapping을 가지고 쉽게 transducer를 만들 수 있다.

-- xlist는 transducer를 받아서 Foldable하고 Conjable 한 f b를 입력하면 f a를 반환하는 함수를 만든다.
-- 쉬운 예를 위해 f를 List라 하면
-- Transducer Integer String을 넣으면 Integer의 List를 받아 String의 List를 반환하는 함수를 만들어준다.
-- xf를 Reducer인 conj에 적용하여 새로운 Reducer를 만들어 reducing하는 것이다.
--conj xs x = xs ++ [x]
--xlist :: ((r -> a -> r) -> (r -> b -> r)) -> [b] -> [a]
xlist:: (Foldable f, Conjable f) => Transducer a b -> f b -> f a
xlist xf = foldl (xf conj) empty

-- xlist를 활용하여 map, filter을 만들어 보았다.
-- 지금까지 이해하면서 따라왔다면 아래도 이해가 쉬울 것이다.
xmap :: (Foldable f, Conjable f) => (a -> b) -> f a -> f b
--xmap :: (a -> b) -> [a] -> [b]
xmap f = xlist $ mapping f

xfilter :: (Foldable f, Conjable f) => (a -> Bool) -> f a -> f a
xfilter p = xlist $ filtering p

-- 자 마지막 예이다. 
-- transducer도 함수이므로 조합이 가능하다.
-- 3개의 transducer를 조합하여 xform이라는 새로운 transducer를 만들었다.
xform :: Transducer Int Int
xform = mapping (+ 1) . filtering even . flatmapping (\x -> [0..x])

-- 그리고 xform을 xlist를 사용해 동작시켜본다.
munge :: (Foldable f, Conjable f) => f Int -> f Int
munge = xlist xform

-- 아래는 실행예이다.
-- Prelude> munge [1..3]
-- [0,1,2,0,1,2,3,4]

-- 자 지금까지 본 것처럼 transducer라는 일반화를 통해서 reducer의 세부구현과 독립된 reducer를 다루는 고차함수를
-- 만들 수 있다.
-- transducer를 사용하면 겉보기로는 기존의 map, filter 등을 사용하는 것과 크게 다르지 않지만 훨씬 강력한 reducer를
-- 조합하거나 변환시키면서 보다 강력하게 사용할 수 있다.