LEB128 in Haskell

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.