Created
October 30, 2021 16:28
-
-
Save tkuriyama/5cb269e89c6cfadf3969ea0fbc629aeb to your computer and use it in GitHub Desktop.
Elm Eratosthenes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module Examples.Eratosthenes exposing (..) | |
{-| Sieve of Eratosthenes examples. | |
See <https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf> for further details on the algorithms. | |
-} | |
import Dict | |
import Generator as G | |
-------------------------------------------------------------------------------- | |
{-| Primes by an incremental Sieve of Eratosthenes. | |
The idea is to store the sieve's composite generators in a Dict, and update them just-in-time as more and more candidates are explored. | |
import Generator as G | |
Wheel2Init |> sieve | |
|> G.take 10 | |
--> [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ] | |
wheel2357Init |> sieve | |
|> G.take 10 | |
--> [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ] | |
See section 3 of <https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf> | |
-} | |
type alias SieveState b = | |
( GeneratorDict b, G.Generator Int b ) | |
type alias GeneratorDict b = | |
Dict.Dict Int (List (G.Generator Int b)) | |
sieve : | |
( List Int, Int, G.Generator Int b ) | |
-> G.Generator Int ( SieveState b, List Int ) | |
sieve ( primes, lastPrime, candidateWheel ) = | |
let | |
state0 = | |
( insertNext lastPrime candidateWheel Dict.empty | |
, candidateWheel | |
) | |
in | |
G.prefix primes <| G.init state0 sieveNext | |
sieveNext : SieveState b -> Maybe ( Int, SieveState b ) | |
sieveNext ( map, wheel ) = | |
let | |
( guess, wheel_ ) = | |
safeAdvance1 wheel | |
in | |
case Dict.get guess map of | |
Nothing -> | |
Just | |
( guess, ( insertNext guess wheel_ map, wheel_ ) ) | |
Just composites -> | |
sieveNext | |
( updateMap guess composites map, wheel_ ) | |
insertNext : Int -> G.Generator Int b -> GeneratorDict b -> GeneratorDict b | |
insertNext n generator = | |
Dict.insert | |
(n * n) | |
[ G.map ((*) n) generator ] | |
updateMap : | |
Int | |
-> List (G.Generator Int b) | |
-> GeneratorDict b | |
-> GeneratorDict b | |
updateMap guess compositeGenerators = | |
let | |
reinsert compositeGenerator map_ = | |
safeAdvance1 compositeGenerator |> insertToList map_ | |
in | |
Dict.remove guess | |
>> (\map -> List.foldl reinsert map compositeGenerators) | |
-------------------------------------------------------------------------------- | |
-- Seeds / Candidates | |
wheel2 = | |
G.repeat 2 | |
wheel2Init = | |
( [ 2, 3 ], 3, wheel2 |> G.scanl (+) 3 ) | |
wheel2357 = | |
G.cycle [ 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10 ] | |
wheel2357Init = | |
( [ 2, 3, 5, 7, 11 ], 11, wheel2357 |> G.scanl (+) 11 ) | |
-------------------------------------------------------------------------------- | |
-- Helpers | |
insertToList : | |
Dict.Dict comparable (List v) | |
-> ( comparable, v ) | |
-> Dict.Dict comparable (List v) | |
insertToList map ( key, val ) = | |
case Dict.member key map of | |
False -> | |
Dict.insert key [ val ] map | |
True -> | |
Dict.update key (Maybe.map ((::) val)) map | |
safeAdvance1 : G.Generator Int b -> ( Int, G.Generator Int b ) | |
safeAdvance1 = | |
let | |
unwrap = | |
List.head >> Maybe.withDefault 0 | |
in | |
G.advance 1 >> Tuple.mapFirst unwrap |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment