Перенесите значения в отдельные векторы, используя generate

Я пытаюсь создать кортеж из Vector с помощью функции, которая создает настраиваемый тип данных (или кортеж) значений из индекса. Вот подход, который позволяет достичь желаемого результата:

import Prelude hiding (map, unzip)
import Data.Vector hiding (map)
import Data.Array.Repa
import Data.Functor.Identity

data Foo = Foo {fooX :: Int, fooY :: Int}

unfoo :: Foo -> (Int, Int)
unfoo (Foo x y) = (x, y)

make :: Int -> (Int -> Foo) -> (Vector Int, Vector Int)
make n f = unzip $ generate n getElt where
  getElt i = unfoo $ f i

За исключением того, что я хотел бы сделать это за одну итерацию для каждого вектора, почти как показано ниже, но избегая многократного вычисления функции f:

make' :: Int -> (Int -> Foo) -> (Vector Int, Vector Int)
make' n f = (generate n getElt1, generate n getElt2) where
  getElt1 i = fooX $ f i
  getElt2 i = fooY $ f i

Просто в качестве примечания я понимаю, что библиотека Vector поддерживает слияние, и первый пример уже довольно эффективен. Мне нужно решение концепции generate, другие библиотеки имеют очень похожие конструкторы (например, у Repa есть fromFunction), и я использую здесь Vector просто для демонстрации проблемы.

Возможно, какое-то запоминание вызова функции f сработало бы, но я ничего не могу придумать.

Изменить:

Еще одна демонстрация проблемы с использованием Repa:

makeR :: Int -> (Int -> Foo) -> (Array U DIM1 Int, Array U DIM1 Int)
makeR n f = runIdentity $ do
  let arr = fromFunction (Z :. n) (\ (Z :. i) -> unfoo $ f i)
  arr1 <- computeP $ map fst arr
  arr2 <- computeP $ map snd arr
  return (arr1, arr2)

Так же, как и с векторами, слияние экономит день на производительности, но по-прежнему требуется промежуточный массив arr кортежей, которого я пытаюсь избежать.

Изменить 2: (3 года спустя)

В приведенном выше примере Repa он не будет создавать промежуточный массив, так как fromFunction создает задержанный массив. Вместо этого будет еще хуже, он будет оценивать f дважды для каждого индекса, один раз для первого массива, второй раз для второго массива. Задержанный массив необходимо вычислять, чтобы избежать такого дублирования работы.


haskell haskell-vector repa
person lehins    schedule 24.01.2016    source источник
comment
Это определенно не будет более эффективно, чем ваша первая версия, но если вы хотите запомнить все Foo, которые вы можете сделать generateM, и нести IntMap Foo в монаде State, то используйте IntMap для генерации второго вектора.   -  person zakyggaps    schedule 24.01.2016
comment
Это будет работать с Vector, но, к сожалению, я не могу использовать монаду в этой конкретной ситуации.   -  person lehins    schedule 24.01.2016

Ответы (2)


arrow_upward
1
arrow_downward

Оглядываясь назад на свой собственный вопрос, заданный несколько лет назад, теперь я могу легко показать, что я пытался сделать раньше и как это сделать.

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

import Control.Monad.ST
import Data.Vector.Primitive
import Data.Vector.Primitive.Mutable

data Foo = Foo {fooX :: Int, fooY :: Int}

make :: Int -> (Int -> Foo) -> (Vector Int, Vector Int)
make n f = runST $ do
  let n' = max 0 n
  mv1 <- new n'
  mv2 <- new n'
  let fillVectors i
        | i < n' = let Foo x y = f i
                   in write mv1 i x >> write mv2 i y >> fillVectors (i + 1)
        | otherwise = return ()
  fillVectors 0
  v1 <- unsafeFreeze mv1
  v2 <- unsafeFreeze mv2
  return (v1, v2)

И мы используем его аналогичным образом, это делается с generate:

λ> make 10 (\ i -> Foo (i + i) (i * i))
([0,2,4,6,8,10,12,14,16,18],[0,1,4,9,16,25,36,49,64,81])
person lehins    schedule 18.12.2018

arrow_upward
0
arrow_downward

Главное, что вы пытаетесь написать, это

splat f = unzip . fmap f

который разделяет результаты оценки f между двумя векторами результатов, но вы хотите избежать промежуточного вектора. К сожалению, я почти уверен, что у вас не может быть и того, и другого в каком-либо осмысленном смысле. Рассмотрим вектор длины 1 для простоты. Чтобы результирующие векторы могли совместно использовать результат f (v ! 0), каждому из них потребуется ссылка на преобразователь, представляющий этот результат. Что ж, этот преобразователь должен где-то быть, и он действительно может быть в векторе.

person dfeuer    schedule 25.01.2016
comment
Я почти уверен, что у меня не может быть и того, и другого, но я хотел, чтобы сообщество заверило меня. Спасибо за ответ. - person lehins; 25.01.2016