4
\$\begingroup\$

I have implemented the LEB128 encoding for unsigned integers. I'm fairly new to Haskell so I have some doubt about the coding style I'm using, particularly the definition of byte and then 2 lines later byte':

import Data.Bits
import Data.Word

uleb128 :: Integer -> [Word8]
uleb128 0 = []
uleb128 n =
  let byte = (fromIntegral n :: Word8) .&. 0x7F
      n' = shiftR n 7
      byte' = if n' == 0
              then byte
              else (byte .|. 0x80)
  in
    byte' : uleb128 n'

Futhermore I have doubts about the choice of let .. in in favor of ... where and the use of if then else vs case of. I'm very much still learning Haskell so I'm curious how a seasoned Haskell programmer would have written the above function.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Nice first question! \$\endgroup\$ – syb0rg May 19 '16 at 20:56
1
\$\begingroup\$

Your uleb128 doesn't follow the LEB128 format, since 0 isn't encoded as a single byte:

uleb128 0 `shouldBe` [0x00]

With this in mind, we have to rewrite uleb128:

uleb128 :: Integer -> [Word8]
uleb128 n
  | n' == 0   = [byte]
  | otherwise = (byte .|. 0x80) : uleb128 n'
  where
    byte = fromIntegral (n .&. 0x7F)
    n'   = n `shiftR` 7

Or, to write it with let…in… and if:

uleb128 n = 
  let byte = fromIntegral (n .&. 0x7F)
      n'   = n `shiftR` 7
  in 
    if n' == 0
      then [byte]
      else (byte .|. 0x80) : uleb128 n'

It's a personal preference whether you use where or let. I usually prefer where, since it works great with guards.

Note that neither of these versions check whether n is actually non-negative. Unfortunately, there is no Natural type in base. Depending on your use case, you can use ErrorType [Word8] or error, although the first is usually preferred (with ErrorType = Maybe or ErrorType = Either String).

An alternative that doesn't exploit the bits behind the number can be achieved with quotRem, where case is rather handy:

uleb128' :: Integer -> [Word8]
uleb128' n = case n `quotRem` 128 of
  (0, r) -> [fromIntegral r]
  (q, r) -> (fromIntegral r + 128) : uleb128' q

We can use QuickCheck to verify that both work the same:

ghci> let largeInt = choose (10^4, 10^10) -- to generate large Integers
ghci> quickCheck $ forAll largeInt $ \x -> uleb128 x == uleb128' x
+++ OK, passed 100 tests.

Another way would be to use unfoldr from Data.List, but that wouldn't be as clear.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for your detailed answer. And thanks for pointing out that my function didn't even works as intended! \$\endgroup\$ – lucasj May 22 '16 at 19:31
  • 1
    \$\begingroup\$ @LucasJ: If possible, write a test. For example, you want the inverse (uleb128Inverse :: [Word8] -> Integer) to form an isomorphism for valid [Word8]s (x >= 0 ==> uleb128inverse (uleb128 x) == x). \$\endgroup\$ – Zeta May 22 '16 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.