Блог

Я играю с векторами и распакованными векторами с помощью довольно простой программы. Я перечисляю все целые числа, единственными факторами которых являются 2,3 и 5.

Я подумал, что попробую записать это на память Data.Vector , что сработало и было очень просто. Так что я решил попробовать Data.Vector.Unboxed . Однако он зависает, когда z равно [0..5] , но не тогда, когда z равно [0..4] , и я не уверен, почему. Разница между ними заключается в том, что 5 включает взаимно рекурсивный вызов.

Что здесь происходит не так?

 import Data.Vector.Unboxed as UV

memoisingCandidateUV :: UV.Vector Bool
memoisingCandidateUV = UV.map isCandidateUV z

isCandidateUV :: Int -> Bool
isCandidateUV 0 = False
isCandidateUV n
    | n2r == 0 = n2q == 1 || memoisingCandidateUV UV.! n2q
    | n3r == 0 = n3q == 1 || memoisingCandidateUV UV.! n3q
    | n5r == 0 = n5q == 1 || memoisingCandidateUV UV.! n5q
    | otherwise = False
    where
      (n2q, n2r) = n `quotRem` 2
      (n3q, n3r) = n `quotRem` 3
      (n5q, n5r) = n `quotRem` 5
  

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

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

В этом конкретном случае (все рекурсивные вызовы относятся к меньшим индексам и n могут быть восстановлены из уже вычисленного вектора), вы можете использовать constructN (он работает итеративно, а не полагается на лень):

 import Data.Vector.Unboxed as UV

memoisingCandidateUV :: UV.Vector Bool
memoisingCandidateUV = UV.constructN 100 isCandidateUV

isCandidateUV :: UV.Vector Bool -> Bool
isCandidateUV vec = result
  where
    n = UV.length vec

    result
      |   n == 0 = False
      | n2r == 0 = n2q == 1 || vec UV.! n2q
      | n3r == 0 = n3q == 1 || vec UV.! n3q
      | n5r == 0 = n5q == 1 || vec UV.! n5q
      | otherwise = False

    (n2q, n2r) = n `quotRem` 2
    (n3q, n3r) = n `quotRem` 3
    (n5q, n5r) = n `quotRem` 5