efficiency of mfix

[Levent Erkok]

On Friday 27 September 2002 05:19 pm, Hal Daume III wrote:
> There is a one pass solution using mfix.  This looks like:
>
>   mfix (\ ~s -> ioaA a 1 s)
>
> where  ioaA is defined as:
>
>   ioaA a i s
>
>     | i > sz = return 0
>     | otherwise =
>
>         do s' <- ioaA a (i+1) s
>            v  <- readArray a i
>            writeArray a i (v/s)
>            return (s' + v)
>     where (_,sz) = Data.Array.IO.bounds a
>
> Using unboxed arrays is not possible in the fixed point version
> (loop).  On the normal version, it just about triples the speed across the
> board.

Hi,

I'm not sure if it's mfix we should blame here. Can you please 
experiment with the following version of normalize and report on 
running times?

  norm a = mdo s <- ioaA 1 s id
               return ()
    where (_, sz) = bounds a
          ioaA i s acc
           | i > sz = return (acc 0)
           | True   =
               do v <- readArray a i
                  writeArray a i (v/s)
                  ioaA (i+1) s (\x -> v + acc x)

It'd be interesting to see the results especially for very large 
inputs (i.e. >= half a million elements.)

-Levent.