>>803
> {-# LANGUAGE GADTs #-}

この手の型を表現するためのよくあるトリック。名前は知らない

> data TrimmedRose a = ZeroTR a | SuccTR (TrimmedRose [a])

> flattenTR :: TrimmedRose a -> [a]
> flattenTR (ZeroTR x) = [x]
> flattenTR (SuccTR ts) = concat (flattenTR ts)

> testTR = do
>   print $ flattenTR $ SuccTR $ SuccTR $ ZeroTR [[1, 2], [3, 4, 5]] -- => [1,2,3,4,5]
>   print $ flattenTR $ SuccTR $ SuccTR $ SuccTR $ ZeroTR [[[1, 2], []], [[3, 4], [5], [6, 7]]] -- => [1,2,3,4,5,6,7]

GADT拡張があれば依存型もどきが使えるから、それを使う方法もある

> data Zero = Zero
> data Succ n = Succ

> data RoseN a n where
>   Leaf :: a -> RoseN a Zero
>   Branch :: [RoseN a n] -> RoseN a (Succ n)

> flattenRN :: RoseN a n -> [a]
> flattenRN (Leaf x) = [x]
> flattenRN (Branch ts) = concat $ map flattenRN ts

> testRN = do
>   print $ flattenRN $ Branch [Branch [Leaf 1, Leaf 2], Branch [Leaf 3, Leaf 4, Leaf 5]] -- => [1,2,3,4,5]
>   --print $ flattenRN $ Branch [Leaf 1, Branch [Leaf 2, Leaf 3]] -- error