Куда прячется ленивость и как ее оттуда достать?

[deniok]

Мы привыкли, что правая свертка (foldr) хорошо заточена для работы с бесконечными списками:

> let mapPlusPi = foldr (\x xs -> (x+pi):xs) []
> head $ mapPlusPi [1..]
4.141592653589793

К сожалению, иногда возникают неприятности. Вот функция, которая берет список и выкидывает из него элементы стоящие на нечетных местах:

> let evenOnly = snd . foldr (\x (os,es) -> (x:es,os)) ([],[])
> evenOnly [1..10]
[2,4,6,8,10]

Только вот на бесконечном списке она ведет себя неподобающе

> head $ evenOnly [1..]
Interrupted.

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

Comments

[voidex.livejournal.com]

Я с телефона, поэтому больше гадаю, но предположительно надо избавиться от разбора кортежа, например, добавив там ~

[deni-ok.livejournal.com]

Бинго!

[pod-baobabom.livejournal.com]

Ну вот примерно так.

let evenOnly = snd . foldr (\x z -> let (os,es) = z in (x:es,os)) ([],[])

В оригинальном примере явный pattern matching в параметре автоматически делает функцию строгой по второму аргументу. Что происходит внутри -- хорошо видно при вызове ghc -O -ddump-stranal. В первом случае demand на параметер -- (S,1*U), во втором -- (L,U(1*U,1*U)).

[sassa-nf.livejournal.com]

let evenOnly = snd . foldr (\x ~(os,es) -> (x:es, os)) ([],[])

а почему именно - надо подумать.

[sassa-nf.livejournal.com]

а, нутк, довольно странно это, конечно, но выходит, что pattern-match не может доказать, что он irrefutable, а потому должен быть strict.

Т.е. например вот здесь:

let bla = foldr(\x (y:t) -> x:t) [0]

понятно, что поскольку у списка есть два конструктора, то нужно убедиться, что y:t, а не []. А вот у тупля только один конструктор, так что, не ясно, что его останавливает лениво матчить.

[voidex.livejournal.com]

То, что помимо (,) у кортежа есть ещё один конструтор: _|_

[thedeemon.livejournal.com]

Анализатор суровости слишком суров. Т.е. строгости. :)

[gds.livejournal.com]

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

[nivanych.livejournal.com]

Иными словами, у повсеместной ленивости есть только один существенный недостаток —
большая непривычность (но не сложность!) рассуждения за costs semantics.
Что довольно сильно, не буду спорить.

[gds.livejournal.com]

и сложность тоже есть -- надо помнить, где что лениво, а где строго. В данной задаче пришлось вспомнить/узнать, что есть волшебное "~" перед паттерном, которое делает лениво. Чем меньше помнить (иметь заученных наизусть знаний), тем проще.

" = "

[alexandermarkov.livejournal.com]

Язык надо знать, дубина!

[gds.livejournal.com]

пасяп)))))))

[nivanych.livejournal.com]

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

[alexandermarkov.livejournal.com]

Тот, на котором погроммируешь, конечно.