Don't know where to start with mutable vectors

I am trying to do something like this in Haskell using the Data.Vector packages. * and I really don’t know where to start. I am new to Haskell, with a subtle understanding of some basic concepts (but I get there).

What I'm trying to do can be roughly expressed 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]; 

Note:

  • Reusing arrays for performance reasons, but I need two of them to avoid porting the necessary values ​​for the next iteration
  • Arrays swap
  • The upper bound of the inner loop changes with each iteration of the outer loop

Any help you could offer would be greatly appreciated.

+6
source share
1 answer

This is a dumb task.

It's pretty stupid to do a direct translation of C to Haskell. I have done this for payment before, and it does not go smoothly or quickly. It is much better to describe the task and implement it in an idiomatic style in the target language. You will most likely receive quality answers by providing an English description of the algorithm.

Please post compiled code

When you submit questions, make sure they compile!

Learn Haskell not How to Write C in Haskell

The way everything is done in different languages ​​can vary greatly, especially when you cross a section from imperative to functional, or changeable to immutable, or strict, so that lazy or implicit listing in explicit or manually managed memory for garbage collection, you cross all these divisions.

If your task is to learn Haskell, you start from the wrong point. If your task is to study mutable vectors / arrays in Haskell, then you need to learn more about the basics to appreciate the nuances. If your task is to mock Haskell for having poor array support, you would have a very simple time before Roman comes and does the Vector package - this is my way of saying: don't look at Haskell Array Look at Vector s only.

OK, what is the solution?

We will use the Vector package for our arrays and the ST monad for mutable operations (your first marker 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 getting mutable array references using thaw and use a simple fold so we can 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 does some simple reads from arrays and writes a new value. It should return two arrays to the tuple; the tuple is flipped at each iteration to get the same semantics of your mutable pointers (second dot):

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

According to your third point, the binding of the inner loop changes depending on the exit loop.

Just to compile the executable program, we will include main:

 someFn ij 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 have not tested this, it should be morally the same as your C, but it may be disabled alone in the loop or have other trivial differences.

+19
source

Source: https://habr.com/ru/post/920459/


All Articles