Removing items while generating an infinite sequence

Question

I found a great haskell solution ( source ) to generate a Hofstadter sequence :

hofstadter = unfoldr (\(r:s:ss) -> Just (r, r+s:delete (r+s) ss)) [1..] 

Now I am also trying to write such a solution in F #. Unfortunately (I'm not very happy with F #), I have not been successful so far.

My problem is that when I use sequence in F #, it seems that I will not be able to delete the element (as is done in the haskell solution).
Other data structures, such as arrays , list or set , which allow you to delete items, do not generate an infinite sequence, but only work with specific items.

So my question is: Is it possible in F # to generate an infinite sequence where the elements are deleted?

Some things I've tried so far:

Infinite sequence of numbers:

 let infinite = Seq.unfold( fun state -> Some( state, state + 1) ) 1 

Hofstadter sequence - does not work because there is no del keyword and there are more syntax errors

 let hofstadter = Seq.unfold( fun (r :: s :: ss) -> Some( r, r+s, del (r+s) ss)) infinite 

I was thinking about using Seq.filter but could not find a solution.

Answer 1

The pad's solution is nice, but probably due to the LazyList implementation, the stack overflows somewhere between 3-4K numbers. For curiosity, I wrote a version built around a generator function ( unit -> 'a ) that is called multiple times to get the next element (to bypass the bulky IEnumerable ). I was able to get the first 10 thousand numbers (I have not tried beyond this).

 let hofstadter() = let delete xf = let found = ref false let rec loop() = let y = f() if not !found && x = y then found := true; loop() else y loop let cons xf = let first = ref true fun () -> if !first then first := false; x else f() let next = let i = ref 0 fun () -> incr i; !i Seq.unfold (fun next -> let r = next() let s = next() Some(r, (cons (r+s) (delete (r+s) next)))) next 

Answer 2

I think you need more than the delete function for the sequence. Your example requires matching patterns in inifinite collections whose sequence is not supported.

F # friend from the Haskell LazyList from F # PowerPack. LazyList is also potentially endless and supports pattern matching, which makes it easy to implement delete .

Here is the correct translation:

 open Microsoft.FSharp.Collections.LazyList let delete x xs = let rec loop x xs = seq { match xs with | Nil -> yield! xs | Cons(x', xs') when x = x' -> yield! xs' | Cons(x', xs') -> yield x' yield! loop x xs' } ofSeq (loop x xs) let hofstadter = 1I |> unfold (fun state -> Some(state, state + 1I)) |> unfold (function | (Cons(r, Cons(s, ss))) -> Some(r, cons (r+s) (delete (r+s) ss)) | _ -> None) |> toSeq 

There are several interesting things here:

• Use a sequence expression to implement delete to ensure that the function is tail recursive. A non-specific recursive version should be simple.
• Use BigInteger ; if you don’t need too many elements, using int and Seq.initInfinite more efficient.
• Add a case returning None to provide a comprehensive pattern matching.
• Finally, I convert LazyList to a sequence. This provides better compatibility with .NET collections.

Implementing delete in a sequence is uglier. If you're interested, look to remove the only non-unique value from the sequence in F # for reference.

Answer 3

In fact, you can use the filter and design that follows the haskell solution (but as @pad says, you don't have pattern matching on sequences, so I used erasing lisp styles):

 let infinite = Seq.initInfinite (fun i -> i+1) let generator = fun ss -> let (r, st) = (Seq.head ss, Seq.skip 1 ss) let (s, stt) = (Seq.head st, Seq.skip 1 st) let srps = seq [ r + s ] let filtered = Seq.filter (fun t -> (r + s) <> t) stt Some (r, Seq.append srps filtered) let hofstadter = Seq.unfold generator infinite let t10 = Seq.take 10 hofstadter |> Seq.toList // val t10 : int list = [1; 3; 7; 12; 18; 26; 35; 45; 56; 69] 

I do not pretend to be effective, though!