无限序列生成过程中删除元素

Question

我找到了一个伟大的haskell解决方案(来源)来生成一个Hofstadter序列

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

现在，我也在尝试用F#编写这样一个解决方案。不幸的是(我不太熟悉F#)，到目前为止我还没有成功。

我的问题是，当我在sequence中使用F#时，似乎不可能删除元素(就像在haskell解决方案中那样)。

允许删除元素的其他数据结构(如arrays、list或set )不是生成无限序列，而是只对某些元素进行操作。

因此，我的问题是:在中，是否有可能生成一个无限序列，其中元素被删除？

到目前为止我尝试过的一些东西：

无限数列：

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

Hofstadter序列-不工作，因为没有del关键字，语法错误也更多

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

我考虑过使用Seq.filter，但也没有找到解决方案。

Answer 1

pad的解决方案不错，但可能由于LazyList的实现方式，堆栈溢出在3-4K数字之间。出于好奇，我编写了一个围绕生成器函数(unit -> 'a)构建的版本，它被反复调用以获得下一个元素(以解决IEnumerable的笨拙)。我得到了第一个10K的数字(还没有试过)。

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

Answer 2

我认为您需要的不仅仅是序列上的delete函数。您的示例需要在inifinite集合上进行模式匹配，而序列不支持这种匹配。

哈斯克尔列表的F#对应者是来自F# PowerPack的LazyList。LazyList也可能是无限的，它支持模式匹配，这有助于您轻松地实现delete。

这里有一个忠实的翻译：

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

这里有一些有趣的事情：

• 使用序列表达式实现delete，以确保函数是尾递归的。非尾递归版本应该很容易。
• 使用BigInteger；如果您不需要太多的元素，那么使用int和Seq.initInfinite更有效。
• 添加一个返回None的案例，以确保详尽的模式匹配。
• 最后将LazyList转换成序列。它提供了更好的与.NET集合的互操作性。

在序列上实现delete更丑陋。如果您有兴趣，请看一看从F#中的序列中删除单个非唯一值，以供参考。

Answer 3

实际上，您可以使用过滤器和遵循haskell解决方案的设计(但是，正如@pad所说，序列上没有模式匹配；所以我使用了lisp风格的销毁)：

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]

不过，我对效率没有任何要求！