Задачка со свёрткой

[lomeo]

Читал статью Bernie Pope "Getting a Fix from the Right Fold" из The Monad. Reader Issue 6. В ней решается задачка о написании dropWhile через foldr. В частности, эта задачка решалась в Graham Hutton "A Tutorial on the Universality and Expressiveness of Fold" через таплы.

У меня удивительно быстро получилось решить эту задачку. Решение было эквивалентным решению 2 в статье.


Смысл в том, чтобы породить функцию с помощью foldr, которую мы уже затем применим к списку. Функция или вернёт тот же список или обрежет у него хвост, т.е. id (tail (tail (tail (tail (tail xs))))).

myDropWhile p xs = foldr f id xs xs
    where
        f x g xs | p x       = g (tail xs)
                 | otherwise = xs

К сожалению, это решение неоптимально, т.к. функция, порожденная foldr (та самая к которой мы второй раз применяем список), зависит от количества сброшенных элементов. Pope предлагает решение, которое вместо порождения цепочки функций, попеременно применяет функцию к списку. Для этого достаточно, чтобы tail был вызван раньше g, который является рекурсивным вызовом foldr. С помощью паттерн-матчинга (который как известно неленив) мы получим:

myDropWhile p xs = foldr f id xs xs
    where
        f x g xs@(_:ys) | p x       = g ys
                        | otherwise = xs

Я бы не догадался. Мне пришлось бы расписывать пример, как проходит вычисление, чтобы до этого дойти. Как он это сообразил, не пойму... Он то, конечно, говорит, мол, Эврика! и всё такое...