Подтвердить что ты не робот

Haskell - строгий против нестрогого с foldl

У меня есть вопрос относительно определения строгих vs нестрогих. В вики-книге Haskell для Laziness (http://en.wikibooks.org/wiki/Haskell/Laziness) в разделе "Анализ строгости черного ящика" делается следующее утверждение:

[Предполагая функцию f, которая принимает один параметр.] Функция f является строгой функцией, если и только если f undefined приводит к печатанию ошибки и остановке нашей программы.

Вики контрастируют const с id, показывая нестрогую и строгую функцию соответственно.

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

Однако вышеприведенный тест, похоже, утверждает, что и foldl, и foldl 'строги. То есть обе функции производят undefined, если любой из их параметров undefined:

> Data.List.foldl (+) undefined [1,2,3,4]
    Prelude.undefined
> Data.List.foldl' (+) 0 undefined
    Prelude.undefined
> Data.List.foldl' (+) undefined [1,2,3,4]
    Prelude.undefined
> Data.List.foldl (+) 0 undefined
    Prelude.undefined

Может кто-нибудь объяснить, что мне не хватает?

Спасибо!

4b9b3361

ОТВЕТЫ

Ответ 1

Лучшее определение: функция называется строгой в аргументе, если она undefined в случае, если этот аргумент undefined.

Посмотрим на следующее определение foldl:

 foldl f s [] = s
 foldl f s (x:xs) = foldl f (f s x) xs

Из этого можно сделать следующее:

  • Он не является строгим в f, потому что значение f несущественно в первом уравнении.
  • Он не является строгим в s, так как список может быть непустым, а f может быть нестрогим в нем первым аргументом (подумайте flip const).
  • Строго в аргументе списка, однако, потому что, независимо от того, что f и s, этот аргумент должен быть оценен так называемой слабой головной нормальной формой. Значение типа алгебраических данных находится в WHNF, если вы можете указать внешний конструктор. Иными словами, не существует способа, чтобы foldl мог избежать поиска, если аргумент списка является пустым списком или нет. И, следовательно, он должен оценивать значение списка по крайней мере до сих пор. Но если это значение undefined, ни одно из двух уравнений не применимо, поэтому это приложение foldl само по себе undefined.

Кроме того, из того, что foldl не является строгим в аккумуляторе s, мы также можем узнать, почему во многих случаях плохая идея использовать foldl: система не видит причин действительно оценивать термин f s x, так как он передается функции, которая не является строгой в соответствующем аргументе. Действительно, это было бы нарушением принципов ненапряженности, если бы оно это оценило. Следовательно, в зависимости от длины списка в аккумуляторе накапливается огромный кусок:

((((s `f` x_1) `f` x_2) `f` x_3) ....) `f` x_n)

Теперь, если сам f является строгим в своем левом аргументе, например (+), любая попытка оценить результат foldl с необходимостью требует пространства стека, пропорционального длине списка. Для оценки f ... x_n, где ... обозначает левую сторону, сначала нужно оценить эту левую сторону и т.д., Вплоть до f s x_1 и обратно.

Отсюда следует, что

foldl (flip const) 0 [1..n]

есть n, а

foldl const 0 [1..n]

будет стекать переполнение для достаточно больших n. Это верный индикатор, что здесь случаи, когда люди лучше разбираются в компьютерах, чем в машинах, так как во втором примере длина и содержание списка совершенно неактуальны, и большинство людей сразу увидит, что результат должен быть 0.

Ответ 2

В разделе вики, которое вы цитируете, предполагается, что вы имеете дело с функцией, которая принимает один аргумент. Ситуация с foldl отличается, во-первых, потому что она принимает несколько аргументов, но что более важно, потому что один из этих аргументов является функцией. Давайте рассмотрим несколько примеров и посмотрим, когда foldl является строгим в своих аргументах. (Обратите внимание, что к foldl' относится также следующее.)

> foldl undefined 0 []
0
> foldl undefined 0 [1]
*** Exception: Prelude.undefined

Для пустых списков foldl не нужна функция объединения, переданная ему. В этом случае он не является строгим в первом аргументе.

> foldl (+) undefined [1, 2, 3]
*** Exception: Prelude.undefined
> foldl (+) 0 undefined
*** Exception: Prelude.undefined

Когда вы передаете (+) в качестве функции объединения, он строит исходное значение и список. Вот еще один пример с другой функцией комбинирования:

> foldl (flip (:)) undefined [1, 2, 3]
[3,2,1*** Exception: Prelude.undefined

Интересно. Начальное значение undefined, но кажется, что вызов foldl дал некоторые результаты, прежде чем выбрасывать исключение. Что об этом:

> let (x:xs) = foldl (flip (:)) undefined [1, 2, 3]
> x
3

Никаких исключений нет. Таким образом, мы можем получить частичный результат из foldl без попадания в страшный Prelude.undefined. Почему?

Ну, единственное, что изменилось, это функция объединения, которую мы передали foldl. В то время как (+) имеет тип (примерно) Int -> Int -> Int, flip (:) имеет тип [a] -> a -> [a]. В то время как 3 + ((2 + 1) + undefined) не находится в слабой нормальной форме головы и должен быть уменьшен таким образом, что оценивается undefined, (3:(2:(1:undefined))) находится в слабом состоянии нормальная форма, которая не требует дополнительной оценки и, в частности, не требует оценки undefined.