Infinite lazy list of primes

An infinite lazy list of primes. Not efficient, but elegant and fun.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53:

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 = function
            | 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 = function
    | 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

namespace System

namespace System.Collections

namespace System.Collections.Generic

Multiple items
active recognizer Lazy: Lazy<'T> -> 'T

--------------------
type Lazy<'T> = System.Lazy<'T>

type InfiniteLazyList<'T> =
  | ( :: ) of ('T * Lazy<InfiniteLazyList<'T>>)
    interface IEnumerable
    interface IEnumerable<'T>

Multiple items
type IEnumerable =
  member GetEnumerator : unit -> IEnumerator

--------------------
type IEnumerable<'T> =
  inherit IEnumerable
  member GetEnumerator : unit -> IEnumerator<'T>

val this : InfiniteLazyList<'T>

val head : 'T

val tail : Lazy<InfiniteLazyList<'T>>

val s : seq<'T>

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

--------------------
type seq<'T> = IEnumerable<'T>

property System.Lazy.Value: InfiniteLazyList<'T> with get

IEnumerable.GetEnumerator() : IEnumerator<'T>

val initInfinite : initializer:(int -> 'a) -> InfiniteLazyList<'a>

val initializer : (int -> 'a)

val loop : (int -> InfiniteLazyList<'a>)

val i : int

val where : pred:('a -> bool) -> list:InfiniteLazyList<'a> -> InfiniteLazyList<'a>

val pred : ('a -> bool)

Multiple items
val list : InfiniteLazyList<'a>

--------------------
type 'T list = List<'T>

val loop : (InfiniteLazyList<'a> -> InfiniteLazyList<'a>)

val head : 'a

val tail : Lazy<InfiniteLazyList<'a>>

property System.Lazy.Value: InfiniteLazyList<'a> with get

val sieve : _arg1:InfiniteLazyList<int> -> InfiniteLazyList<int>

https://literateprograms.org/sieve_of_eratosthenes__haskell_.html

val head : int

val tail : Lazy<InfiniteLazyList<int>>

val tail' : InfiniteLazyList<int>

property System.Lazy.Value: InfiniteLazyList<int> with get

Multiple items
module InfiniteLazyList

from Script

--------------------
type InfiniteLazyList<'T> =
  | ( :: ) of ('T * Lazy<InfiniteLazyList<'T>>)
    interface IEnumerable
    interface IEnumerable<'T>

val n : int

val primes : count:int -> int []

val count : int

module Seq

from Microsoft.FSharp.Collections

val take : count:int -> source:seq<'T> -> seq<'T>

val toArray : source:seq<'T> -> 'T []

Multiple items
type EntryPointAttribute =
inherit Attribute
new : unit -> EntryPointAttribute

--------------------
new : unit -> EntryPointAttribute

val main : argv:string [] -> int

val argv : string []

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Raw view Test code New version

More information

Link:	http://fssnip.net/81r
Posted:	3 years ago
Author:	Brian Berns
Tags:	laziness , lazy , prime