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

[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

[thesz.livejournal.com]

А что означает xs(_@ys)?

[lomeo.livejournal.com]

Бляха-муха, быстро писал.
Исправил, спасибо.

[thesz.livejournal.com]

А он маньяк, судя по всему. ;)

Форсирование вычислений паттернами я тоже делал, но тут как-то... жестковато, что-ли. ;)

[lomeo.livejournal.com]

Ах, и ты тоже! ;-)

[thesz.livejournal.com]

"Кто, кроме меня?
Если не я, то кто же?" (C) чьи-то стихи.

;)

[lomeo.livejournal.com]

А ты тоже в таких случаях говоришь "Эврика!"?

[thesz.livejournal.com]

Ну, у меня случаи попроще.

Я просто тупо форсирую вычисления. ;)

[deni-ok.livejournal.com]

Я думаю, имелось ввиду xs@(_:ys)

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

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

[rvp74.livejournal.com]

Мое решение, которое пришло мне сходу в первую минуту:

myDropWhile p xs = res 
 where
  (_,res) = foldr f ([],[]) xs
  f x (acc,res) | p x       = (x:acc,res)
                | otherwise = (x:acc,x:acc)

[lomeo.livejournal.com]

Я его просто уже знал - оно из Graham Hutton "A Tutorial on the Universality and Expressiveness of Fold".
Поэтому мне было интересно сделать по другому :)

[deni-ok.livejournal.com]

> Как он это сообразил, не пойму... Он то, конечно, говорит, мол, Эврика! и всё такое...

Он там дальше раскрывает тайну:

the functional programming coprocessor in my head

:-)

[lomeo.livejournal.com]

Где такие ставят? :)

[deni-ok.livejournal.com]

Я думаю где-то в Англии. Или в Шотландии. :)

[eraplee.livejournal.com]

или я чето не понял, или решение просто :)

mdropWhile p l = foldr (\x (y:ys) -> if p y then ys else (y:ys)) l [0..length l - 1]

Там ещё было дополнительное требование

[deni-ok.livejournal.com]

It is also highly desirable that the non-strictness of dropWhile is preserved. For instance, it should still be able to return results on infinite lists:

Hugs> take 3 (dropWhile (<5) [1..])
[5,6,7]

Вызов length портит non-strictness.

[deni-ok.livejournal.com]

А вообще да, неожиданное решение!

[lomeo.livejournal.com]

О, интересно.

[migmit.livejournal.com]

Забавно... Я, по чисто эстетическим причинам, почти всегда использую второй вариант.

[lomeo.livejournal.com]

Угу, может быть и я тоже его использовал бы, но только разницы не заметил :(
Вообще, когда начинаются разговоры о том, что вот здесь лениво, а тут strict, поэтому семантика нарушается, это ещё достаточно легко поглядеть глазом, но когда от этого зависит производительность, приходится брать в руку ручку. Я про себя, разумеется.