Генерировать простые числа на haskell

по Эратосфену

primes' = sieve [2..] where sieve (s:ss) = s : (filter ((/=0).(`mod` s)) $ sieve ss)

по Бертрану (лучше)

primes = 2 : filter isprime [3,5..] where
    isprime n = all ((/=0).(mod n)) $ takeWhile ((<=n).(^2)) primes

https://wiki.haskell.org/Prime_numbers

чем бертран лучше эратосфена?

Я не компилировал и не игрался с опциями оптимизации, но в интерпретаторе насколько я помню приведенный мной кот Бертрана существенно быстрее кота Эратосфена. Но может последний у меня не оптимальный, я по алгоритмам SICP писал, а ниже привели более подробную и хаскельную ссылку. Но конечно вот это https://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html на порядки быстрее вышеприведенных ручных котов

на самом деле, у тебя это не эратосфен, а ухудшенный бертран (если вообще можно так назвать)

у твоего кота каждый элемент проверяется на делимость на каждое p, и сложность получается n * (n / log n) вместо n * log (log n)

эратосфена на хаскелле сделать несколько проблематично ввиду отсутствия массивов

Одна из главных фишек, которую дает ленивость в языке Haskell, это мемоизация. Это позволяет значению ссылаться на самого себя при вычислении, что либо позволяет делать то, что очень сложно или просто невозможно реализовать на других языках, либо позволяет упростить существенно код и сделать его эффективным как по скорости, так и по потребляемой памяти.

Мемоизировать можно конкретное значение. У тебя же функции, а они каждый раз фактически возвращают новое значение в памяти. Проблема в том, что ты используешь функцию там, где должно быть значение. Это подсказка.

Тема мемоизации хорошо описана в книге «The Haskell school of Expression» за авторством Paul Hudak.

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

Что касается кода, то загляни на главную страницу http://haskell.org. Там этот код давно красуется)

на хаскелле сделать несколько проблематично ввиду отсутствия массивов

Есть массивы, причем нескольких видов. Есть иммутабельные, есть мутабельные.

Если в Haskell есть как зеленые потоки, так и потоки, жестко привязанные к системным (нативным), то массивы в языке должны быть подавно.

если подключать ffi, то вопрос о реализуемости императивных алгоритмов вообще не стоит

это всё без FFI

Есть массивы, причем нескольких видов. Есть иммутабельные, есть мутабельные.

А что проблема из муттабельного массива иммутабельный сделать? Зачем лишние сущности то плодить? ... А, дв, это же хаскель..

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

А при чем тут ленивость? И в чем трудность реализации на других языках? Если функция уже вызывалась она вернет результат, вот и все.

MyTrooName, вполне возможно, что мой Эратосфеновый кот совсем не торт. Но это прямая реализация алгоритма, как он был подан, без оптимизаций. И это почти тот же кот, что в первом ответе темы (а он в свою очередь буква в букву совпадает с красующимся на главной странице http://haskell.org). И, к примеру, при взятии

primes !! 10000

time: 0.07 memory: 4700

filequest всего пара фраз, а уже видно специалиста )...

Я не совсем понял, то ли это был сарказм, то ли что-то исчо, но на всякий случай приведу пример из SICP

Мемоизация (memoization) (называемая также табуляризация (tabulation)) — прием, который поз- воляет процедуре записывать в локальной таблице единожды вычисленные значения. Такой прием может сильно повысить производительность программы. Мемоизированная процедура поддержива- ет таблицу, где сохраняются результаты предыдущих вызовов, а в качестве ключей используются аргументы, относительно которых эти результаты были получены. Когда от мемоизированной про- цедуры требуют вычислить значение, сначала она проверят в таблице, нет ли там уже нужного значения, и если да, то она просто возвращает это значение. Если нет, то она вычисляет значение обычным способом и заносит его в таблицу. В качестве примера мемоизации, вспомним экспоненциальный процесс вычисления чисел Фибоначчи из раздела 1.2.2:

(define (fib n)
 (cond ((= n 0) 0)
       ((= n 1) 1)
 (else (+ (fib (- n 1))
  (fib (- n 2))))))

