CODEWITHSUNDEEP
haskellvector
devgeek
devgeek

Reputation: 360

How to map a function over a specific range of a Vector in Haskell

I have a very large Vector a and I want to map a function over a small range. For example, if I have a Vector of size 1000, I want to map function f over values at indices 100-200 and then return the entire updated Vector. What is the best way to do this. I'm open to other data structures, but I would prefer not to use mutable vectors.

Edit: Here's an equivalent in imperative code.

for (int i = startIdx; i < endIdx ; i++){
bigVector[i] = myFunction(bigVector[i]);
}

Upvotes: 2

Views: 681

Answers (3)

Nikita Volkov
Nikita Volkov

Reputation: 43310

The immutable vector implementation of the "vector" package is basically an array. This means that any modifying operation on it requires the traversal of the whole array. That limitation doesn't play well with the requirements that you've mentioned.

Since you're saying that you're open to a choice of a different data-structure, the first thing you need to consider is a data-structure driven by the Array-Mapped Trie algorithm. That algorithm allows you to project on the slices of the data-structure, concatenate, drop/take, append/prepend - all in either a constant or logarithmic time. It's efficiency is proven in production with it driving the ubiquitous immutable vector data-structures of such languages as Clojure and Scala.

Fortunately, Haskell has an implementation as well. It's presented by the "persistent-vector" package, and here's how you can efficiently solve your problem using it:

mapOverSlice :: Int -> Int -> (a -> a) -> Vector a -> Vector a
mapOverSlice startIndex length mapper input =
  let
    (split1Heading, split1Trail) =
      splitAt startIndex input
    (split2Heading, split2Trail) =
      splitAt (pred length) split1Trail
    in
      split1Heading <>
      map mapper split2Heading <>
      split2Trail

Upvotes: 3

Frank Schmitt
Frank Schmitt

Reputation: 30775

One way to to this is

  • zip your original vector with [1..] to get a vector with indices
  • map over the zipped vector; if the index is within (skip, skip+nb] then apply f, else return the original value

The implementation is pretty straightforward:

maprange :: (a -> a) -> [a] -> Int -> Int -> [a]
maprange f vector skip nb = map (\(idx,v) -> if idx > skip && idx <= skip+nb then f v else v) zipped_vector
     where zipped_vector = zip [1..] vector

The complexity should be O(n) where n is the size of the original vector (I'm not 100% sure about the complexity of zip, though); if you need something more efficient, you should investigate the data structures mentioned in the answer by Nikita Volkov.

Upvotes: 0

Lumen
Lumen

Reputation: 3574

How about something like

maprange :: (a -> a) -> [a] -> Int -> Int -> [a]
maprange f vector skip nb = (take skip vector) ++ (map f (take nb (drop skip vector))) ++ (drop (skip + nb) vector)

and then use it like

*Main> maprange (\x -> 2*x) [1 .. 10] 3 4
[1,2,3,8,10,12,14,8,9,10]

to double the 4 elements after the first 3 elements.

Upvotes: 0

Related Questions