Back to Questions
1.9k
views 5
comments
Can lazy evaluation provide an elegant solution to this?
f#
The problem is as follows:

Write a program that generates the following sequence:

a) 1 is in the sequence
b) An element j is in the sequence if and only if j=2n, 3n, or 5n, where n is in the sequence.

At first I thought this could be represented using a clever sequence expression, but then I decided it can't. So next I wrote a recursive function that uses Set.fold_left to add doubles, triples, and quintuples of elements to the set, and a recursion to build the entire sequence. But since there is no laziness involved the function to build the sequence will never terminate. I still haven't fully wrapped my head around the lazy evaluation or use of the y combinator, but my gut tells me they can come in handy here and this can somehow be represented by a seq<'a>. Anyone care to shed some light?

The solution isn't difficult using more complicated methods, but I want to see if there's a two or three liner that can do this elegantly with laziness.

Thanks
.
What's the expected result ?

I had a try as follows, but it's still more awkward than in Haskell or OCaml.

let rec s = seq { yield 1
                  yield! (sn 2) |> combine (sn 3) |> combine (sn 5) }
and sn n = Seq.map (( * ) n) s
and combine sx sy =
  let x, y = Seq.hd sx, Seq.hd sy
  let x, sx, sy =
    if x < y then x, Seq.skip 1 sx, sy
    elif x > y then y, sx, Seq.skip 1 sy
    else x, Seq.skip 1 sx, Seq.skip 1 sy
  seq { yield x
        yield! combine sx sy }


By on 12/10/2008 12:35 PM ()
My direct attempt to solve that problem hangs up fsi after first 10-15 values :( (stack overflow?)

let rec f =
  seq {
    yield 1
    for i in 1..100 do
      if Seq.exists (fun a -> a = i) f then
        yield 2*i
        yield 3*i
        yield 5*i
  }

Seq.take 100 f |> Seq.iter (fun i -> printf "%d " i)


By on 12/11/2008 5:40 AM ()
>> Seq.exists (fun a -> a = i) f

Would this line keep on consuming f ? May be you need a takewhile or something like that.

I believe this is another case where the laziness of haskell fits more nicely. Though brian's solution is pretty much the same, other than the need for guarding empty sequence.

That brings up another interesting point.

In haskell, one can say

combine [] xs = xs

combine xs [] = xs

combine x:xs y:ys = ...

But that needs to be coded into the combine function f# making this kind of 'more guard' less 'declarative' in nature than haskell.

Is this style of coding possible in F# ?
By on 12/11/2008 8:01 PM ()
I have encountered this exact same problem before, years ago when working on FC++, it seems like a pretty famous problem.

Below is one solution, you can probably shorten it even a little more.

#light

let rec combine (LazyList.Cons(h1,t1) as ll1) (LazyList.Cons(h2,t2) as ll2) =
    if h1 = h2 then
        LazyList.consf h1 (fun() -> combine t1 t2)
    elif h1 < h2 then
        LazyList.consf h1 (fun() -> combine t1 ll2)
    else
        LazyList.consf h2 (fun() -> combine t2 ll1)
                    
let rec ll = LazyList.consf 1 (fun() ->
    let twos = LazyList.map (fun n -> 2*n) ll
    let threes = LazyList.map (fun n -> 3*n) ll
    let fives = LazyList.map (fun n -> 5*n) ll
    combine (combine twos threes) fives)

for x in LazyList.take 20 ll do
    printfn "%d" x
By on 12/7/2008 10:56 PM ()
This may be a dumb question, but why do we not have to worry about combine ever being called with an empty list? It seems like you would eventually end up with a MatchFailureException.

Edit: BTW, it actually is a pretty famous problem. read about its history here: [link:en.wikipedia.org]
By on 12/8/2008 6:17 AM ()

    Topic tags

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