Haskell: фильтрация на основе индексного вектора с использованием только основных функций высшего порядка.

Проблема

У меня есть вектор a размера N, содержащий выборочные данные, и другой вектор b размера M (N>M), содержащих индексы. Я хочу получить вектор c размера N, содержащий отфильтрованные элементы из a на основе индексов в b.

Вопрос

Можно ли реализовать желаемую функцию без использования понимания списка, только базовые функции более высокого порядка, такие как map, zipWith, filter и т. д. (точнее, их эквиваленты mapV, zipWithV, filterV и т. д.)

Предпосылки:

Я использую встроенный предметно-ориентированный язык Haskell (ForSyDe, модуль ForSyDe.Shallow.Vector), ограничено набором функций аппаратного синтеза. В целях соблюдения методологии проектирования мне разрешено использовать только предоставленные функции (таким образом, я не могу использовать списки и т. д.).


filter higher-order-functions haskell
person Iedu    schedule 24.07.2014    source источник
comment
Включение списков может быть довольно тривиально преобразовано в map, filter, zipWith и т. д. На самом деле, списки - это просто синтаксический сахар для монадических функций, и ваш тип Vector можно сделать монадой, так что вы могли бы просто написать версию понимания списка и включите MonadComprehensions.   -  person user2407038    schedule 24.07.2014

Ответы (2)


arrow_upward
4
arrow_downward

Отказ от ответственности:

Я не проверял этот код на функциональность, потому что клика начала глючить. Это хорошо работало для списков, и поскольку я преобразовал каждый вектор в список, он должен работать нормально, хотя могут возникнуть проблемы.

Попробуй это:

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 берет список кортежей формы (<element>, <index>), а затем возвращает вектор всех элементов, индекс которых находится в векторе b. vectorMap - это просто почтовый индекс элементов a и их индексов в векторе.

person ThreeFx    schedule 24.07.2014
comment
Спасибо, я пробую ваш метод прямо сейчас, переводя его в свою проблему (применяя некоторые ограничения, чтобы сделать его синтезируемым). С другой стороны, это кажется отличным ответом и имеет смысл. - person Iedu; 24.07.2014
comment
@GeorgeUngureanu Дайте мне знать, если возникнут дальнейшие проблемы - person ThreeFx; 24.07.2014
comment
Я отметил этот ответ как правильный, потому что он ДЕЙСТВИТЕЛЬНО отвечает на мой вопрос. Однако я не решил свою проблему из-за нескольких ограничений методологии проектирования, которые не упоминаются. Кроме того, предоставленный ответ вызвал ход мыслей, которые привели к решению (решениям), описанным ниже. - person Iedu; 24.07.2014

arrow_upward
4
arrow_downward

Хотя ответ, предоставленный ThreeFx, является правильным ответом на вопрос, он не решил мою проблему из-за нескольких ограничений, налагаемых методология проектирования (ForSyDe), которые не были упомянуты:

  • списки нельзя использовать (их нельзя синтезировать с другими бэкендами). ForSyDe предоставляет два контейнера данных: Signal (для временного диапазона) и Vector (для пространственного диапазона). Это должно обеспечить анализируемость для системного синтеза.
  • elem не имеет реализации ForSyDe.Shallow.Vector

Решение 1

Используя только то, что предоставляет библиотека, самое короткое решение, которое я нашел:

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

Выходной вектор можно дополнительно развернуть, в зависимости от дальнейшего использования.

Решение 2

Перевод решения ThreeFx для удовлетворения упомянутых ограничений:

 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
person Iedu    schedule 24.07.2014