Motivation (II)

Lösung etwa so:

relabel t xs = case t of
  Leaf -> ( Leaf, xs )
  Branch {} ->
    let (l, ys) = relabel (left t) xs
        (k, zs) = ( head ys, tail ys)
        (r, ws) = relabel (right t) zs
    in  (Branch {left=l,key=k,right=r} , ws)

Die Teilrechnungen als Aktionen auffassen, die jeweils ein Resultat liefern l,k,r und einen Zustand ändern xs -> ys -> zs -> ws.

Verkettung der Zustände durch >>= einer geeigneten Monade.