4

我找到了一个很棒的 haskell 解决方案（源代码）来生成Hofstadter 序列：

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

现在，我也在尝试用 F# 编写这样的解决方案。不幸的是（我对 F# 不是很熟悉）到目前为止我还没有成功。

我的问题是，当我sequence在 F# 中使用 a 时，似乎无法删除元素（就像在 haskell 解决方案中所做的那样）。
其他数据结构，如arrays, listorset允许删除元素不会生成无限序列，而是仅对某些元素进行操作。

所以我的问题是：在 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，但也没有找到解决方案。

4

3 回答 3

5

我认为您需要的不仅仅是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；如果你不需要太多元素，使用intandSeq.initInfinite效率更高。
  • 添加 case 返回None以确保详尽的模式匹配。
  • 最后我转换LazyList为序列。它提供了与 .NET 集合更好的互操作性。

delete在序列上实现更丑陋。如果您好奇，请查看Remove a single non-unique value from a sequence in F#以供参考。

于 2013-02-15T14:29:40.173 回答
4

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
于 2013-02-15T16:10:23.070 回答
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]

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

于 2013-02-15T15:28:36.133 回答