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

[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

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

Comments

[deni-ok.livejournal.com]

О! Уже исправили :)

[lomeo.livejournal.com]

Да.. быстро писал, а в ЖЖ ещё компилер хаскелевый не встроили, подлецы.

[deni-ok.livejournal.com]

От них даже интерпретатора фиг дождёшься :)

Кстати (точнее совсем не в тему), нарыл сегодня, ещё не разбирался толком:

Automatic generation of free theorems: http://haskell.as9x.info/index.html

Какой-то немец и документация подробная по-немецки.

[lomeo.livejournal.com]

Ага, знаком - я с онлайновой версией баловался.
Там всё из "теоремы нахаляву" - две модели - обычная и с fixpoint, точно по Вадлеру.

Хорошая вещь, в закладках.

[deni-ok.livejournal.com]

Угу, и у меня там же :)