Таблица ускорения в Haskell ускоряется

Question

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

oddfac :: Int -> Int
oddfac n = product [1,3...n]

т.е. похож на факториальную функцию, но только умножая нечетные числа. Я хотел бы выполнить эту функцию на ускоренном бэкэнде, поэтому, если я правильно понимаю вещи, она должна иметь тип Exp Int -> Exp Int, Однако библиотека не позволяет вычислять произвольные выражения в Expпо причинам производительности. К счастью, мне нужно оценивать эту функцию только для небольших значений, например, n<=7. У меня была идея определить список (или массив) предварительно рассчитанных возвращаемых значений, чтобы простая индексация возвращала соответствующее значение, и каждая оценка занимала одинаковое количество времени, что не относится к наивной версии. Тем не менее, я не смог найти способ сделать это. Теперь у меня есть два вопроса:

1) Есть ли способ сделать это, то есть определить жестко закодированный массив, который затем индексируется для получения соответствующего значения в функции типа Exp a -> Exp b?

2) Я иду о вещах эффективным способом? Есть ли очевидные недостатки в том, как я думаю об этой проблеме?

ОБНОВИТЬ

Следующие работы основаны на ответе @ErikR и последующих комментариях:

module Test where

import Data.Array.Accelerate as A
import Prelude as P

oddfac :: Exp Int -> Exp Int
oddfac n = (use $ A.fromList (Z :. 6) [1, 1, 3, 3, 15, 15]) A.! (index1 n)

alloddfac :: Acc (Vector Int)
alloddfac = A.map oddfac $ use $ A.fromList (Z :. 3) [1, 3, 5]

Answer 1

Мне кажется, что вы могли бы создать Acc (Array DIM1 Int) используя один из нескольких методов, а затем использовать ускорение (!) с index1 функция для индексации в массиве.

Обратите внимание, что Vector a это псевдоним для Array DIM1 a,

Вот как создать Acc (Vector Int) of the odd factorials (7 elements):

oddfacts :: Acc (Vector Int)
-- analogous to: take 7 $ scanl (*) 1 [3,5..]
oddfacts = A.scanl (*) (constant (1::Int)) $ A.enumFromStepN (A.index1 (constant (7::Int))) (constant (3::Int)) (constant (2::Int))

and here's how to index into it:

foo :: Exp Int -> Exp Int
foo n = oddfacts A.! (A.index1 n)

and how you might use it with a conditional:

bar :: Exp Int-> Exp Int
bar n = (n <=* (constant (7::Int))) ?
           ( oddfacts A.! (A.index1 n)
           , constant (0::Int)           -- return 0 if n > 7
           )

Caveat - I haven't actually run this code, but it type checks.

The examples in the accelerate-examples package has a lot of code that uses the array generation functions (A.generate, A.scanl, etc.) and the indexing functions (A.index1, A.index2, etc.)

Answer 2

Вы можете "перебросить забор" из Хаскелла в Exp произвольные массивы через (Shape sh, Elt e) => Lift Acc (Array sh e) пример. Таким образом, вы можете создать свою таблицу поиска в Haskell, а затем просто lift Это:

import Data.Array.Accelerate as A hiding (product)

oddfac :: Int -> Int
oddfac n = product [1,3..n]

oddfacs :: Vector Int
oddfacs = A.fromFunction (Z :. 7) (\(Z :. i) -> oddfac i)

lut :: Acc (Vector Int)
lut = A.lift oddfacs

Остальное затем можно выполнить в виде ответа la @ErikR путем индексации в таблице соответствия. lut,