Тут приводился исвестный пример вычисления среднего значения в списке, захотелось его допилить:
-- Попытка 1:
mysum :: [Integer] -> Integer
mysum xs = sum' xs 0
where
sum' [] acc = acc
sum' (x:xs) acc = sum' xs (acc + x)
mean1 :: [Integer] -> Double
mean1 xs = fromIntegral (mysum xs) / fromIntegral (length xs)
-- Попытка 2:
mean2 :: [Integer] -> Double
mean2 xs = fromIntegral s / fromIntegral l
where
(s, l) = mean' xs 0 0
mean' :: [Integer] -> Integer -> Integer -> (Integer, Integer)
mean' [] accSum accLen = (accSum, accLen) -- ((,) $! accSum) $! accLen
mean' (x:xs) accSum accLen = mean' xs (accSum + x) (accLen + 1)
-- Пробуем:
n = 10000000
list = [1..n]
--main = putStrLn $ show $ mysum list
--main = putStrLn $ show $ mean1 list
main = putStrLn $ show $ mean2 list
Замечания и вопросы:
Как компилятор (с опцией -O) понимает, что функция mysum — строгая? Я несколько раз встречал упоминания о том, что '+' — строгий, но непонятно, откуда это — в Haskell Report я ничего не нашел. Можно ли всегда на это полагаться или это фича GHC?
Почему mean1 жрет память в объеме O(N), понятно — см. http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16, хотя если при таком тривиальном изменении программы приходится смотреть на Core Haskell, это неуютно как-то.
Можно ли как-то заставить работать mean2 без использования лишней памяти, не прибегая к хакам вроде $! или seq?
Правильно ли я понимаю, что stack space overflow выдается из-за того, что начинает вычисляться отложенное вычисление (...((0+1)+2)+...+N), а не из-за того, что компилятор не сделал tail-call optimization?
Здравствуйте, jpx, Вы писали:
jpx>Но опять же, почему деление строгое?
значит, как работает анализатор строгости:
есть у тебя к примеру функция
f x y | y>0 = ...
f x y = ...
анализатор смотрит на это дело и видит, что без знания значения y мы не сможем дальше продвинуться в вычислении f. в данном случае он нам банально необходим для выбора альтернативы. это называется фукнция f строга по аргументу y. строго говоря функция строга по аргументу, если f _|_ = _|_, но это то же самое, только выраженное более математическим языком — значение функции вычислить не удастся если значение аргумента неизвестно
функции +,/ строги, потому что ghc проанализировал их определения и нашёл что они удовлетворяют этому условию
Здравствуйте, jpx, Вы писали:
jpx>Но опять же, почему деление строгое?
А в каком смысле встроенная функция может быть нестрогой? Если у нас есть ленивая myFunc a b, то в рантайме STG-машины происходит обращение к коду myFunc и выполняются редукции, которые там есть. Дойдет ли дело до аргументов — выясняется в процессе этих редукций. А для (+) a b никаких редукций в плюсе (или, там, делении) нету. Это же не числа Пеано, Int'ы складываются атомарно, с помощью средств целевой платформы. Если рантайм добрался до (+), то для вызова низкоуровневого кода сложения аргументы необходимы.
Здравствуйте, jpx, Вы писали:
jpx> Почему mean1 жрет память в объеме O(N), понятно — см. http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16, хотя если при таком тривиальном изменении программы приходится смотреть на Core Haskell, это неуютно как-то.
не надо воспринимать возможность работать с большими списками в O(1) памяти как всегда существующую. считай это полезным хаком, которого можно добиться, посмотрев в core или просто понимая как работает laziness. н хочешь думать — получаешь с гарантией поведение не хуже чем в обычных языках
jpx> Можно ли как-то заставить работать mean2 без использования лишней памяти, не прибегая к хакам вроде $! или seq?
есть ли хак, который позволяет обойтись без хаков? сейчас достаточно поставить ! перед именем аргумента, чтобы он стал строго вычисляться при вызове функции
jpx> Правильно ли я понимаю, что stack space overflow выдается из-за того, что начинает вычисляться отложенное вычисление (...((0+1)+2)+...+N), а не из-за того, что компилятор не сделал tail-call optimization?
не понятно, где именно, но всё равно да. mysum у тебя создаёт такой thunk и вероятно mean2 (без кахов ) тоже
вообще, добиться от ghc чтоб он не делал tail-call optimization — это надо постараться
Здравствуйте, deniok, Вы писали:
D>А в каком смысле встроенная функция может быть нестрогой?
а это не встроенные функции. встроенные +-*/ работают с небоксированными значениями, и они конечно не могут быть ленивыми а определения +-*/ дебоксируют аргументы и вызывают встроенные функции, типа такого:
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, deniok, Вы писали:
D>>А в каком смысле встроенная функция может быть нестрогой?
BZ>а это не встроенные функции. встроенные +-*/ работают с небоксированными значениями, и они конечно не могут быть ленивыми а определения +-*/ дебоксируют аргументы и вызывают встроенные функции, типа такого:
BZ>instance Num Double BZ> (D# x) + (D# y) = D# (x +## y)
Да, правильно, просто топикстартеру "неуютно как-то смотреть в Core Haskell", так что я решил опустить часть уровней абстракции Боксирование, всё-таки, деталь реализации GHC. А так, да, заключение о строгости дает ее анализатор.
Кстати, прикольно, что, если бы мы имели дело с числами Черча
data Nat = Z | S Nat
(+) :: Nat -> Nat -> Nat
Z + m = m
(S n) + m = n + S m
то второе слагаемое вполне себе может быть undefined.
Здравствуйте, deniok, Вы писали:
D>>>А в каком смысле встроенная функция может быть нестрогой?
D>Да, правильно, просто топикстартеру "неуютно как-то смотреть в Core Haskell", так что я решил опустить часть уровней абстракции
насколько я понимаю, встроенная функция может быть нестрогой, к примеру par и par#
BZ>насколько я понимаю, встроенная функция может быть нестрогой, к примеру par и par#
В этом случае, как я понимаю глядя в исходники, приходится дурить компилятор:
-- The reason for the strange "lazy" call is that
-- it fools the compiler into thinking that pseq and par are non-strict in
-- their second argument (even if it inlines pseq at the call site).
-- If it thinks pseq is strict in "y", then it often evaluates
-- "y" before "x", which is totally wrong.
{-# INLINE pseq #-}
pseq :: a -> b -> b
pseq x y = x `seq` lazy y
{-# INLINE par #-}
par :: a -> b -> b
par x y = case (par# x) of { _ -> lazy y }
Здравствуйте, jpx, Вы писали:
jpx>Здравствуйте, deniok, Вы писали:
D>> А в каком смысле встроенная функция может быть нестрогой?
jpx>Ну например реализация Integer может быть какой-нибудь ленивой структурой данных.
Можно, конечно, только в этом нет никакого прикладного смысла; у конечного пользователя нет средств использовать подобную ленивость, поскольку определение Integer не рекурсивно. Конструкторы данных у Integer примитивные 1, 42, 1000000000000001, поэтому сопоставление с образцом с частичным разбором по структуре не пройдет. А числа Черча, к несчастью, вычислительно крайне неэффективны.
jpx>В любом случае, это детали реализации. Такое поведение прописано в спецификации или нет, интересно?
В спецификации написано
Function application in Haskell is non-strict; that is, a function argument is evaluated only when required.
(6.2 Strict Evaluation)
Но если редукции дошли до (+) x y, то вычисление x и y уже в любом случае required, не так ли?
функция строга по аргументу, если f _|_ = _|_, но это то же самое, только выраженное более математическим языком — значение функции вычислить не удастся если значение аргумента неизвестно
сейчас достаточно поставить ! перед именем аргумента, чтобы он стал строго вычисляться при вызове функции