結合リスト
data Tree a = Single a | App (Tree a) (Tree a)

を普通のリストに変換する関数

toList :: Tree a -> [a]
toList (Single a) = [a]
toList (App (Single a) xs) = a:toList xs
toList (App (App xs ys) zs) = toList $ App xs $ App ys zs

この関数の2つ目の式では呼び出しの度に要素数が減ってるけど
でも3つ目の式では要素数が減ってない
でも有限リスト与えた時にちゃんと止まる
じゃあ3つ目の式と2つ目の式でに共通の呼び出し毎に減っているものは何ですか？
整礎帰納法の例で探してもマージソートとか割り算ばっかりで木の平坦化とか全然出てきません