Почему toInteger :: Int -> Integer ленив? - PullRequest
Новая
       13

Почему toInteger :: Int -> Integer ленив?

4 голосов
/ 01 мая 2010

У меня есть следующий код: 

{-# NOINLINE i2i #-}
i2i :: Int -> Integer
i2i x = toInteger x

main = print $ i2i 2

Запуск GHC с флагом -ddump-simp дает: 

[Arity 1
 NoCafRefs
 Str: DmdType U(L)]
Main.i2i = GHC.Real.toInteger1

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

(toInteger _|_ ::Int) /= _|_

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

--mean :: Integer -> Integer -> [Integer] -> Double
mean :: Integer -> Int -> [Integer] -> Double
mean acc n [] = fromIntegral acc / fromIntegral n
mean acc n (x:xs) = mean (acc + x) (n + 1) xs

main = print $ mean 0 0 [1..1000000]

Этот код выполняется в пространстве O (N). Когда я раскомментирую первую строку, потребление пространства изменится на O (1). Кажется, это сводится к вызову fromIntegral, который, в свою очередь, сводится к toInteger. Анализатор строгости почему-то не может сделать вывод о строгости преобразования, что мне кажется странным.

Ответы [ 2 ]

13 голосов
/ 01 мая 2010

Ответ на ваше редактирование: опасность утечки пространства O (N) при накоплении параметров хорошо известна, по крайней мере, программистам на Haskell. То, что должно быть хорошо известно, но это не то, что независимо от того, какой язык, вы должны никогда не доверять оптимизатору, чтобы обеспечить асимптотические гарантии для поведения ваших программ в пространстве и времени. Я не понимаю смысла простых оптимизаторов, которые я написал сам, не говоря уже о чем-то волосатом, как передний конец GHC, с анализатором строгости, инлайнером и всем остальным.

Что касается ваших двух вопросов,

Почему анализатор строгости GHC не оптимизирует этот конкретный код, когда он оптимизирует очень похожий код?

Кто знает ?? (Возможно, Саймон ПиДжей знает, а может и нет.) Если вы заботитесь о производительности, вам не следует полагаться на анализатор строгости. Что подводит нас ко второму, подразумеваемому вопросу:

Как можно избежать O (N) затрат пространства на эту функцию и на любую другую функцию, которая использует накапливающиеся параметры?

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

2 голосов
/ 01 мая 2010

Я думаю, что вы смотрите на это неправильно. Рассмотрим следующий глупый фрагмент кода 

let x = [undefined]
let y = map toInteger x

Если мы оценим 

 y == []

мы получаем False, тогда как если мы оцениваем 

 head y

мы получаем исключение undefined. Нет причины, по которой применение map или сравнение y с [] должно расходиться только потому, что единственный элемент x не определен. В этом суть нестрогости.

...