Мемоизированная версия той же самой процедуры выглядит так: (define memo-fib (memoize (lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (memo-fib (- n 1)) (memo-fib (- n 2)))))))) а процедура memoize определяется так: (define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result))))))

Абсолютно на любом ЯП можно это сделать, не вижу причин выдавать это за фичу хашкеля.

Не надо копипастить сюда простых многабукаф. Это можно сделать на любом языке, но речь не об этом. А об автоматической мемоизации без лишних усилий рассчитанных значений ленивых структур данных, например потока.

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

Если язык достаточно гибок, ты сам делаешь все что тебе надо, и так как надо.

И да, все почему то привыкли говорить о какой-то мифической лени в хашкеле, лень — это конечно, неформальное понятие, любой вася пупкин может называть ленью что угодно, но сраненькие санки — это явно не полноценная лень, скорей ее иллюзия.

но речь не об этом

А о чем речь была, я напомню, раз мы такие забывчивые

очень сложно или просто невозможно реализовать на других языках

Раз мы такие забывчивые (С), то напомню стартовый пост

... генерирующую бесконечный список ...

То есть изначально требуется такая структура данных. Очевидно, она может быть только ленивой. И реализована либо с использованием абстракций языка из коробки, либо костылями в виде генерирующей функции с мемоизацией, если язык это не поддерживает.

я не на стартовый пост отвечал, а на конкретное утверждение, которое я процитировал даже.

Ссылочную прозрачность тоже нужно учитывать.

Но это прямая реализация алгоритма, как он был подан, без оптимизаций. И это почти тот же кот, что в первом ответе темы (а он в свою очередь буква в букву совпадает с красующимся на главной странице http://haskell.org)

да пофиг. я просто о том, что для оценки скорости эратосфена (алгоритма) эти реализации не подходят.

хотел бы я посмотреть на реализацию массивов на чистом хаскеле

смотри

А при чем тут ленивость? И в чем трудность реализации на других языках? Если функция уже вызывалась она вернет результат, вот и все.

Ты не понял. Читай книгу. Там есть пример и с функцией. Как раз дело в ленивости. Автору настоящего топика очень не хватало ее. Иначе получаем чудовищно неэффективный алгоритм.

В других языках нет MonadFix и особенно ArrowLoop. Если по простому, то это рекурсивные вычисления или вычисления, которые выражаются через самих себя, например, уравнения с обратными связями или схемы и автоматы с обратными связями.

Что ты несешь?

$ ghci
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude> :m Data.Array
Prelude Data.Array> :t array
array :: Ix i => (i, i) -> [(i, e)] -> Array i e

Задаются индексы и генератор элементов массива для создания иммутабельного массива. Элементы могут ссылаться на сам массив при желании.

нет MonadFix и особенно ArrowLoop

а, ну тогда все пропало, да.

runST buildPair

а полноценные, без монады есть?

реализацию массивов на чистом хаскеле

не вижу

не вижу

ну, со зрением я тебе не помогу, тут только к окулисту

Может лучше тебе к психиатру, на предмет того, что видится несуществующее?

а полноценные, без монады есть?

Ржу в голос.

Что попросим дальше? Полноценные массивы в Си, без указателей?

А разве хаскель такое умеет? Он же для факториалов.

Твой юмор забавляет) Есть такая штука как парадокс Блаба. Именно здесь он и проявляется c MonadFix и ArrowLoop в полной мере)

Но я думаю, что студентов этим вещам обычно не учат, поскольку сами преподаватели могут в них ни фига не разбираться, хотя там ничего особенно сложного. Просто немного непривычно для тех, кто имеет уже груз мейнстримных языков. Вот, ворчу, а сам до черта кода пишу именно на мейнстримных языках.

эратосфена на хаскелле сделать несколько проблематично ввиду отсутствия массивов

- массивы там есть;

- можно и без них.

да - проблема, т.е. с мутабельными структурами алгоритмы GC сильно усложняются т.к. более старые объекты имеют ссылки на молодые.