Принцип «Разделяй и властвуй», а также бесконечные потоки в Haskell

[@leventov]

Маленькое примечание к этому типу: filter (<10) primes ->> [2,3,5,7, никогда не завершит своего выполнения, т.к. filter не знает, будут ли числа меньше 10 или нет и продолжает их искать.

Да вроде нет, filter ничем не отличается от других ленивых функций.

На тему «разделяй и властвуй» советую очень крутую книжку Ричарда Бёрда «Жемчужины проектирования алгоритмов: функциональный подход», почитать первые главы можно тут: oz.by/books/more10282958.html

[@barmaley_exe]

Вижу, Вас минусуют (это не я :-) ), но никто не отписался, за что.

Да вроде нет, filter ничем не отличается от других ленивых функций.

Автор имеет в виду, что простых чисел, меньших 10 конечное число, но filter никогда об этом не узнает.

[@nsinreal]

Кстати, можно вопрос, а нет там какого-нибудь filterInSorted, takeWhile?

[@barmaley_exe]

takeWhile упоминался в посте, а какого поведения ожидать от filterInSorted, и чем это поможет? Предикат-то не обязан зависеть от упорядоченности.

[@IvanP]

функциа filter обязана проверить каждый элемент листа который ей передаётся, в то время как takeWhile берет элемент за элементом пока условие выполняется. Функция filter в любом случае никогда не завершит своего выполнения при работе с бесконечными потоками (ведь даже filter (>100) primes никогда не завершается, и понятно почему). Можно рассматривать primes как строго возрастающую функцию, и только благодаря этому свойству takeWhile (<10) primes «фильтрует» список правильно.

[@edem]

Принцип «Разделяй и властвуй», а также бесконечные потоки в Haskell

Поэтичное название статьи)

[@Qrilka]

А можно поинтересоваться, в каком это универе курс по Haskell?
Может слайды доступны публике?

[@yupic]

Вот здесь в первых лекциях рассказывается о Haskell. В том числе и о бесконечных потоках, тоже строится бесконечная последовательность простых чисел.

[@Qrilka]

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

[@IvanP]

Технический Университет Вены. Курс «Функциональное программирование». Слайды на немецком языке, поэтому публиковать не стал (ну и чтобы хабраэффект не создавать). Если кому интересно, все слайды тут: http://www.complang.tuwien.ac.at/knoop/lehre/ws1213/fp185A03/fp185A03_ws1213_121204.pdf

[@barmaley_exe]

На матмехе СПбГУ есть аж 2 полугодовых курса по нему. Они не обязательны и не для всех, но желающих не выгоняют.
Слайдов, видимо, нет.

[@Gokjer]

[sum [2..n] | n < — primes] ->> [2,5,14,27,65,90,… поток сум простых чисел

Стоит отметить, что это не поток сумм простых чисел, а поток сумм натуральных от двойки до простого.

[@IvanP]

Спасибо, поправил!

[@grigorym]

Для того, чтобы решить задачу методом «разделяй и властвуй», нужно еще доказать, что агрегация решений подзадач даст решение всей задачи.