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

[permea-kra.livejournal.com]

No, there is no standard way to do such things, i.e. there is no famous functions in base libraries that does something alike. You can build your one primitives to work with lists, however. Parser combinators library like ReadP is a good start point.

[rinver.livejournal.com]

Наверное так. Но что если этой функции подать список из нечётного количества элементов ? :) Или нефиг ? :)

[nivanych.livejournal.com]

Надо было добавить что-нибудь, вроде
pairwise (x:[]) = [(x,x)] или []
Без подобного паттерн получается неполным.

[http://users.livejournal.com/_navi_/]

Nothing standard comes to my. There's a problem with your code btw: pairwise is not tail-recursive and will blow up the stack.

[huzhepidarasa.livejournal.com]

а как сделать tail-recursive чтобы не разворачивало список?

[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]

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

[alexey-rom.livejournal.com]

It isn't tail-recursive, but it is bounded-recursive (all recursive calls are under data constructors), which is more relevant when returning lazy structures. See, e.g. http://debasishg.blogspot.com/2009/01/to-tail-recurse-or-not-part-2-follow-up.html

[nivanych.livejournal.com]

> is there something that does it already

А какая разница, если это пишется за полминуты?

[nivanych.livejournal.com]

Вот так будет лучше (и паттерн полный) ->
pairwise (x:y:rest) = (x,y) : pairwise rest
pairwise _ = []

[vyahhi.livejournal.com]

zip xs (tail xs)
и как-нибудь взять все элементы с позиций 0,2..

[nivanych.livejournal.com]

Так и быть ;-)

takeNth _ [] = []
takeNth n lst = (head lst) : takeNth (drop n lst)

pairwise lst = takeNth 1 $ zip lst (tail lst)

[nivanych.livejournal.com]

Описался. Конечно же,
pairwise lst = takeNth 2 $ zip lst (tail lst)

[vyahhi.livejournal.com]

Да, даже длиннее получилось :(

[nivanych.livejournal.com]

Зато более универсально.
Это самое takeNth может ещё где-то потребоваться.

[nivanych.livejournal.com]

Там вон снизу прикольную идею с cycle высказали.
На той же идее
takeNth n lst = map fst $ filter (\(x,t)-> t == 1) $ zip lst $ cycle [1..n]
Но по-моему, это уже извраты,
которые непонятно, для чего нужны,
кроме как, сэкономить лишнюю строчку.
Лучше писать тупо и понятно,
потом свой же код проще смотреть.

полет фантазии

[huzhepidarasa.livejournal.com]

pairwise xs = uncurry zip $ pairmap (map snd) $ partition fst $ zip (cycle [True, False]) xs
  where pairmap f (x,y) = (f x, f y)

хотел без рекурсии и не определяя никаких вспомогательных ф-й, но не вышло

Re: полет фантазии

[huzhepidarasa.livejournal.com]

объединяя с предыдущей идеей

pairwise xs = map snd $ filter fst $ zip (cycle [True, False]) $ zip xs (tail xs)

Re: полет фантазии

[ivan-gandhi.livejournal.com]

О! cycle приходит на помощь!

Re: полет фантазии

[nivanych.livejournal.com]

Прикольная идея ;-)

[http://users.livejournal.com/_adept_/]

Как всегда, забыли unfoldr :)


splitInto n = unfoldr (chunk n)
where chunk _ [] = Nothing
chunk n lst = Just $ splitAt n lst


[ivan-gandhi.livejournal.com]

Вот! Не слыхал про unfold раньше, но это то, что должно было вертеться на языке.