Sieve of Eratosthenes in Elm?

[polarit]

I tried to find a code for searching prime numbers but there is hardly anything written in elm, not much in any other functional programmng language either. Maybe the primes are not an interesting topic in a language used mainly in frontend codes. Perhaps it’s piece of cake to write a code for Eratoshenes sieve in FP and it’s assumed everybody can do it for him(her)self.

There is one exception, Haskell, see Sieve of Eratosthenes but I don’t read haskell.

I wrote a little piece just for begin using elm repl…
This shall find all primes of the range 1 … 121.
The primes used in sieve [2,3,5,7,11] are dropped from beginning of the resulting list.

sieve prime integers = List.filter (\i → remainderBy prime i > 0) integers
: Int → List Int → List Int

il = List.range 1 121

sieve 2 il |> sieve 3 |> sieve 5 |> sieve 7 |> sieve 11
[1,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
: List Int

How about using combination of sieve function, map2 and filter or foldl or recursion and sieve?
I don’t know yet.

[Carsten_Konig]

Hi,

first a disclaimer: a sieve-function will not be fast and this one will be slower than man you can come up with I’m sure.

In case you want something like a direct translation from the Haskell one (the one with fixed upper bound - if you like you can do the same for lazy-lists - there is a Seq package that comes close-ish):

primesTo : Int -> List Int
primesTo m =
    let
        multiplesOf n =
            let
                go x =
                    if x <= m then
                        x :: go (x + n)

                    else
                        []
            in
            go n

        sieve nrs =
            case ( List.head nrs, List.tail nrs ) of
                ( Just x, Just xs ) ->
                    x :: sieve (List.filter (\y -> not (List.member y (multiplesOf x))) xs)

                _ ->
                    []
    in
    sieve (List.range 2 m)

here is a quick REPL test:

> Main.primesTo 100
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

---

I think you should be able to use the ideas here (recursion within multiplesOf and sieve) to get yours in the right direction too.

have fun

[polarit]

Hallo @Carsten_Konig ,

yes, this works fine for small integers.
However, the next happens if the code is run in elm repl on my old MacBook Air with 8 GB RAM only:

b = primesTo 13444
RangeError: Maximum call stack size exceeded
b = primesTo 13443
[2,3,5,7,11,13,…, ,13411,13417,13421,13441]

If a limited range of bigger primes with the lower limit is used, maybe it would not cause stack overflow.
See for instance this SPA example I wrote to be run with elm-spa server.

It finds primes at least for a range [200003 200009 200017 200023 … 202129 202183 202187 202201 ]

However, I would like to continue with your code but I don’t know, whereto set the lower limit of primes range exactly, would you kindly advise me?

[Carsten_Konig]

Hi,

to be honest I would not bother to overthink this - what exactly is your use case here?
As I said before: the Sieve is not really an efficient algorithm for finding primes (for a computer)

[polarit]

This is for me personnally just a case of learning a bit more about coding in Elm because FP happens to be my favourite too.

I have imaginated that searching primes does’nt require that amount of complexity of code as it happens to do. I believed earlier that all recursion could be avoided if some List functions e.g. filter, map, foldl etc. are properly used.

There are many examples of shorter codes for prime sieve in C++ and Python but they are no FP codes. Sure, simple but not effective in running speed.

I understand fully that you mind continuing on this topic.

Anyway, I have enjoyed lots on reading your article about FP .

[Carsten_Konig]

Yes you should be able to rewrite most of this into List.fold style - maybe it’s a good exercise for you? If you want I can have a go at it but it’ll probably have to wait till tomorrow.

I don’t mind continuing this here it’s just that I don’t really use Elm for this kind of algorithms (I’d go with Haskell here) so I constantly are missing functions I’d go to.
There are packages like list-extra that includes some of those but I though it’s better to keep it with what comes after elm init.

To be honest I don’t have much experience in optimizing Elm in that way (there is the compiler in between and the output contains all the runtime so it’s not easy to see what is produced).

Concerning the StackOverflow: usually you can get rid of this by pushing stuff on the heap instead of the stack (continuations often work) so with a bit of work we should be able to fix this.

But then you have a big messy piece of code where the original concern probably is almost not recognizable.

That’s why I personally would keep it simple and see how to get this working for small numbers - especially if this is only for learning purposes.

[Carsten_Konig]

PS: look at the filter function - if you do mod instead of member there you should be good to go - I really tried to give something close to the Haskell one

[polarit]

The more I read your comments about Haskell or Elm, the less I can resist temptation to visit Haskell homepage
And there I see just this as the first thing on the header page!

primes = filterPrime [2…] where
filterPrime (p:xs) =
p : filterPrime [x | x ← xs, x mod p /= 0]

Well, it looks quite cryptic first.
May even strengthen the feeling that Elm is a toy language only, more or less.
On the other hand, Haskell has surely lots higher learning treshold.
But I am not a heavy-user of any language *), neither a professional developer.
Doing all this, just for fun.

*) I use rather Finnish, Swedish and German languages

[Carsten_Konig]

I really did not want to make the impression that Elm is a toy - it’s a tool and it’s rather specific (creating Web-Apps for a lack of a better word). And that is only my opinion - there are people out there who really go out of their way and use it for way more (backend, …).

Now I’ve come to Elm from Haskell so in a way I am “tainted” - and to make this even worse I studied Math so I’m not only comfortable with all those abstractions some people dislike - I love them and am happy when I can relive those old good memories in my now day-to-day work.

And finally Haskell comes from an academic background so of course it’s filled with “mathy” examples like finding primes. I think the Elm community just don’t go out of there way and explore this space much (some do a bit ever advent of code) - so to me all the algorithmic stuff is much more comfortable in Haskell where pattern matching on lists and the lazy nature lends itself to terse definitions like those you found.

