畳み込みと展開
畳み込み(fold)
と
展開(unfold)
リストに対する再帰関数から再帰的な様式を抽出する
foldrとunfoldrは双対
fold/unfoldの練習
畳み込み
畳み込み(fold)
データ構造を消費する
展開
展開(unfold)
データ構造を生産する
再帰関数の制限の緩さ
再帰
畳み込み
mapやfilter
上の方が制限が緩い。つまり抽象度が高く、できることが多い
なので、できるだけ制限の強い、下の方のものを使って実装することで簡潔でわかりやすくなる
大抵の
Sort
は再帰で書ける
Sorting Morphisms
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3315
Generic fold
参考
/mrsekut-book-4274068056/060 (第3章 おりがみプログラミング)
右も左も分かる再帰 - あどけない話
末尾再帰
との関係