Parsing a random-access format into a pure data structure. Parsing will be lazy: parts of the data structure will be parsed on demand.

RandomAccessParser.hs

import Data.Word
import qualified Data.ByteString as B
type ByteString = B.ByteString

data Tree = Leaf [Word8] | Branch Tree Tree deriving (Eq,Show)

parse :: ByteString -> Tree
parse xs = case view xs of
    Cons 0 xs -> case view xs of
        Cons length xs -> Leaf . B.unpack $ B.take (fromIntegral . toInteger $ length) xs
    Cons 1 xs -> case view xs of
        Cons length xs -> let (a,b) = B.splitAt (fromIntegral . toInteger $ length) xs in
            Branch (parse a) (parse b)

data View = Nil | Cons Word8 ByteString

view :: ByteString -> View
view xs
    | B.null xs = Nil
    | otherwise = Cons (B.head xs) (B.tail xs)
    

serialize :: Tree -> ByteString
serialize (Branch x y) =
    1 `B.cons` (length `B.cons` (sx `B.append` serialize y))
    where
    sx = serialize x
    length = fromIntegral . toInteger $ B.length sx
serialize (Leaf ws) =
    0 `B.cons` (length `B.cons` w)
    where
    w = B.pack ws
    length = fromIntegral . toInteger $ B.length w

exampleTree = Branch (Leaf [1,2,3]) (Branch (Leaf []) (Leaf [4,5]))

-- try
-- > parse $ serialize exampleTree