Decode.hs

data Value = Num Integer | Nil | Cons Value Value
  deriving Show

negateVal (Num x) = Num (-x)
negateVal other = other

decodeUnary ('0' : s) = (0, s)
decodeUnary ('1' : s) =
  let (n, s') = decodeUnary s in
    (n + 1, s')

decodeIntBits acc 0 s = (acc, s)
decodeIntBits acc n ('0' : s) = decodeIntBits (2 * acc) (n - 1) s
decodeIntBits acc n ('1' : s) = decodeIntBits (2 * acc + 1) (n - 1) s

decodeInt :: String -> (Integer, String)
decodeInt s =
  let (len, s') = decodeUnary s in
    decodeIntBits 0 (4 * len) s'

decode ('0' : '0' : tail) = (Nil, tail)
decode ('0' : '1' : tail) =
  let (v, xs) = decodeInt tail in (Num v, xs)
decode ('1' : '0' : tail) =
  let (v, xs) = decodeInt tail in (Num (-v), xs)
decode ('1' : '1' : tail) =
  let (x, tail') = decode tail in
    let (y, tail'') = decode tail' in
      (Cons x y, tail'')

main = do
  line <- getLine
  putStrLn $ show $ decode line