If you like those than I would encourage you to explore Haskell further but if you don’t like those abstractions than Elm surely is a great language to write apps that do “real life” stuff also.

And if you like there is somewhat a in-between those two in PureScript (which I like quite a bit too).

PS: If you like I can try and explain what is going on in the Haskell example - I just don’t want to do that directly as it might be seem to be disrespectful to do this here in the Elm-discourse (I guess I will be seen by many as someone who tries to lure people away anyway )

[polarit]

I fear there are many who think already that continuing on this topic is out of topic.
First of all, I regret I have written anything like Elm being a toy - it certainly isn’t.
In contrary, I appreciate much the work done by Evan Czaplicki and many others.

Would be nice if we could continue discussions on FP generally, Elm, Haskell details, algorithms etc, either with PM or some other open forum. I found you already in LinkedIn but not in FB. Do not fear, I’ll not disturb you too often.

Once, I have used LISP-like Racket language for several months but I was not happy with Racket without web programming. Then I changed to Python3 for longer time. I started first time using Elm already 2019, about one year, then less actively until last year.

P.S. He has forgotten to ask AI about Elm as alternative in FP.

KI-Antwort.de

[Carsten_Konig]

No problem - I’m not on FB or any other big “social media” platform - maybe aside from linkedin but I’m not really active there. Sure ping me there but I cannot promise to react too often (sorry)

I prefer to keep my conversations closer to topics of my interest and sadly Twitter&co quickly escalate in anything but (at least in my experience) - I can say my days got really better since I dropped FB and Twitter.

[polarit]

I have also reduced usage of fb during the last 6 months - max one time a week (earlier every day) and I have never joined to Twitter. That way, more time is left for the more interesting things as programming in Elm.

[veryamusing]

Hi @polarit,

Maybe this helps?

Sieve of Eratosthenes

[polarit]

Thank you @veryamusing !
This is really interesting site.
I tried just the first version, translated from Haskell to Elm, see it live on Ellie .

Pretty fast in fact :
The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Found 78498 primes to 1000000 in 432 milliseconds.

I made a new version showing the primes in the range 2 to 320,000

The primes up to 320 000 are: 2, 3, 5, 7, 11, 13, …,
319901, 319919, 319927, 319931, 319937, 319967, 319973, 319981, 319993.

Found 27608 primes up to 320000 in 113 milliseconds.

[dta]

Because it’s all the rage these days, I decided to ask ChatGPT to write it for me. It did a surprisingly good job. The code looks correct to me, except for using ' in a variable name, and it even understood the surprising (to me) behavior that the upper bound for List.range is inclusive.

@dta

Please write an implementation of the Sieve of Eratosthenes in Elm

@ChatGPT

Sure! Here’s an implementation of the Sieve of Eratosthenes algorithm in Elm:

sieve : Int -> List Int
sieve limit =
    let
        numbers =
            List.range 2 limit

        removeMultiples p ns =
            List.filter (\n -> n % p /= 0) ns

        sieve' ns =
            case ns of
                [] ->
                    []

                p :: rest ->
                    p :: sieve' (removeMultiples p rest)
    in
    sieve' numbers

Here’s an explanation of how this code works:

• The sieve function takes an integer limit and returns a list of prime numbers up to and including limit.
• First, we generate a list of numbers from 2 up to limit.
• Then we define a removeMultiples function, which takes a prime number p and a list of numbers ns and removes all multiples of p from the list.
• The sieve' function is a recursive function that takes a list of numbers ns and applies the removeMultiples function to the first prime number p in the list, then recursively calls itself on the remaining numbers in the list. The base case is when the list is empty, in which case we return the empty list.
• Finally, we call the sieve' function on the list of numbers from 2 up to limit, which gives us a list of prime numbers.

Here’s an example of how you can use this sieve function:

sieve 20 -- returns [2, 3, 5, 7, 11, 13, 17, 19]

[polarit]

Wow, quite impressive, required only a few changes until it works.
The following version may be iported to repl and tested using sieve

1 module AiSieve exposing (sieve)
  2 
  3 sieve : Int -> List Int
  4 sieve limit =
  5     let
  6         numbers =
  7             List.range 2 limit
  8 
  9         removeMultiples p ns =
 10             List.filter (\n -> remainderBy p n /= 0) ns
 11 
 12         siever ns =
 13             case ns of
 14                 [] ->
 15                     []
 16 
 17                 p :: rest ->
 18                     p :: siever (removeMultiples p rest)
 19     in
 20     siever numbers

Testing:

import AiSieve exposing (sieve)
sieve 101
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]

[Carsten_Konig]

just a little meta-hint: if you either add 4 space before each line or (probably easier) if you start your code-blocks with a line of ``` (3 backticks) and end them with a line of 3 backticks also you get those nicely escaped code-blocks here (sadly there seems to be no quick-button in the editor for this )

[polarit]

I have tried earlier a few times that way of 3 ticks ( ```) and it failed always.

For that reson I have saved the code here.

Now it works. Thanks for a good hint.

[polarit]

@dta

Because it’s all the rage these days, I decided to ask ChatGPT to write it for me.

The piece of code looks quite similar as the one earlier in this chain by @Carsten_Konig
Perhaps ChatGPT follows our writings in discourse

No surprise as the similar codes behave in similar way too.
Look at these test results…

> sieve 63409
RangeError: Maximum call stack size exceeded
> 
> sieve 63408
[2,3,5,7,11,13,17,  ...  ,63347,63353,63367,63377,63389,63391,63397]

Thus, the upper working limit is now 63408 .