たのしい Foldable

Foldable がよくわからない人のための3分くっきんぐです！

Foldable って何？

どんなに複雑なデータ構造でも、一列のフラットなデータ構造と同一視できるという性質のことです。

例えば、

data Tree a = Leaf a | Node (Tree a) (Tree a)

      Node
      /  \
  Node    Node
  /  \    /  \
 a    b  c    d

これを、

  Node
  /  \
 a   Node
     /  \
    b   Node
        /  \
       c   Node
           /  \
          d   (EMPTY)

これと同じものとみなしても良いという性質が Foldable。

ちなみに List は何もしなくてもこの形なので、一番分かりやすい Foldable の例です。

foldr って何？

フラットにしたデータ構造の節と末端を好きなものに置き換えるだけの関数です。

data List a = Nil | Cons a (List a)
(:) = Cons

1 : 2 : 3 : Nil
  Cons
  /  \
 1   Cons
     /  \
    2   Cons
        /  \
       3    Nil

foldr :: forall f a b. Foldable f => (a -> b -> b) -> b -> f a -> b
foldr f init = ?データ構造ごとに定義されています

foldr (+) 999

   (+)
  /   \
 1    (+)
     /   \
    2    (+)
        /   \
       3     999

(1 : (2 : (3 : Nil))) ==> (1 + (2 + (3 + 999)))
==> 1005


foldr (-) 456

   (-)
  /   \
 1    (-)
     /   \
    2    (-)
        /   \
       3     456

(1 : (2 : (3 : Nil))) ==> (1 - (2 - (3 - 456)))
==> -454


foldr (append <<< show) "END"

 (append <<< show)
  /     \
 1    (append <<< show)
       /     \
      2    (append <<< show)
            /     \
           3      "END"

(1 : (2 : (3 : Nil))) ==> (show 1 <> (show 2 <> (show 3 <> "END")))
==> "123END"

foldl は？

foldr で節を「右向きの関数合成」に置き換えたときに得られるものです。
実質的には、「逆向きにフラットにしたデータ構造」の節と末端を好きなものに置き換えるだけの関数と考えられます。

a : b : c : Nil
  Cons
  /  \
 a   Cons
     /  \
    b   Cons
        /  \
       c    Nil


foldl :: forall f a b. Foldable f => (b -> a -> b) -> b -> f a -> b
foldl f = flip $ foldr (\left right -> flip f left >>> right) identity

  (flip f _ >>> _)
  /     \
 a    (flip f _ >>> _)
      /     \
     b    (flip f _ >>> _)
          /     \
         c      identity

==> (flip f a >>> (flip f b >>> (flip f c >>> identity)))

==> \init -> init # flip f a # flip f b # flip f c # identity
==> \init -> (((init `f` a) `f` b) `f` c)

          `f`
         /   \
       `f`    c
      /   \
    `f`    b
   /   \
 init   a


foldl (+) 999

          (+)
         /   \
       (+)    3
      /   \
    (+)    2
   /   \
 999    1

(1 : (2 : (3 : Nil))) ==> (((999 + 1) + 2) + 3)
==> 1005


foldl (-) 456

          (-)
         /   \
       (-)    3
      /   \
    (-)    2
   /   \
 456    1

(1 : (2 : (3 : Nil))) ==> (((456 - 1) - 2) - 3)
==> 450

この絵を見れば、foldr と foldl で節を構成する関数の引数順序が入れ替わっている理由も自然に分かりますね？

おわり

• Foldable なら、データ構造をフラットなものとみなすことができる。
• foldr は、フラットなデータ構造の節と末端を好きなものに置き換える関数。
• foldl は foldr の逆向きだけど、foldr で節を関数合成に置き換えたものとも言える。

どのように再帰してるかとか、右から計算とか左から計算とか、そういうむずかしい感じに考えなくても大丈夫。
要は単なるデータ構造の式変換でしかないわけです。かんたんかんたん。