Haskell: Filtering based on an index vector, using only basic higher-order functions

Question

The problem

I have a vector a of size N holding sample data, and another vector b of size M (N>M) holding indices. I would like to obtain a vector c of size N containing the filtered elements from a based on the indices in b.

The question

Is it possible to implement the desired function without using list comprehension, just basic higher-order functions like map, zipWith, filter, etc. (more precisely, their equivalents mapV, zipWithV, filterV, etc.)

Prerequisites:

I am using a Haskell Embedded Domain Specific Language (ForSyDe, module ForSyDe.Shallow.Vector), limited to a set of hardware synthesize-able functions. In order to respect the design methodology, I am allowed to use only the provided functions (thus I cannot use list comprehensions, etc.)

Answer 1

Disclaimer:

I did not test this code for functionality because cabal started bugging around. It worked well for lists and as I transformed every vector to a list, it should work fine although problems may arise.

---

Try this:

indexFilter :: (Num b, Eq b, Enum b) => Vector a -> Vector b -> Vector a
indexFilter vector indices = vector (map fst (filter (\x -> (snd x) `elem` (fromVector indices)) vectorMap))
 where
   vectorMap = zip (fromVector vector) [0..]

indexFilter takes a list of tuple of the form (<element>, <index>) and then returns a vector of all elements which index is in the vector b. vectorMap is a just a zip of the elements of a and their indices in the vector.

Answer 2

Although the answer provided by ThreeFx is a correct answer to the question, it did not solve my problem due to several constraints enforced by the design methodology (ForSyDe), which were not mentioned:

• lists cannot be used (they cannot be synthesized to other backends). ForSyDe provides two data containers: Signal (for temporal span) and Vector (for spatial span). This should ensure analyzability for system synthesis.
• elem does not have a ForSyDe.Shallow.Vector implementation

Solution 1

Using only what the library provides, the shortest solution I found is:

indexFilter1     :: (Num b, Eq b, Enum b) => Vector a 
                     -> Vector b 
                     -> Vector (Vector a)
indexFilter1 v = mapV (\idx -> selectV idx 1 1 v)

The output vector can further be unwrapped, depending on the further usage.

Solution 2

Translating ThreeFx's solution to satisfy the constraints mentioned:

 indexFilter       :: (Num b, Eq b, Enum b) => Vector a 
                      -> Vector b 
                      -> Vector a
 indexFilter v idx = mapV (fst) (filterV (\x -> elemV (snd x) idx) vectorMap)
     where
       vectorMap = zipWithV (\a b -> (b, a)) (iterateV size (+1) 0) v
       size      = lengthV v
       elemV a   = foldlV (\acc x -> if x == a then True else acc) False