Brotli compression algorithm, translated from Python into Haskell
don't use lists

Almost any non-trivial operation on lists is O(n) or worse. Python is using mutable arrays. Haskell also mutable arrays, so why not use mutable arrays?

The only problem with Haskell's arrays is that there are so many choices to make:


pure vs. mutable
boxed vs. unboxed
array vs. vector
run in the ST monad or IO?


Here is the routine coded in Haskell which uses both pure and mutable unboxed vectors. It could be improved, but this is basically how you would go about it.

(code updated)

module Lib
where

import Control.Monad
import Control.Monad.Primitive
import Control.Monad.ST
import qualified Data.Vector.Unboxed.Mutable as UVM
import qualified Data.Vector.Unboxed as UV

calculate_codes :: PrimMonad m =&gt; UV.Vector Int -&gt; UV.Vector Int -&gt; m (UV.Vector Int)
calculate_codes tree codes = do
  next_codes &lt;- UV.thaw codes
  UV.generateM (UV.length tree) $ \i -&gt; do
    let x = tree UV.! i
    z &lt;- if x /= 0
           then do y &lt;- UVM.read next_codes x
                   UVM.write next_codes x (y+1)
                   return y
           else return 0
    return z

test = do
  let tree = UV.fromList [ 3, 3, 3, 3, 3, 2, 4, 4 ]
      codes = UV.fromList [ 0, 0, 0, 2, 14 ]
      next = runST $ calculate_codes tree codes
  print next

{-
tree      = [ 3, 3, 3, 3, 3, 2, 4, 4 ]
next_code = [0,0,0,2,14]

def calculate_codes( tree, codes ):
    tree_code = {}
    next_code = copy.copy( codes )
    for i in range(len(tree)):
        if tree[i] != 0:
            tree_code[i] = next_code[ tree[i] ]
            next_code[tree[i]] += 1             -- This "effectful" line is throwing me off.
    return tree_code

print calculate_codes( tree, next_code )
-}