在无限序列生成期间删除元素

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其允许除去元件不产生无限序列,但仅在某些元素进行操作.

所以我的问题是:在F#中是否可以生成无限序列,其中元素被删除？

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

无限的数字序列:

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

我认为你需要的不仅仅是delete序列上的一个功能.您的示例需要在无限集合上进行模式匹配,该序列不支持.

Haskell列表的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#中的序列中删除单个非唯一值以供参考.