liftM
liftM :: Monad m => (a1 -> r) -> m a1 -> m r
타입 선언으로 보면, 이는Functor의fmap그 자체입니다:
fmap :: Functor f => (a -> b) -> f a -> f b
context 가Monad로 바뀌었을 뿐, 그 외에는 차이가 없습니다. 또한 Functor laws 와 Monad laws 를 준수하는 타입의 경우, 이 두 함수는완전히 동등합니다. 예를 들어:
> liftM (+1) (Just 1)
Just 2
> fmap (+1) (Just 1)
Just 2
liftM의 구체적인 구현은 다음과 같습니다:
liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r
liftM f m1 = do { x1 <- m1; return (f x1) }
이는 다음과 동등합니다:
liftM' f m = m >>= \x -> return (f x)
주의할 점은, 이 구현이Functor의 특성에 의존하지 않고,Monad가 가진 동작만으로 완료할 수 있다는 것입니다 (게다가 Monad laws 를 준수하면fmap과 완전히 동등해지며, context 를 가진 값에 함수를 적용하기만 하고 불필요한 일은 하지 않습니다). 이 관점에서 보면,Monad가Functor보다 더 강력합니다
Monad가Functor보다 강력하다는 것은 증명되었지만,Applicative는 어떨까요?
Applicative에서 가장 중요한 것은 이것입니다:
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
실제로Monad로도 구현할 수 있으며,ap라고 합니다:
ap :: Monad m => m (a -> b) -> m a -> m b
쉽게 구현할 수 있습니다:
mf `ap'` m = do
f <- mf
x <- m
return (f x)
따라서,Monad는Applicative보다 더 강력합니다. 더 나아가서, 커스텀Monad를 구현하려면 먼저return과>>=를 구현하면 쉽게Applicative(<*> = ap, pure = return) 와Functor(fmap = liftM) 를 구현할 수 있습니다
liftA2(liftA3까지) 가 있다는 것을 알고 있습니다. 이는 "다중 인자" 함수에 대응하기 위한 것입니다:
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
실제로는 대응하는liftM2(liftM5까지) 도 있습니다:
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
예를 들어:
> liftM2 (+) (Just 1) (Just 1)
Just 2
> liftM3 (\x y z -> x + y + z) (Just 1) (Just 2) (Just 3)
Just 6
fmap에서liftM로, 그리고liftM5까지 이해하기 쉽습니다
join
monadic value 의 value 가 여전히 monadic value 인 상황에 직면할 수 있습니다. 예를 들어:
Just (Just 1)
그렇다면 내側の monadic value 를 어떻게 꺼낼 수 있을까요?join함수를 사용할 수 있습니다:
join :: Monad m => m (m a) -> m a
시험해 봅시다:
> join (Just (Just 1))
Just 1
> join Nothing
Nothing
> join (Just (Just (Just 1)))
Just (Just 1)
주의할 점은, 타입상에서 내측과 외측의Monad가 같아야 한다는 것입니다 (둘 다m). 따라서join (Just [1])등은 정상적으로 작동하지 않습니다
위의Maybe예제로 보면,join은 실제적인 의미가 없는 것처럼 보입니다. 다른Monad를 살펴봅시다:
> join [[1, 2], [3], [4, 5]]
[1,2,3,4,5]
> join (writer (writer (1, "a"), "b")) :: Writer String Int
WriterT (Identity (1,"ba"))
조금 join(연결) 이라는 의미가 있습니다. 내측 monadic value 를 꺼낸 후 어떤 연산도 수행하는 것 같습니다. 추측컨대 다음과 같습니다:
join' mm = do
m <- mm
m
이는 다음과 동등합니다:
join'' mm = mm >>= (\m -> m)
-- 즉
join'' mm = mm >>= id
그렇다면 내측 List 는 누구에 의해 연결되는 것일까요? List 의>>=구현은 List Comprehension 입니다:
xs >>= f = [y | x <- xs, y <- f x]
따라서 List 의 상황에서는 다음과 동등합니다:
joinList xss = xss >>= (\xs -> xs)
joinList' xss = [y | x <- xss, y <- id x]
Writer의 상황은 List 와 유사하며, 연산은 모두>>=에 의해 완료됩니다. Maybe에 연산이 없는 것도 그>>=구현 때문입니다:
(Just x) >>= k = k x
Nothing >>= _ = Nothing
join의k는id이므로, 내측Maybe값을 그대로 꺼낼 뿐입니다
P.S.또한,재미있는 것이 있습니다:
m >>= f = join (fmap f m)
즉>>=는 변환 함수 (f :: a -> m b) 로 monadic value(m) 를 매핑하여 monadic monadic value 를 얻고, join으로 내측 monadic value 를 꺼내는 것이 최종 결과입니다:
> fmap (\x -> return (x + 1)) (Just 1) :: Maybe (Maybe Int)
Just (Just 2)
> join (Just (Just 2))
> Just 2
> Just 1 >>= (\x -> return (x + 1))
Just 2
실제로,이 동등 관계는>>=를 구현하는 또 다른思路를 제공합니다. join만 구현하면 됩니다. 이는 커스텀 Monad instance 를 구현할 때 특히 유용합니다. >>=를 어떻게 구현해야 Monad laws 를 준수할 수 있을지 모를 경우, 각도를 바꿔 네스트된 monadic value 를 평평하게 하는join을 구현하는 것을 고려해 보세요
filterM
일반적인filter와 유사합니다:
filter :: (a -> Bool) -> [a] -> [a]
filterM은 이렇습니다:
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]
주의할 점은, predicate 함수 (a -> m Bool) 의Bool반환값에 context 가 추가되었다는 것입니다. 이것이 어떤 효과가 있을까요?
필터링 처리 중에 context 를 추가할 수 있으며, 결과 (m [a]) 에 유지됩니다. 예를 들어:
> graterThan2 = filterM (\x -> if (x > 2) then writer (True, [show x ++ " reserved"]); else writer (False, [show x ++ " discarded"])) [9, 5, 0, 2, 1, 3] :: Writer [String] [Int]
> fst . runWriter $ graterThan2
[9,5,3]
> mapM_ putStrLn (snd . runWriter $ graterThan2)
9 reserved
5 reserved
0 discarded
2 discarded
1 discarded
3 reserved
List 를 필터링하는 동시에,Writer Monad를 사용하여 작업 로그를 기록합니다. 특히버려진 요소도 관련 정보를 기록합니다 (예를 들어0 discarded). 매우 흥미롭습니다
더흥미로운 사용법이 있습니다:
powerset :: [a] -> [[a]]
powerset = filterM (\x -> [True, False])
이상한 함수를 정의했습니다. 배열을 받아 이차원 배열을 반환합니다. 시험해 봅시다:
> powerset [1, 2, 3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
작용으로 보면 멱집합 (집합의 모든 부분집합으로 이루어진 집합. 공집합과 자신 포함) 을 구하는 함수입니다. filterM이 어떻게 구현했는지 생각해 봅시다?
predicate 함수\x -> [True, False]는 동시에 여러 결과를 반환합니다: 유지와 폐기. 이는 List 의non-deterministic 문맥의 응용입니다:
[a] 는 동시에 많은 결과를 가진 computation 을 나타냅니다 (non-deterministic computation)
non-deterministic 계산은 여러 결과를 생성할 수 있으므로,powerset상황에서 멱집합을 구하는 효과적인 방법은: 집합의 각 요소를 순회하며 두 가지 작업 (유지하기와 버리기) 을 수행하고 작업 결과를 수집하는 것입니다
filterM의 구현을 살펴봅시다:
filterM :: (Applicative m) => (a -> m Bool) -> [a] -> m [a]
filterM p = foldr (\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)) (pure [])
(Control.Monad 에서 인용)
foldr은 배열을 순회하며, 초기값은pure [], 누산 함수 (accumulator) 는\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)입니다. 현재 요소에liftA2로 매핑하며,p x의 결과에 따라x:또는id를 반환합니다 (유지하는 경우, 현재 요소를 결과 집합에 삽입. 폐기하는 경우, 결과 집합은 원래대로)
조금 혼란스럽지만, 파라미터를 보완하면 실제로는 이렇습니다:
\ x ma -> liftA2 (\ flg a -> if flg then (x: a) else id a) (p x) ma
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b는 이항 함수를 받아, 파라미터 순서는 현재 요소와 누산 결과 (각각 위의x와ma에 해당.ma의 초기값은pure []) 입니다. liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c는 이항 함수를 두 개의 monadic value(각각p x와ma) 에 적용하여 monadic value 를 반환합니다. 마지막으로, 이러한 monadic value 들은foldr에 의해mappend로 접혀 최종 결과를 얻습니다
P.S.맞습니다.foldr의 구현에는foldMap :: Monoid m => (a -> m) -> t a -> m이 사용되었습니다. 자세한 내용은 Data.Foldable 참조
foldM
foldl에 대응하는 monadic 버전을foldM이라고 합니다:
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
예를 들어:
> foldl (\a x -> a + x) 0 [1..10]
55
P.S.작은 세부 사항이지만,foldl과foldr의 누산 함수 파라미터 순서는 반대입니다. 전자는a v, 후자는v a입니다
foldl에 계산 문맥 (예를 들어 실패할 수 있는 문맥) 을 추가하려면,foldM으로 쉽게 처리할 수 있습니다:
> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..10]
Just 55
> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..100]
Nothing
이 상황에서는 합계가99를 초과하면 큰 수 오버플로우로 간주하여 계산 실패로 간주합니다
foldM의 구현을 추측해 봅시다:
foldM' acc a xs = foldl (\ma v -> ma >>= (\a -> acc a v)) (return a) xs
중요한 점은누산값의 context 를 유지하는 것으로, 연산에 참여 (acc에 전달) 할 때는 제거하고, 순회할 때 추가합니다. 표준 (라이브러리) 답은 이렇습니다:
foldM = foldlM
foldlM f z0 xs = foldr f' return xs z0
where f' x k z = f z x >>= k
잠깐만요,f z x >>= k에서 무슨 일이 일어난 것일까요?
f 는 누산 함수
z0 는 초기값
xs 는 Foldable 인스턴스
z 는 누산값
x 는 현재 요소
k 는? return 처럼, 일반값을 받아 context 를 가진 값을 반환
한 단계씩 살펴보면, 그 중f'의 타입은:
f' :: Monad m => t -> (a -> m b) -> a -> m b
foldr의 타입은:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
가장 이해하기 어려운 것은:
(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b
이 단계에서 무슨 일이 일어난 것일까요?
foldr에 파라미터 하나만 주는 경우, 이항 함수a -> b -> b가 필요하고, 두 번째 파라미터와 반환값 타입은 같아야 합니다. 따라서*f'를 보는 자세를 바꿔야*합니다:
f' :: Monad m => t -> (a -> m b) -> (a -> m b)
이때b는a -> m b에 해당하며,foldr에 대응합니다:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
-- (a -> b -> b) 는 f' 에 의해 채워지고, 나머지 b -> t a -> b. b 를 a -> m b 로 교체
foldr f' :: Foldable t => (a -> m b) -> t a -> (a -> m b)
-- 즉
(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b
다음으로 3 개의 파라미터를 줍니다. 각각:
return :: (a -> m b)
xs :: t t1
z0 :: a
원활하게m b를 반환합니다
P.S.이렇게 교묘한 변환이 가능한 이유는 Haskell 함수의 기본 커링 특성 때문입니다. 파라미터를 채워야만 값을 반환합니다. 따라서:
f' :: Monad m => t -> (a -> m b) -> a -> m b
-- 동등
f' :: Monad m => t -> (a -> m b) -> (a -> m b)
이해하기 쉽습니다.f' :: Monad m => t -> (a -> m b) -> (a -> m b)는 두 개의 파라미터를 받아a -> m b함수를 반환합니다 (이��에는 3 개의 파라미터를 받아m b값을 반환했습니다)
비슷하게, 이렇게 할 수 있습니다:
f :: (Num b, Monad m) => b -> (t -> t1 -> m b) -> t -> t1 -> m b
f a b c d = b c d >>= \v -> return (v + a)
foldr f에 대응하는 타입은:
foldr f :: (Foldable t, Num b, Monad m) => (t1 -> t2 -> m b) -> t b -> t1 -> t2 -> m b
시험해 봅시다:
> foldr f (\x y -> return (x + y)) [1..10] 0 0
55
P.S.표준 답의 힌트를 받아, 파라미터 순서를 변경하여 lambda 를 하나 줄일 수 있습니다:
foldM'' acc a xs = foldr (\v ma -> ma >>= acc v) (return a) xs
합성
함수는 합성할 수 있다는 것을 알고 있습니다:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g . h는 오른쪽에서 왼쪽으로 합성합니다. 예를 들어:
> ((+1) . (/2) . (subtract 1)) 7
4.0
monadic function 도 function 이므로, 당연히 합성할 수 있습니다 (실제로 이미 본 적이 있습니다)
Monad laws 에서Kleisli composition이라는 것이 언급되었습니다:
-- | Left-to-right Kleisli composition of monads.
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(<=<) = flip (>=>)
<=<는.의 monadic 버전이며, 작용도 유사합니다:
> Just 7 >>= (return . (+1) <=< return . (/2) <=< return . (subtract 1))
Just 4.0
일련의Monad m => a -> m a함수를 합성하는 데 사용되며, 합성 순서도 오른쪽에서 왼쪽입니다
아직 댓글이 없습니다