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

foldlをfoldrで実装する

More than 3 years have passed since last update.

foldlをfoldrで実装する

はじめに

@ruiccさんのスペースリーク、その傾向と対策のコメント欄において、@maoeさんが「最近のbaseではfoldlの実装にfoldrを使っている」という内容のコメントをされていました。
そのリンク先では、次のような形でfoldlを定義しています。

foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
foldl k z0 xs = foldr (\(v::a) (fn::b->b) (z::b) -> fn (k z v)) (id :: b -> b) xs z0

(;・∀・)
(;・∀・)
(;・∀・)
(;・∀・)
(´・ω・`)

なにを言っているのかわけがわからないですね!
ということで、スペースリーク自体とは多少離れてしまうかもしれませんが、この記事ではなぜこれがfoldlになるのかを少しずつ解き明かしていきます。
きっと、foldrによる定義をすると、どのように最適化されてどのようにスペースリークが抑制されるかなどは、誰かが教えてくれると思います。

読み解いてみる

実はfoldlfoldrで実装する方法については、Real World Haskellでも少し触れていますが、なぜそのように書けるのか詳細については触れていません。
Real World Haskellでは、次のような定義になっています。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr step id xs z     -- (1)
    where step x g a = g (f a x)

前述の式のラムダ式の部分に名前をつけてwhere節に分けただけなので、本質的には変わりありませんね?

ここで、本来 foldr :: (a -> b -> b) -> b -> [a] -> b で、引数を2つしかとらないfoldrに3つの引数を与えているように見えて紛らわしいので、このように書き換えましょう。

foldl f z xs = (foldr step id xs) z   -- (2)
    where step x g a = g (f a x)

(foldr step id xs) の中のfoldr

foldr :: (b -> (a -> a) -> (a -> a)) -- step 関数
       -> (a -> a)                   -- id 関数
       -> [b]                        -- xs
       -> (a -> a)                   -- z を変換する関数

というように、関数を評価結果として返しています。
さらに、(2)の式のff :: a -> b -> a で2引数をとる関数なので、わかりやすさのために中置演算子で置き換えましょう。
つまり、f a b == a ?? b となる中置演算子??を使って

foldl (??) z xs = (foldr step id xs) z   -- (3)
    where step x g a = g (a ?? x)

と書き換えました。
同じくfoldrの引数のstepstep a b == a ?! b となる中置演算子?!を使うと...

foldl (??) z xs = (foldr (?!) id xs) z   -- (4)
    where (?!) x g a = g (a ?? x)

ここで、?!演算子を次のように変換します。

(?!) x g a
=> g (a ?? x)      -- (?!)の定義
=> g ((?? x) a)
=> g . (?? x) $ a  -- 関数合成の性質

つまり、(?!) x g = g . (?? x) です。
その結果、次のように書き換えられます。

foldl (??) z xs = (foldr (?!) id xs) z   -- (5)
    where x ?! g = g . (?? x)

では、式(5)の左辺がfoldlになることを確かめましょう。
カッコが多くて途中で??って気持ちになりそうですが、がんばって式変形を追うと最後に感動が待っています。

(foldr (?!) id xs) z
=> ((xs!!0) ?! ((xs!!1) ?! ( ... ((xs!!(n-1)) ?! ((xs!!n) ?! id)) ...))) z        -- foldrの展開
     where n = length(xs)
=> ((xs!!0) ?! ((xs!!1) ?! ( ... ((xs!!(n-1)) ?! (id . (?? (xs!!n)))) ...))) z    -- (?!)の定義
=> ((xs!!0) ?! ((xs!!1) ?! ( ... (id . (?? (xs!!n)) . (?? (xs!!(n-1)))) ...))) z  -- (?!)の定義
=> (id . (?? (xs!!n)) . (?? (xs!!(n-1))) . ... . (?? (xs!!1)) . (?? (xs!!0)))) z  -- (?!)の定義
=> ((?? (xs!!n)) . (?? (xs!!(n-1))) . ... . (?? (xs!!1)) . (?? (xs!!0))) z        -- idの定義
=> (?? (xs!!n)) . (?? (xs!!(n-1))) . ... . (?? (xs!!1)) $ (?? (xs!!0)) z          -- 関数合成の性質
=> (?? (xs!!n)) $ (?? (xs!!(n-1))) $ ... $ (?? (xs!!1)) $ (?? (xs!!0)) z          -- 関数合成の性質

いつの間にか、xsの要素の並びが逆順に変わっています。
それに気づいたあなたの気持ちは?!って感じでしょう。ほら、そういう意図でこんな中置演算子にしたのです(・∀・)
嘘です。こじつけです。

さて、最後の行の処理を読みとくと...

  • 初期値zに対してxsの最初の要素を(??)で適用して
  • その結果に対してxsの次の要素を(??)で適用して
  • その結果に対してxsの次の要素を(??)で適用して
  • ...

これはまさにfoldlの挙動ですね!

いつの間にリスト要素の順番が逆転したのでしょうか?

x ?! g = g . (?? x)

という?!の定義で、g (ここにfoldrによって右から「蓄積」されてきた関数が入る)の適用される順番が後(左)に移されています。
このトリックによって、気づいたらリストの各要素の並びが反転してしまうのです!
このトリック、なんだか差分リストを想起させますね。

あらためて定義を見てみよう!

ということで、このようなfoldrの使い方のメンタルモデル(@ruiccさんがこのアドベントカレンダーの最初の記事で意図した「メンタルモデル」という言葉の使い方ではないかもしれないですが...)ができたあとに改めて(5)の定義式をながめてみましょう。

foldl (??) z xs = (foldr (?!) id xs) z   -- (5)
    where x ?! g = g . (?? x)
  • foldrzを変換するための関数を作っている
  • idを初期値にして、xsのリストを使ってすこしずつ関数を「育てて」いる
  • いままで育てられた関数が、(?? x) のあとに評価されるように合成している

ということが見えるようになり、「なんとなくfoldlになっているっぽい」と思えるようになったのではないでしょうか?

はすけるたのしい。

Why do not you register as a user and use Qiita more conveniently?
  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
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