LINUX.ORG.RU

Принцип работы seq

 


0

2

Имеется два выражения:

seq ((\True y -> «AAA») undefined) 42

seq ((\True -> \y -> «AAA») undefined) 42

Первый даст «42», второй — расходимость. Помогите разобраться, почему во втором случае имеется расходимость? Ведь мы можем из второго варианта получить первый, так как (\True y -> ...) == (\True -> (\y -> ...)).

Ответ на: комментарий от Crocodoom

Если функция может не использовать свой первый аргумент, очевидно

foldl f z (x:xs) = foldl f (f z x) xs

Даже если f = (\_ x = x), foldl сделает гирлянду замыканий, так как вызова f не происходит вплоть до конца построения дерева вызовов из списка.

Поэтому если foldr позволяет досрочно выйти из свёртки, если f проигнорирует второй аргумент, а foldl' позволяет делать свёртку в фиксированном объёме памяти, то foldl полезного применения не имеет (или я его пока не придумал).

monk ★★★★★ ()
Ответ на: комментарий от monk

foldl сделает гирлянду замыканий
foldl' позволяет делать свёртку в фиксированном объёме памяти, то foldl полезного применения не имеет

Ты почему-то рассматриваешь только случаи, когда в списке хранится что-то небольшое, зато сам список огромен. Тогда действительно, foldl съест много кучи, а foldl' — нет.

Рассмотри противоположный случай. Список небольшой, скажем на 10 элементов, зато внутри него хранятся thunk, которые сами по себе могут содержать очень затратные вычисления. В таком случае нет существенной разницы между foldl и foldl' в смысле обхода самого списка, зато foldl может прервать вычисления досрочно, сэкономив кучу памяти и времени.

Crocodoom ★★ ()
Ответ на: комментарий от qnikst

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

Благодарю за пример. Действительно, там к месту.

Повторюсь foldr всегда когда функция аргумент ленивая по второму аргументу.

Протестировал foldl' const 0 [1..10^8] и foldr (flip const) 0 [1..10^8].

В ghci foldl' в 2-3 раза быстрее. В скомпилированном с -O бинарнике одинаковая скорость.

Видимо оптимизатор как-то соображает, что не надо дерево замыканий строить.

monk ★★★★★ ()
Ответ на: комментарий от Crocodoom

Список небольшой, скажем на 10 элементов, зато внутри него хранятся thunk, которые сами по себе могут содержать очень затратные вычисления.

Я по примеру от qnikst уже понял.

monk ★★★★★ ()
Ответ на: комментарий от monk

В ghci foldl' в 2-3 раза быстрее. В скомпилированном с -O бинарнике одинаковая скорость.

Видимо оптимизатор как-то соображает, что не надо дерево замыканий строить.

Ну так тот самый пресловутый strictness analysis. В скопилированном с -O2 бинарнике ты и разницы между sum и foldl' (+) 0 не заметишь в простых случаях.

Crocodoom ★★ ()
Ответ на: комментарий от qnikst

build-foldr deforestation. https://dl.acm.org/citation.cfm?doid=165180.165214 там правила соотвествующие есть, так что не только дерево замыканий не строится, а даже список который ты проходишь.

Ещё раз благодарю. Плохая привычка оценивать скорость по выражениям в REPL подвела. Для SBCL так можно, а для Racket и Haskell получаются ложные выводы.

monk ★★★★★ ()