Help us understand the problem. What is going on with this article?

たのしい 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 で節を関数合成に置き換えたものとも言える。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした