This does sound like a good candidate for using LazyList.

So long as you have an algorithm for 'compute the <i>next <i>value in the series' (which is what you need to make a LazyList), you should be good to go, then can just treat the list as though it were infinitely populated, but only computes as needed and caches results. Do not use 'seq', it is pretty useless for this.

So long as you have an algorithm for 'compute the <i>next <i>value in the series' (which is what you need to make a LazyList), you should be good to go, then can just treat the list as though it were infinitely populated, but only computes as needed and caches results. Do not use 'seq', it is pretty useless for this.

so let's say I have

Not the best algorithm in the world, but it's short at least for the purposes of illustration.

How can I make a LazyList out of this? I guess the trouble comes from the fact that when I'm specifying the function for the LazyList via consf, it takes a unit and returns a new LazyList. How do I access "the last already computed value"? Also, I assume that any previously computed value will always remain computed correct, so that iterating over it a second time will not force a recomputation?

1 2 3 4 5 6 7

let rec next_prime prev = let is_prime n = let limit = System.Math.Sqrt(float(n)) |> int List.for_all (fun k -> (gcd k n) = 1) [1..limit] let this = prev + (2 - prev%2) if (is_prime this) then this else next_prime this

Not the best algorithm in the world, but it's short at least for the purposes of illustration.

How can I make a LazyList out of this? I guess the trouble comes from the fact that when I'm specifying the function for the LazyList via consf, it takes a unit and returns a new LazyList. How do I access "the last already computed value"? Also, I assume that any previously computed value will always remain computed correct, so that iterating over it a second time will not force a recomputation?

Here's some code to get you started.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#light let NextEven prev = printfn "NextEven %d" prev prev + 2 let rec EvensStartingFrom n = LazyList.consf n (fun () -> EvensStartingFrom (NextEven n)) let evens = EvensStartingFrom 2 let rec WalkPortion n ll = if n > 0 then match ll with | LazyList.Cons(h,t) -> printfn "walked %d" h; WalkPortion (n-1) t | LazyList.Nil -> printfn "reached end" WalkPortion 3 evens WalkPortion 6 evens

Ok based on that I came up with the following:

Is there a way to improve this, or is this pretty much right on? It does output the right sequence of printfs when I walk the list of k's, and never recomputes anything.

Thanks!

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

let rec gcd a b = if (b=0) then a else gcd b (a%b) let next_prime prev = printfn "Calculating prime after %d" prev let rec next_prime prev = let is_prime n = let limit = System.Math.Sqrt(float(n)) |> int List.for_all (fun k -> (gcd k n) = 1) [1..limit] let this = if (prev%2<>1) then (prev+1) else (prev+2) if (is_prime this) then this else next_prime this next_prime prev let next_k prev primes = printfn "Calculating k after %d" prev let rec next_k prev primes = let this = if (prev%2<>1) then (prev+1) else (prev+2) let rec check_all_primes prime_list = match prime_list with | LazyList.Cons(p,next) -> if (p=this) then (p%4=1) else if (p>this) then true else if (this%p=0 && p%4<>1) then false else check_all_primes next | LazyList.Nil -> failwith "Prime sequence ends!" if (check_all_primes primes) then this else next_k this primes next_k prev primes let rec PrimesStartingFrom p = LazyList.consf p (fun () -> PrimesStartingFrom (next_prime p)) let KsStartingFrom k = let primes = PrimesStartingFrom 2 let rec KsStartingFrom k = LazyList.consf k (fun () -> KsStartingFrom (next_k k primes)) KsStartingFrom k let primes = PrimesStartingFrom 2 let ks = KsStartingFrom 1

Is there a way to improve this, or is this pretty much right on? It does output the right sequence of printfs when I walk the list of k's, and never recomputes anything.

Thanks!

I'm getting the hang of it :P

I decided to go ahead and optimize the algorithm, since when testing n for primality it's really stupid to check every single number <= sqrt(n) for divisibility. So the idea was to only check

Is there a way to do this any better, (for that matter is it even correct)?

I decided to go ahead and optimize the algorithm, since when testing n for primality it's really stupid to check every single number <= sqrt(n) for divisibility. So the idea was to only check

*primes*less than or equal to sqrt(n). I struggled over this for a bit because I was dealing with the problem of referencing the list of primes from itself. I came up with a solution but I get tons of warning about recursive references being checked at runtime for soundness. What does this mean, and do I need to worry about it? Also, I feel like the code could be made more elegant. I'm not sure I like the idea of separating out the is_prime, gen_next, and next_prime functions, it seems like they could somehow be declared inline inside the scope of the definition of the original data structure. I did it this way though because like I said, the algorithms needed to know about smaller primes in order to determine if larger numbers are prime, and therefore also to specify the function that generates the tail. So this is what I have: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

let is_prime n primes = let limit = System.Math.Sqrt(float(n)) |> int let rec is_prime primes = match primes with | LazyList.Cons(p,tail) when (p>limit) -> (*printfn "p=%d and limit=%d. Returning true" p limit;*) true | LazyList.Cons(p,tail) -> //printfn "Checking if %d is divisible by prime %d" n p if (n=p) then (*printfn "It's equal to p, so it's prime";*) true else if (n%p=0) then (*printfn "It's divisible, so not prime";*) false else is_prime tail is_prime primes let next_prime_l prev primes = let next = if (prev%2=0) then prev+1 else prev+2 let rec next_prime_l nextcand = //printfn "Checking if %d is prime" nextcand if (is_prime nextcand primes) then //printfn "It is" nextcand else //printfn "It's not, moving on..." next_prime_l (nextcand+2) next_prime_l next let gen_next primes = let rec gen_next tail = match tail with | LazyList.Cons(hd,tl) -> let next = next_prime_l hd primes LazyList.consf next (fun () -> gen_next tl) gen_next primes let rec all_primes = LazyList.consf 2 ( fun() -> gen_next all_primes )

Is there a way to do this any better, (for that matter is it even correct)?

Here's a tighter version, I'm sure you can improve it more.

The warning about initialization soundness is just telling you that it will check for bad programs such as this one:

which tries to evaluate Kaboom inside the definition of Kaboom. 'primes' is similar, except we don't evaluate primes now, we just store it away in a thunk inside the lazy list tail, so it will only be evaluated after the initial value of 'primes' has been set.

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

#light let rec is_prime n = let limit = System.Math.Sqrt(float(n)) |> int let rec is_prime primes = match primes with | LazyList.Cons(p,tail) when (p>limit) -> (*printfn "p=%d and limit=%d. Returning true" p limit;*) true | LazyList.Cons(p,tail) -> //printfn "Checking if %d is divisible by prime %d" n p if (n=p) then (*printfn "It's equal to p, so it's prime";*) true else if (n%p=0) then (*printfn "It's divisible, so not prime";*) false else is_prime tail | _ -> failwith "impossible, primes are infinite list" is_prime primes and next_prime_after n = assert(n%2=1) let candidate = n + 2 //printfn "Checking if %d is prime" candidate if (is_prime candidate) then //printfn "It is" candidate else //printfn "It's not, moving on..." next_prime_after candidate and all_primes_after n = let next = next_prime_after n LazyList.consf next (fun () -> all_primes_after next) and primes = LazyList.consf 2 ( fun() -> LazyList.consf 3 ( fun() -> all_primes_after 3 ) ) primes |> LazyList.take 10 |> Seq.to_list |> printfn "%A"

The warning about initialization soundness is just telling you that it will check for bad programs such as this one:

1 2 3 4

let Call f = f () let rec Kaboom = Call (fun () -> 1 + Kaboom)

which tries to evaluate Kaboom inside the definition of Kaboom. 'primes' is similar, except we don't evaluate primes now, we just store it away in a thunk inside the lazy list tail, so it will only be evaluated after the initial value of 'primes' has been set.

# Topic tags

- f# × 3687
- compiler × 265
- functional × 201
- websharper × 171
- c# × 120
- classes × 97
- web × 96
- book × 84
- .net × 82
- async × 72
- parallel × 43
- server × 43
- parsing × 41
- testing × 41
- asynchronous × 30
- monad × 28
- ocaml × 28
- haskell × 26
- tutorial × 26
- html × 23
- workflows × 22
- linq × 21
- fpish × 19
- introduction × 19
- silverlight × 19
- wpf × 19
- collections × 14
- pipeline × 14
- templates × 12
- monads × 11
- opinion × 10
- reactive × 10
- sitelets × 10
- plugin × 9
- scheme × 9
- solid × 9
- basics × 8
- concurrent × 8
- deployment × 8
- how-to × 8
- javascript × 8
- jquery × 8
- python × 8
- complexity × 7
- lisp × 6
- real-world × 6
- scala × 6
- workshop × 6
- xaml × 6
- conference × 5
- dsl × 5
- java × 5
- metaprogramming × 5
- ml × 5
- piglets × 5
- sitelet × 5
- sql × 5
- visual studio × 5
- formlets × 4
- fsi × 4
- lift × 4
- teaching × 4
- alt.net × 3
- aml × 3
- enhancement × 3
- erlang × 3
- highcharts × 3
- list × 3
- piglet × 3
- reflection × 3
- type provider × 3
- azure × 2
- blog × 2
- clojure × 2
- compilation × 2
- computation expressions × 2
- corporate × 2
- courses × 2
- cufp × 2
- enterprise × 2
- entity framework × 2
- events × 2
- f# interactive × 2
- fsc × 2
- google maps × 2
- hosting × 2
- html5 × 2
- http × 2
- interactive × 2
- interface × 2
- iphone × 2
- iteratee × 2
- jobs × 2
- kendo × 2
- keynote × 2
- mvc × 2
- numeric × 2
- obfuscation × 2
- oop × 2
- packaging × 2
- pattern matching × 2
- performance × 2
- pipelines × 2
- rest × 2
- rx × 2
- script × 2
- seq × 2
- sockets × 2
- stm × 2
- tcp × 2
- trie × 2
- type × 2
- typescript × 2
- ui.next × 2
- xna × 2
- zh × 2
- .net interop × 1
- 2012 × 1
- abstract class × 1
- accumulator × 1
- active pattern × 1
- actor × 1
- addin × 1
- agents × 1
- agile × 1
- alter session × 1
- android × 1
- anonymous object × 1
- appcelerator × 1
- architecture × 1
- array × 1
- arrays × 1
- asp.net 4.5 × 1
- asp.net integration × 1
- asp.net mvc × 1
- asp.net mvc 4 × 1
- asp.net web api × 1
- aspnet × 1
- ast × 1
- b-tree × 1
- badimageformatexception × 1
- batching × 1
- bistro × 1
- bootstrap × 1
- bug × 1
- bundle × 1
- camtasia studio × 1
- canvas × 1
- class × 1
- client × 1
- clojurescript × 1
- closures × 1
- cloud × 1
- cms × 1
- coding diacritics × 1
- color highlighting × 1
- combinator × 1
- confirm × 1
- constructor × 1
- continuation-passing style × 1
- coords × 1
- coursera × 1
- csla × 1
- css × 1
- current_schema × 1
- custom content × 1
- data × 1
- database × 1
- datetime × 1
- declarative × 1
- delete × 1
- dhtmlx × 1
- discriminated union × 1
- disqus × 1
- distance × 1
- docs × 1
- documentation × 1
- dol × 1
- dom × 1
- domain × 1
- du × 1
- duf-101 × 1
- eclipse × 1
- edsl × 1
- em algorithm × 1
- emacs × 1
- emotion × 1
- error × 1
- etw × 1
- euclidean × 1
- event × 1
- example × 1
- examples × 1
- ext js × 1
- extension methods × 1
- extra × 1
- facet pattern × 1
- fantomas × 1
- fear × 1
- float × 1
- flowlet × 1
- fp × 1
- frank × 1
- fsdoc × 1
- fsharp.core × 1
- fsharp.powerpack × 1
- fsharpx × 1
- function × 1
- functional style × 1
- game × 1
- games × 1
- gc × 1
- generic × 1
- geometry × 1
- getlastwin32error × 1
- getting started × 1
- google × 1
- group × 1
- hash × 1
- hello world example × 1
- history × 1
- httpcontext × 1
- https × 1
- hubfs × 1
- ie 8 × 1
- if-doc × 1
- iis 8.0 × 1
- inheritance × 1
- installer × 1
- interfaces × 1
- interpreter × 1
- io × 1
- iobservable × 1
- ios × 1
- ipad × 1
- issue × 1
- jqueryui × 1
- kendochart × 1
- kendoui × 1
- learning × 1
- license × 1
- licensing × 1
- linux × 1
- macro × 1
- macros × 1
- maps × 1
- markerclusterer × 1
- markup × 1
- marshal × 1
- math × 1
- message × 1
- message passing × 1
- message-passing × 1
- metro style × 1
- micro orm × 1
- minimum-requirements × 1
- module × 1
- mono × 1
- msbuild × 1
- multidimensional × 1
- multiline × 1
- multithreading × 1
- mysql × 1
- mysqlclient × 1
- nancy × 1
- native × 1
- nested × 1
- nested loops × 1
- node × 1
- object relation mapper × 1
- object-oriented × 1
- offline × 1
- om × 1
- option × 1
- orm × 1
- osx × 1
- owin × 1
- paper × 1
- parameter × 1
- persistent data structure × 1
- phonegap × 1
- pola × 1
- powerpack × 1
- prefix tree × 1
- principle of least authority × 1
- programming × 1
- project euler × 1
- projekt_feladat × 1
- protected × 1
- provider × 1
- ptvs × 1
- quant × 1
- quotations × 1
- range × 1
- raphael × 1
- razor × 1
- rc × 1
- reactjs × 1
- real-time × 1
- reference × 1
- remote × 1
- remoting × 1
- restful × 1
- round table × 1
- routing × 1
- runtime × 1
- scriptcs × 1
- scripting × 1
- service × 1
- session-state × 1
- sitelet website × 1
- sitlets × 1
- sqlentityconnection × 1
- standards × 1
- stickynotes × 1
- stress × 1
- strong name × 1
- structures × 1
- svg × 1
- targets × 1
- tdd × 1
- template × 1
- text parsing × 1
- time travel × 1
- tracing × 1
- tsunamiide × 1
- type inference × 1
- type providers × 1
- typeprovider × 1
- upload × 1
- url × 1
- vb × 1
- vb.net × 1
- vector × 1
- visal studio × 1
- visual f# × 1
- visual studio 11 × 1
- visual studio 2012 × 1
- visual studio shell × 1
- visualstudio × 1
- web api × 1
- webapi × 1
- webshaper × 1
- websharper f# google × 1
- windows 7 × 1
- windows 8 × 1
- windows-phone × 1
- winrt × 1
- xml × 1
- yield × 1
- zarovizsga × 1

Copyright (c) 2011-2012 IntelliFactory. All rights reserved. Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us |
Built with WebSharper |

I have two sequences. The first is a sequence of all prime numbers.

The second is a sequence of all numbers (not necessarily prime) that satisfy some property which depends on the primes from the first sequence. Specifically, it's a sequence of all numbers that do NOT have a prime factor that is congruent to anything other than 1 mod 4. So, for example, 25 is in the second sequence because 25=5*5, and 5 is congruent to 1 mod 4. 11 is not in the sequence, because 11 is congruent to 3 mod 4, 15 is not in the sequence, because 15=5*3, and even though 5 is congruent to 1 mod 4, 3 is not, and 5525 is in the sequence, because it is equal to 5*5*13*17, all of which are congruent to 1 mod 4.

I actually don't care about the list of primes, they are only there in order to help me determine if a number is in the second sequence. Furthermore, I do not know in advance how many values I will end up needing from the second sequence, and on top of that I definitely don't want to test the same number for primality twice, and I will need to make multiple successively deepening passes over the second sequence, so I don't want to ever compute one of those values more than once either.

Is there an elegant solution to this? I still have trouble thinking "lazily" but it seems like a good candidate.

Also, I'm not too concerned about the algorithms themselves, mostly just how to express the relationship between the two in a way that minimizes recomputation.

Thanks