Accompanying material for the paper "Generalizing Generalized Tries" by Ralf Hinze, in Journal of Functional Programming, 10(4), pp. 327-351, July 2000. Perfectly balanced, binary leaf trees. > module Perfect ( > Perfect(Null, Succ), > perfect, > ) where > import Fork > data Perfect a = Null a | Succ (Perfect (Fork a)) > deriving (Show) Constructing a perfect tree (the length of the list must be a perfect power of 2). > perfect :: [a] -> Perfect a > perfect as > | single as = Null (unwrap as) > | otherwise = Succ (perfect (forks as)) > forks :: [a] -> [Fork a] > forks [] = [] > forks (a : b : x) = Fork a b : forks x > single :: [a] -> Bool > single [_] = True > single _ = False > unwrap :: [a] -> a > unwrap [a] = a