This is the code from the paper "Generalizing Generalized Tries" by Ralf Hinze, in Journal of Functional Programming,10(4), pp. 327-351, July 2000. > import Bintree > import Fork > import Perfect > import Sequ %-------------------------------= -------------------------------------------- 2.3. Specializing polytypic definitions %-------------------------------= -------------------------------------------- Bits. > data Bit = O | I > instance Show Bit where > showsPrec _ O = showChar '0' > showsPrec _ I = showChar '1' > > showList [] = id > showList (b : bs) = shows b . showList bs Encoding the empty tuple, bits, characters, and integers. > encodeUnit :: () -> [Bit] > encodeUnit () = [] > encodeBit :: Bit -> [Bit] > encodeBit b = [b] > encodeChar :: Char -> [Bit] > encodeChar c = bits 8 (fromEnum c) > encodeInt :: Int -> [Bit] > encodeInt n = bits 16 n Encoding lists. > encodeL :: (a -> [Bit]) -> ([a] -> [Bit]) > encodeL enca [] = [O] > encodeL enca (x : xs) = I : enca x ++ encodeL enca xs > encodeStr :: String -> [Bit] > encodeStr = encodeL encodeChar Try `encodeL encodeChar "hello world"', or `encodeL encodeUnit (replicate 11 ())', or `encodeL encodeBit \$ encodeL encodeChar "hello world"', or `encodeL encodeBit \$ encodeL encodeUnit (replicate 11 ())'. Encoding external binary search trees. > encodeB :: (a1 -> [Bit]) -> (a2 -> [Bit]) > -> (Bintree a1 a2 -> [Bit]) > encodeB enca1 enca2 (Leaf x) = O : enca1 x > encodeB enca1 enca2 (Node l x r) > = I : encodeB enca1 enca2 l > ++ enca2 x > ++ encodeB enca1 enca2 r Try `encodeB encodeStr encodeChar (Leaf "a")' or `encodeB encodeStr encodeChar (Node (Leaf "a") '+' (Leaf "b"))'. Encoding internal nodes. > encodeF :: (a -> [Bit]) -> (Fork a -> [Bit]) > encodeF enca (Fork x1 x2) = enca x1 ++ enca x2 Encoding perfectly balanced, binary leaf trees. > encodeP :: (a -> [Bit]) -> (Perfect a -> [Bit]) > encodeP enca (Null x) = O : enca x > encodeP enca (Succ x) = I : encodeP (encodeF enca) x > encodePI :: Perfect Int -> [Bit] > encodePI x = encodeP encodeInt x Try `encodePI (perfect [0 .. 7])', or `encodeP encodeUnit (perfect (replicate 8 ()))', or `encodeP encodeChar (perfect "good bye")'. Encoding binary random-access lists. > encodeS :: (a -> [Bit]) -> (Sequ a -> [Bit]) > encodeS enca Empty = [O] > encodeS enca (Zero xs) = I : O : encodeS (encodeF enca) xs > encodeS enca (One x xs) = I : I : enca x ++ encodeS (encodeF enca) xs Try `encodeS encodeChar (sequ "hello world")', or `encodeS encodeUnit (sequ (replicate 11 ()))', or `encodeS encodeUnit (sequ (replicate 1024 ()))', or `encodeS encodeUnit (sequ (replicate 2048 ()))'. Auxiliary function. > bits :: Int -> Int -> [Bit] > bits 0 n = [] > bits (k + 1) n > | r == 0 = O : bits k q > | otherwise = I : bits k q > where (q, r) = divMod n 2