stimulant and competitive programming (original) (raw)
Foldableとは？
foldrやfoldlができる型クラス。
class Foldable (t :: Type -> Type) where
というように宣言されている。
https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-Foldable.html
ちなみに t :: Type -> Type というのは単に型t aと書けるようなtということを明示しているだけらしい。昔はclass Monad m whereと書いてメソッドでm aと書いていたが、確かにこれだとダックタイピング的な気がする。
Foldable の実装
foldMapかfoldrのどっちかのメソッドを定義するだけでいい。それらを実装できるということが具体的にどんな条件なのかはfoldMapで考えればわかりやすい。
foldMap :: Monoid m => (a -> m) -> t a -> m foldMap f t = ...
という定義から分かるように、コンテナtにfoldMapを実装するためには、t aからaをモノイドへの変換関数fに渡せて、その戻り値を（複数ある場合は）<>で右結合的に合成できる必要がある（foldMapは右結合）。ここで、aをモノイドへの変換関数に渡せるなら普通は（aを受け取れる）任意の関数にも渡せるだろうし、その結果を<>で合成できるなら任意の二項演算子でも合成できるはずなので、foldMapを実装するのは以下のfoldMapByを実装するのと同じと言える。
foldMapBy :: (a -> b) -> (b -> b -> b) -> t a foldMapBy f op t = ...
これを使ってfoldMapは次のように書ける。
foldMap f t = foldMapBy f (<>) t
ちなみにt aからaを関数に渡せさえすればいいというのはファンクターと似ているが、関数の結果をtに入れ直さなくてもいい。コンテナをリストで考えれば、aは複数個あるのでそれぞれに関数を適用したあと情報を失わず保存するには再びそれらをリストに入れればいい。したがってリストからaを取り出す操作はファンクターが相応しいわけだが、もし関数適用した後でaをすぐにまとめ上げてしまうならそれはそれで情報は保たれる。この自然（？）な構造がFoldableということなのだろう。
ところで要素の順序が上手く定まらないコンテナでは右結合とは？という話になるように思うが、Foldableは順序について特に口出ししていないようなので、とにかくfoldMapを定義で来たなら、そこで<>の評価されていく順序が要素の右から左に並べた順序ということなんだろうと思う。foldrを実装した場合も同じことで、foldl等のデフォルト実装は単にfoldMap(foldr)の逆向き操作として定義されているので、そうやって勝手に順序を定義しても矛盾はないと思う。
foldMap と foldr
foldrのデフォルト実装は
foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo #. f) t) z
となっている。
EndoというのはEndo型のデータコンストラクタで、Endo型というのはa -> aな関数を関数合成.を二項演算子としてモノイドにするためラッパー。#.は.と同じもの。なぜこんな定義なのかというと、例えば、foldr f 0 [1,2,3] == f 1 (f 2 (f 3 0)だが、これは*1 0と同じなので、<>として関数合成が使えればfoldMapでfoldr`が実装できる。
ちなみに、逆にfoldrを使ったfoldMapのデフォルト実装は
foldMap f = foldr (mappend . f) mempty
と直感的なものになっている。
二つのデフォルト実装の感覚的な違いは、二つの関数を素朴に実装できる条件に由来しているように思う。
foldrを素朴に実装する場合、foldrに与える二項演算子fの中で要素とそれまでの（fによる）畳み込みの結果を同時に受け取れる必要がある。これは例えば、合成と関数適用が別々のインターフェイスで、かつ関数適用がmap的な方法でしか行えないコンテナなら難しい。一方でfoldMapはそのコンテナで素朴に実装できるし、foldrを素朴に実装するための要素とそれまでの（fによる）畳み込みの結果を同時に受け取れるインターフェイスを使っても素朴に実装できる。
もちろん今言ったようなコンテナでも、関数適用用のインターフェイスで部分適用をして、合成用インターフェイスで関数合成すれば、foldrは実装できる。したがって両者は同値なのだが、それはラムダ計算とHaskellが同値というような意味だろうと思う。
Endo の stimes
Endoのソースを見ていると、Endoのstimesが特殊化されていた。stimesというのはstimes n xという関数で、Semigroupであるxをn個<>で合成させるSemigroupのメソッド。デフォルト実装は単純に考えるなら<>を再帰で繋げるものだが、その場合、EndoのstimesはEndoの中身である関数fをf . f . f ... という風に関数合成するのとほぼ同じことになる。しかし実際にはfを呼びながらn回回る再帰関数を作ってそれを返すというようなコードになってて、いわば一種のインライン展開みたいな最適化をしている。しかも、再帰関数を返すだけなのでstimes自体の計算量はO(1)になる。
この特殊化はこのissueが元になっていて、そのissueは「stimesが作るツリーはEndoにとっては最適とは言えない」というような発言から始まっている。最初は何のことかと思ったが、実はstimesのデフォルト実装はバイナリ法的に実装されている。ここでいうバイナリ法というのは累乗modを高速に計算するテクニックで、要は a^8 を計算するのに a^2 = a * a ->a4 = a2 * a2 -> a8 = a4 * a4というような高速化だ（ちょっと工夫すれば2冪じゃなくても使える）。この高速化は任意の半群上の累乗（演算子を乗法とみなした時の累乗）でも使えるので、stimesも使っているというわけだ。これによってn個の合成をO(logN)で行えるわけだが、この高速化をEndoに使っても、Endoの中身の関数は結局n`回呼ぶ必要があるので、合成がO(1)で終わる上の特殊化の方がいい。
ちなみにstimesのデフォルト実装の威力を試したコード。
import Data.Semigroup data PM = PM Integer Integer deriving Show
instance Semigroup PM where
(PM m x) <> (PM _ y) = PM m ((x * y) mod m)
powmod x n m = let (PM _ y) = stimes n $ PM m x in y main = do print $ powmod 123 12345678910 1234567
foldrM
foldrMはControl.MonadにあるfoldMの右結合版だが、
import Data.Foldable import Control.Monad.Identity
main = do print $ take 10 $ runIdentity $ foldrM (\x xs -> Identity (x : xs)) [] [1..]
としても終了しない。Identityモナドを使うなら単にfoldrを使うのと変わらないのだが、foldrMはfoldlを使って書かれているので無限リストを評価してしまうからだ。実際に以下のようにfoldrで実装すると終了する。
import Control.Monad.Identity
foldrM f a [] = return a foldrM f a (x:xs) = foldrM f a xs >>= f x
main = do print $ take 10 $ runIdentity $ foldrM (\x xs -> Identity (x : xs)) [] [1..]
foldrMがfoldを使う理由は foldr/build が関係しているらしいが、インライン展開云々という難しい話になるので理解できなかった。
*1:f 1) . (f 2) . (f 3