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