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

4
votes

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.)

2
haskellfilterhigher-order-functions
List comprehensions can be fairly trivially translated to map, filter, zipWith, etc. In fact, list comprehensions are just syntactic sugar for monadic functions, and your Vector type can be made a monad, so you could could just write the list comprehension version and turn on MonadComprehensions. – user2407038

2 Answers

4
votes

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.

4
votes

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