Don't know where to start with mutable Vectors

Question

I am trying to do something like this in Haskell using the Data.Vector.* packages, and I really have no idea where to start. I'm a newb to Haskell, with a tenuous grasp of certain core concepts (but I'm getting there).

What I'm trying to do can be expressed approximately by the following C code:

float *arrA = /* initialized to array of length n */;
float *arrB = /* initialized to array of length n */;
for (i = 1; i < n; i++) {
  for (j = 0; j < n - i; j++) {
    arrB[j] = someFn(i, j, arrA[j], arrB[j+1])
  }
  float *p = arrA;
  arrA = arrB;
  arrB = p;
}
return arrA[0];

Points to note:

• Reuse of arrays for performance reasons, but I need two of them to avoid trampling required values for the next iteration
• Arrays are swapped
• Upper bound of inner loop changes with each iteration of outer loop

Any help that you might offer would be greatly appreciated.

Answer 1

This is a Foolish Task

It's rather silly to perform direct translation of C to Haskell. I've done it for pay before and it doesn't go smoothly or quickly. It is much better to describe the task and implement it in an idiomatic style in the target language. You would be more likely to get quality answers by providing an English description of the algorithm.

Please Post Compilable Code

When you post questions, please be sure it compiles!

Learn Haskell not How to write C in Haskell

How things are done in different languages can vary drastically, especially when you cross a divide such as from imperative to functional, or mutable to immutable, or strict to lazy, or implicit casting to explicit, or manually managed memory to garbage collected. You are crossing all these divides.

If your task is to learn Haskell, you are starting at the wrong point. If your task is to learn mutable vectors/arrays in Haskell then you need to know more of the fundamentals to appreciate the nuances. If your task is to taunt Haskell for having poor support of arrays then you would have had a really easy time of it before Roman came along and made the Vector package - this is my way of saying: don't look at Haskell Arrays only look at Vectors.

OK OK, What's the Solution?

We'll use the Vector package for our Arrays and the ST monad for mutable operations (your first bullet point):

import qualified Data.Vector.Unboxed.Mutable as M
import qualified Data.Vector.Unboxed as V
import Control.Monad.ST
import Control.Monad

Your main function takes two vectors and returns a float. We start by obtaining mutable references to the arrays using thaw and use a simple fold to allow us to flip our array references.

someFunc :: V.Vector Float -> V.Vector Float -> Float
someFunc arrA arrB = runST $ do
        -- Obtain mutable copies of the arrays
        mA <- V.thaw arrA 
        mB <- V.thaw arrB
        (mA', mB') <- foldM op (mA, mB) [1..n-1] -- for(i = 1 ; i < n; i++)
        M.read mA' 0
 where
 n = min (V.length arrA) (V.length arrB)

The inner for loop is contained in op. It just performs some simple reads from the arrays and writes a new value. It has to return the two arrays in a tuple; the tuple is flipped on every iteration to obtain the same semantics of your mutable pointers (your second point):

 op (mA, mB) i = do
        forM_ [0..n-i-1] $ \j -> do
                v1 <- M.read mA j
                v2 <- M.read mB (j+1)
                M.write mB j (someFn i j v1 v2)
        return (mB, mA)

Consistent with your third point, the inner loop bound changes based on the outter loop.

Just so we can compile a runable program we'll include main:

someFn i j f1 f2 = f1 + fromIntegral i + fromIntegral j - f2

main = print $ someFunc (V.fromList [1..10]) (V.fromList [0..9])

This is for educational purposes only. I haven't tested this, it should be morally the same as your C but might be off by one in a loop or have other trivial differences.