Remove elements during infinite sequence generation

Question

I found a great haskell solution (source) for generating a Hofstadter sequence:

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

Now, I am trying to write such a solution in F#, too. Unfortunately (I am not really familar to F#) I had no success so far.

My problem is, that when I use a sequence in F#, it seems not to be possible to remove an element (like it is done in the haskell solution).
Other data structures like arrays, list or set which allow to remove elements are not generating an infinite sequence, but operate on certain elements, only.

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

Some stuff I tried so far:

Infinite sequence of numbers:

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

Hofstadter sequence - not working, 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 thought about using Seq.filter, but found no solution, either.

Answer 1

I think you need more than a delete function on sequence. Your example requires pattern matching on inifinite collections, which sequence doesn't support.

The F# counterpart of Haskell list is LazyList from F# PowerPack. LazyList is also potentially infinite and it supports pattern matching, which helps you to implement delete easily.

Here is a faithful 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 a few interesting things here:

• Use sequence expression to implement delete to ensure that the function is tail-recursive. A non-tail-recursive version should be easy.
• Use BigInteger; if you don't need too many elements, using int and Seq.initInfinite is more efficient.
• Add a case returning None to ensure exhaustive pattern matching.
• At last I convert LazyList to sequence. It gives better interoperability with .NET collections.

Implementing delete on sequence is uglier. If you are curious, take a look at Remove a single non-unique value from a sequence in F# for reference.

Answer 2

pad's solution is nice but, likely due to the way LazyList is implemented, stack overflows somewhere between 3-4K numbers. For curiosity's sake I wrote a version built around a generator function (unit -> 'a) which is called repeatedly to get the next element (to work around the unwieldiness of IEnumerable). I was able to get the first 10K numbers (haven't tried beyond that).

let hofstadter() =

  let delete x f =
    let found = ref false
    let rec loop() =
      let y = f()
      if not !found && x = y
      then found := true; loop()
      else y
    loop

  let cons x f =
    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