nattybear/foldable.md

## foldable.md

      
    Raw
  

              foldable.md
            
          
    이 글은 Typeclassopedia를 읽고 정리한 것이다. 타입 클래스 백과
Foldable

타입 클래스 Foldable은 모듈 Data.Foldable에 정의되어 있다. 어떤 상자 같은 것에 담겨 있는 것들을 합쳐서 하나의 값으로 만들 수 있는 것을 말한다. container
예를 들어서 아래와 같이 리스트라는 상자에는 여러 값을 담을 수 있는데 sum이라는 함수를 이용하면 안에 있는 것들을 합쳐서 하나의 값으로 만들 수 있다.
ghci> sum [1, 2, 3]
6
이때 나는 '합치다'라는 표현을 썼지만 하스켈에서는 '접는다'라고 표현한다. foldable
Foldable에는 꽤 많은 함수들이 있는데 아래 두개중에 하나만 구현하면 된다. 나머지는 공짜
class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr   :: (a -> b -> b) -> b -> t a -> b
foldMap

함수 foldMap의 타입은 아래와 같다.
foldMap :: Monoid m => (a -> m) -> t a -> m

먼저 상자 안에 담겨있는 a를 모노이드 m으로 바꿔주는 함수를 인자로 넣고 (a -> m)
상자를 두번째 인자로 넣어주면 t a
하나로 합친 결과가 나온다. m

함수 fmap 같은 것으로 상자 안에 있는 모든 원소를 모노이드로 바꾸고 mappend로 모두 합칠 것 같다. 아래 연습 문제를 풀다가 깨달았는데 foldMap에는 Functor 제약이 없다.
타입 리스트의 Foldable 인스턴스는 아래와 같다.
instance Foldable [] where
  foldMap :: Monoid m => (a -> m) -> [a] -> m
  foldMap g = mconcat . map g
타입 Tree의 정의와 Foldable 인스턴스는 아래와 같다.
data Tree a
  = Empty
  | Leaf a
  | Node (Tree a) a (Tree a)
  
instance Foldable Tree where
  foldMap :: Monoid m => (a -> m) -> Tree a -> m
  foldMap f Empty        = mempty
  foldMap f (Leaf x)     = f x
  foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
타입 Maybe와 Array도 Foldable 인스턴스가 있다.
containers라는 라이브러리에는 아래와 같은 타입들이 있는데

Map
Set
Tree
Sequence

대부분 Foldable 인스턴스가 구현되어 있다. 감사합니다 개발자느님
연습 문제


foldMap으로 fold를 구현해라.

fold :: (Monoid m, Foldable t) => t m -> m
fold = foldMap id

fold로 foldMap을 구현하려면 뭐가 필요할까?

Functor 제약? 잘 모르겠다 ㅎ 아래처럼 내 마음대로 원래 타입에는 없던 제약을 추가해도 되는 것일까?
foldMap :: (Monoid m, Foldable t, Functor t)
        => (a -> m) -> t a -> m
foldMap f xs = fold $ f <$> xs

foldr로 foldMap을 구현해라.

foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty

foldMap으로 foldr을 구현해라.(힌트 : Endo 모노이드를 사용해라) 뭔데 그게...

Endo a는 함수 a -> a에 대한 모노이드 wrapper라고 한다. 그러고 보니 함수는 항등원도 있고 더하기도 된다. 아래처럼 구현되어 있을 것 같다.
newtype Endo a = Endo {appEndo :: a -> a}

instance Semigroup (Endo a) where
  Endo f <> Endo g = Endo (f . g)
  
instance Monoid (Endo a) where
  mempty = Endo id
실제로는 이렇게 구현되어 있다. 함수 <> 구현이 내가 쓴 것과 다른데 맞게 했는지 모르겠다.
foldr의 소스 코드도 실제로 foldMap과 Endo로 작성되어 있다. 봐도 모르겠다

foldMap . foldMap이나 foldMap . foldMap . foldMap의 타입이 뭐냐? 뭐하는데 쓰일까?

잘 모르겠으니 아래처럼 :t로 타입을 확인해보자.
GHCi> :t foldMap . foldMap
foldMap . foldMap
  :: (Foldable t, Foldable t1, Monoid m) => (a -> m) -> t1 (t a) -> m
어라? 왜인지 join이 떠오른다.
join :: Monad m => m (m a) -> m a
3개짜리도 타입을 확인해보자.
GHCi> :t foldMap . foldMap . foldMap
foldMap . foldMap . foldMap
  :: (Foldable t, Foldable t1, Foldable t2, Monoid m) =>
     (a -> m) -> t2 (t1 (t a)) -> m
보아하니 여러 중첩된 상자들을 모두 합쳐서 하나의 값으로 접어주는 함수인 것 같다. 신기하다
대문 링크