The design of array libraries

[jaror]

@oisdk

@jaror

cache :: KnownNat n => V n x -> V n x
cache @n (V f) = 
  let 
    n = fromIntegral (natVal (Proxy @n)) :: Int
    arr = createArray n undefined $ \m -> do
      let go i
            | i < n = writeArray m i (f i) *> go (i + 1)
            | otherwise = pure ()
      go 0
  in V (indexArray arr)

Data.Array is lazy, so you can just write the memoized version directly:

cache :: KnownNat n => V n x -> V n x
cache @n (V f) = 
  let 
    n = fromIntegral (natVal (Proxy @n)) :: Int
    arr = array (0,n-1) [ (i, f i) | i <- [0..n-1] ]
  in V (arr !)

I don’t trust Data.Array to be efficient. Is it really going to fuse that list away? It seems so from looking at the core, but the core is much longer (104 vs 40 lines). I do wish that someone would write a small wrapper library around Data.Primitive.Array with a few more convenience functions.

[dbarton]

I like the contiguous package for primitive (and other) arrays. What do you think?

[jaror]

I don’t think type classes should be used like they are in contiguous. You’re really relying on GHC inlining absolutely everything if you go with that approach. I also think it is just unnecessary. Why not just provide several array implementations in a few different modules? It’s not that bad to qualify some function names.

[dbarton]

Thanks for the response, I really appreciate feedback from experts.

In my sparse vector module I have trees of arrays of size up to 64 (together with a Word64 of bits at each level to say what’s present). The interior arrays are all SmallArrays but the bottom ones could also be other arrays, e.g. ByteArrays filled with integers mod p for e.g. word-sized p (getting this efficient is important for computer algebra). Anyway it’s convenient to code a lot of routines that work at all levels of the tree and all array types the same way using the type classes in contiguous.

[dbarton]

P.S. With all type classes, even Num for basic number types, aren’t you counting on inlining for efficiency?