public
Last active

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

  • Download Gist
RandomAccessParser.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.