Skip to content

Instantly share code, notes, and snippets.

@brianberns
Last active February 23, 2021 07:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save brianberns/886e5c8048cfd53ac43deda91512ba2b to your computer and use it in GitHub Desktop.
Save brianberns/886e5c8048cfd53ac43deda91512ba2b to your computer and use it in GitHub Desktop.
Generating an infinite lazy list of primes in F#
open System.Collections
open System.Collections.Generic
type InfiniteLazyList<'T> =
| (::) of ('T * Lazy<InfiniteLazyList<'T>>)
interface IEnumerable<'T> with
member this.GetEnumerator() =
let head :: tail = this
let s =
seq {
yield head
yield! tail.Value :> IEnumerable<_>
}
s.GetEnumerator()
interface IEnumerable with
member this.GetEnumerator() =
(this :> IEnumerable<'T>).GetEnumerator() :> _
module InfiniteLazyList =
let initInfinite initializer =
let rec loop i =
initializer i :: lazy loop (i + 1)
loop 0
let where pred list =
let rec loop (head :: tail) =
if pred head then head :: lazy loop tail.Value
else loop tail.Value
loop list
/// https://literateprograms.org/sieve_of_eratosthenes__haskell_.html
let rec sieve (head :: tail) =
let tail' =
tail.Value
|> InfiniteLazyList.where (fun n ->
n % head > 0)
head :: lazy (sieve tail')
let primes count =
InfiniteLazyList.initInfinite (fun n -> n + 2)
|> sieve
|> Seq.take count
|> Seq.toArray
[<EntryPoint>]
let main argv =
printfn "%A" (primes 100)
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment