2006-03-11 in haskell-cafe@haskell.org)
> class CollEq coll where
> collEqual :: Eq tag => coll (T tag coll) -> coll (T tag coll) -> Bool
> class CollShow coll where
> collShowsPrec :: Show tag => Int -> coll (T tag coll) -> ShowS
> instance (Eq tag, CollEq coll) => Eq (T tag coll) where
> Branch x0 == Branch x1 = collEqual x0 x1
> Tag tag0 x0 == Tag tag1 x1 = tag0 == tag1 && x0 == x1
> Loop i0 == Loop i1 = i0 == i1
> _ == _ = False
> instance (Show tag, CollShow coll) => Show (T tag coll) where
> showsPrec p branch = showParen (p>10)
> (case branch of
> Branch x -> showString "Branch " . collShowsPrec 11 x
> Tag i e -> showString "Tag " . showsPrec 11 i
> . showString " " . showsPrec 11 e
> Loop i -> showString "Loop " . showsPrec 11 i)
> unwind :: (Ord tag, Functor coll) => T tag coll -> T tag coll
> unwind =
> let aux tags branch =
> case branch of
> Branch x -> Branch (fmap (aux tags) x)
> Tag tag sub -> let e' = aux (Dict.insert tag e' tags) sub
> in e'
> Loop tag -> Dict.lookup tags tag
> in aux Dict.empty