F#序列比较

Question

我已按以下方式实现了斐波那契数列生成器

let getNext upperLimit current= 
        let (e1, e2) = current
        let next = e1 + e2
        if next > upperLimit then None
        else Some (next, (e2,next))

let fib upperLimit = (0,1) |> Seq.unfold (getNext upperLimit) |> Seq.append [0;1] 

我的测试代码是

[<Test>]
member Spec.``fib not exeeding 20 should be 0,1,1,2,3,5,8,13``()=
    let expected = seq [0;1;1;2;3;5;8;13] 
    let result = fib 20
    let expectedSameAsResult = (expected = result)
    printfn "Expected: %A  Result: %A result length: %d" expected result (Seq.length result) 
    Assert.That expectedSameAsResult

测试失败，打印出的结果为：

期望值：[0; 1; 1; 2; 3; 5; 8; 13] 结果值：seq [0; 1; 1; 2; ...] 结果长度：8

当我使用for循环打印结果中的每个元素时，我得到了与期望序列完全相同的元素。

那么，期望序列和结果序列之间有什么区别呢？

编辑：我的实现可以在https://github.com/weima/EulerProblems/tree/master/EulerProblems找到。

编辑：回答John Palmer的答案 我只是在F#交互窗口中编写了一个测试。

 let a = seq[1;2;3]
 let b = seq[1;2;3]
 let c = a = b;;

我得到的结果是 val a : seq = [1; 2; 3] val b : seq = [1; 2; 3] val c : bool = true

因此，F#也可以对序列进行结构比较。

根据Gene Belitski的答案进行编辑 我已经将测试更改为

[<Test>]
member Spec.``fib not exeeding 20 should be 0,1,1,2,3,5,8,13``()=
    let expected = seq [0;1;1;2;3;5;8;13] 
    let result = Problem2.fib 20
    let comparedResult =  Seq.compareWith (fun a b -> a - b) expected result  
    let expectedSameAsResult = (comparedResult = 0)
    Assert.That expectedSameAsResult

现在已经可以工作了，谢谢！但我仍然不明白为什么简单的 seq[1;2;3]=seq[1;2;3] 起作用，而我的测试案例却不起作用。

- Wei Ma

---

你受到编译器未按预期执行的影响 - 请尝试 a=(b|> Seq.map id);; - John Palmer

@WeiMa：为了理解发生了什么，请在FSI中尝试一个不同的简单案例，使用真实序列seq {1..3} = seq {1..3} - 这个表达式等于false。 - Gene Belitski

谢谢，大家，我现在明白了。 - Wei Ma

或者使用http://msdn.microsoft.com/en-us/library/bb348567.aspx。 - Mauricio Scheffer

Answer 1

补充John的回答：可以使用Seq.compareWith函数来确定序列的相等性：

let compareSequences = Seq.compareWith Operators.compare

那么序列相等将是表达式的值

let expectedSameAsResult = (compareSequences expected result = 0)

- Gene Belitski

Answer 2

虽然你可能期望 a=b 会比较序列中的元素，但实际上它会计算引用相等性。

你可以通过类似以下的代码来验证：

seq {1..3} = seq {1..3}

这将返回false。

然而，在一些情况下，当你使用常量时，你会得到令人困惑的结果，尤其是

seq [1;2;3] = seq [1;2;3]

返回 true 很容易让人感到困惑。

为避免这个问题，你需要像这样做：

 let test a b = Seq.fold (&&) true (Seq.zip a b |> Seq.map (fun (aa,bb) -> aa=bb))

逐个比较元素。

或者，您可以使用Gene回答中概述的Seq.compareWith。但是，这需要元素还实现了一个比较操作符和相等性，这可能对于某些像代表联合体的实现了=但不是比较的东西来说并非如此。

- John Palmer

---

在他的博客http://blogs.msdn.com/b/dsyme/archive/2009/11/08/equality-and-comparison-constraints-in-f-1-9-7.aspx中，唐·西姆表示f#支持“结构”相等性，我认为比较两个序列属于这一类别。 - Wei Ma

@WeiMa 这对于 list 是正确的，但对于 Seq 不是。 - John Palmer

我认为list和Seq之间的区别在于list具有固定大小，而Seq的大小可能不确定（你如何比较无限序列？）。 - N_A

序列不是通过引用相等性进行比较的。Equals方法通常由=的通用实现使用（这里有一些细微的差别 - 例如，数组被特殊处理）。对于列表，Equals被重写以实现结构相等性，但对于其他类型的序列，实现可能会回退到引用相等性的默认值（或执行其他操作）。 - kvb

Answer 3

MSDN的Operators.seq<'T>函数说：使用序列表达式语法构建序列。 如果你查看它的实现，你会发现它基本上只是一个特殊含义的标识函数，仅当与序列表达式语法一起使用时编译器才能理解。如果你使用列表调用-你将得到相同的列表(向上转换为seq<_>)。

关于结构相等性，根据F#规范：

默认情况下，记录、联合和结构类型定义——称为结构类型——隐式包含编译器生成的声明，用于结构相等性、哈希和比较。这些隐式声明包括以下内容：

override x.GetHashCode() = ...
override x.Equals(y:obj) = ...
interface System.Collections.IStructuralEquatable with 
    member x.Equals(yobj: obj, comparer: System.Collections.IEqualityComparer) = ...
    member x.GetHashCode(comparer: System.IEqualityComparer) = ...

以下声明可实现结构比较：

interface System.IComparable with 
    member x.CompareTo(y:obj) = ...
interface System.Collections.IStructuralComparable with 
    member x.CompareTo(yobj: obj, comparer: System.Collections.IComparer) = ...

对于异常类型，会生成结构相等和哈希的隐式声明，但不会生成结构比较的声明。接口、委托、类或枚举类型永远不会生成隐式声明。通过它们作为整数的基础表示方式，枚举类型隐含地派生了对相等性、哈希和比较的支持。

因此，列表（本质上是联合）支持结构相等，而序列则不支持。您也可以使用 "Seq.forall2" 逐对检查元素。

let isEqual = (s1, s2) ||> Seq.forall2 (=)

- desco

---

Seq.forall2 对于严格的结构相等性并不做你所需要的工作，特别是当这两个序列的长度不相同时。Seq.forall2 (=) [1;2;3] [1;2;3;4] ;; val it : bool = true - Carsten

Answer 4

对于任何想要比较两个序列的人，有一种替代Seq.compareWith的简单方法:

.NET方法Enumerable.SequenceEqual。我在测试时经常使用它。

使用示例：

let sequenceA = seq { 1..5 }
let sequenceB = seq { 1..5 }

Enumerable.SequenceEqual (sequenceA, sequenceB) // True

- Richiban

Answer 5

原因：

序列不支持结构相等。

如果你将seq看作是.NET的IEnumerable<T>，或许会更容易理解？这里seq [1;2;3] = seq [1;2;3]只是一个不幸的巧合。考虑一个非纯的seq：

let rnd = System.Random()
let x = seq { yield rnd.Next() }
printfn "x is %A" x
printfn "x is %A" x

结果：

x is seq [372511654]
x is seq [1026368248]

val rnd : System.Random
val x : seq<int>

明显的答案是：

使用“list”而不是“seq”。

[<Test>]
member Spec.``fib not exeeding 20 should be 0,1,1,2,3,5,8,13``()=
    let expected = [0;1;1;2;3;5;8;13] 
    let result = fib 20 |> Seq.toList
    let expectedSameAsResult = (expected = result)

详情：

请查看其他答案。

- johv