how to say in Haskell...

[juan_gandhi]

pairwise :: [a] →  [(a, a)]
pairwise [] = []
pairwise (x:y:rest) = (x,y) : pairwise rest

is there something that does it already? Could not figure out.

Comments

[huzhepidarasa.livejournal.com]

нет, что-то не то — pairwise [1..] прекрасно работает, никакого переполнения стека не происходит.

[faceted-jacinth.livejournal.com]

Это потому что она ещё и ленивая. pairwise 1:2:3 = (1, 2) : (pairwise [3]), на стеке ничего нет.

Точно так же foldr может спокойно сворачивать бесконечные списки ничего не переполняя.

[huzhepidarasa.livejournal.com]

не совсем так

*Main> foldr (+) 0 [1..]
*** Exception: stack overflow
*Main> sum [1..]
(комп намертво зависает, считая расходящуюся сумму, но переполнения не происходит)


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

[faceted-jacinth.livejournal.com]

Да нет же. Это у вас (+) стековерфловится, а не фолдр. length (foldr (:) [] (take 10000000 [1..])) замечательно считается и в интерактивном режиме тоже, например.

Посмотрите на определение foldr, нет там никакой рекурсии. А (+) точно так же и foldl оверфловнет -- потому что он на самом деле ничего не вычисляет, а строит огромное дерево термов, при попытке которого и случается SO.

[faceted-jacinth.livejournal.com]

* при попытке вычислить значение которого

[huzhepidarasa.livejournal.com]

а, ну да, в общем понятно. только где такое определение foldr, чтобы без рекурсии?

[faceted-jacinth.livejournal.com]

Ну, я имею в виду, что сам фолдр не вычисляется рекурсивно -- не использует стек. Стек может использовать то, что его вызывает, или переданная ему функция, а сам фолдр (так же, как и pairwise) лениво и нерекурсивно идёт по списку слева-направо, не тратя никакой дополнительной памяти.

foldr f x0 x:xs = f x (foldr f x0 xs)
foldr f x0 [] = x0

[huzhepidarasa.livejournal.com]

ну, если считать, что рекурсивно — это со стеком, то да