Проблемы с использованием карты в Haskell

Question

Я пытаюсь создать алгоритм для решения Project Euler Задача 255

Я придумал это решение:

roundedSq n | (roundedSq n) == roundedSq (n-1) = n : roundedSq (n+1)
            | rem n 2 == 1  = n : floor ( ((2*10^((d-1) `div` 2)) + ceiling (n `div` (2*10^((d-1) `div` 2)) )) `div` 2 )
            | otherwise     = n : floor ( ((7*10^((d-2) `div` 2)) + ceiling (n `div` (7*10^((d-2) `div` 2)) )) `div` 2 )
        where
                d = length (map (digitToInt) (show (n)))

average a = (sum a) `div` (length a)
answer = average [map roundedSq [10E13..10E14]]

main = do
  print answer

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

Answer 1

answer = average [map roundedSq [10E13..10E14]]

Вы поместили сопоставленный список в список из одного элемента здесь. Я думаю, возможно, вы имеете в виду:

answer = average (map roundedSq [10E13..10E14])

Answer 2

Проблема с вашим average.

average a = (sum a) `div` (length a)

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

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

Решение: переписать average как функцию, которая обходит список только один раз, так что список можно собирать мусором при его создании.

Пример (не проверено):

average a = sum `div` length
  where (sum, length) = foldl' f (0, 0) a
        f (sum, length) i = (sum + i, length + 1)

Обратите внимание, что здесь используется foldl', начиная с Data.List, а не foldl. foldl имеет свои собственные проблемы с космосом (которые кто-то более знающий, чем я, возможно, пожелает прокомментировать).

И, как указал Тобиас Вярре,

roundedSq n | (roundedSq n) == roundedSq (n-1) = n : roundedSq (n+1)

приведет к бесконечному циклу:

1. мы хотим оценить roundedSq n
2. если (roundedSq n) == roundedSq (n-1) истинно, мы вернем n : roundedSq (n+1) в качестве ответа
3. нам нужно оценить (roundedSq n) == roundedSq (n-1)
4. нам нужно оценить roundedSq n
5. Перейти к 1.

Answer 3

Если вы хотите, чтобы среднее число возвращало число Fractional, вам нужно использовать это определение:

average a = (sum a) / (fromIntegral $ length a)

(/) - оператор деления Fractional, тогда как div - оператор деления Integral. Обратите внимание, что вам также нужно использовать fromIntegral, потому что length возвращает Int, который не является частью класса Fractional.

Answer 4

Вы застрянете в бесконечном цикле из-за

roundedSq n | (roundedSq n) ...

Редактировать: Иногда мне кажется, что у меня дыра в голове. Конечно, в среднем все в порядке.

Тем не менее, поскольку вы не уменьшаете или не увеличиваете все рекурсивные вызовы функции roundedSq, вы никогда не достигнете «дна» и не завершите его.