关于Haskell的问题 – > C＃转换
背景：
我被“拖累”看到这个问题： Fibonacci在Haskell中的封闭式表达式
当作者最初用许多其他语言标记但后来专注于Haskell问题时。 不幸的是，我对Haskell没有任何经验，所以我无法真正参与这个问题。 然而，其中一个答案引起了我的注意，回答者把它变成了一个纯整数学问题。 这对我来说听起来很棒 ，所以我必须弄清楚它是如何工作的，并将其与递归的Fibonacci实现进行比较，以了解它的准确性。 我有一种感觉，如果我只记得涉及非理性数字的相关数学，我可能能够自己解决所有问题（但我没有）。 因此，我的第一步是将其移植到我熟悉的语言中。 在这种情况下，我正在做C＃。
幸运的是，我并没有完全处于黑暗中。 我在另一种函数式语言（OCaml）方面有很多经验，所以很多看起来对我来说都很熟悉。 从转换开始，一切看起来都很简单，因为它基本上定义了一个新的数字类型来帮助计算。 然而，我在翻译中遇到了几个障碍，但我在完成翻译时遇到了麻烦。 我的结果完全错了。
分析：
这是我正在翻译的代码：
data Ext = Ext !Integer !Integer deriving (Eq, Show) instance Num Ext where fromInteger a = Ext a 0 negate (Ext ab) = Ext (-a) (-b) (Ext ab) + (Ext cd) = Ext (a+c) (b+d) (Ext ab) * (Ext cd) = Ext (a*c + 5*b*d) (a*d + b*c) -- easy to work out on paper -- remaining instance methods are not needed fib n = divide $ twoPhi^n - (2-twoPhi)^n where twoPhi = Ext 1 1 divide (Ext 0 b) = b `div` 2^n -- effectively divides by 2^n * sqrt 5 所以基于我的研究以及我可以推断出的内容（如果我在任何地方都错了，请纠正我），第一部分使用一个构造函数声明类型Ext ，该构造函数将具有两个Integer参数（我想将inheritanceEq和Show类型/模块） 。
接下来是从Num “派生”的Ext的实现。 fromInteger从Integer执行转换。 negate是一元否定，然后是二元加法和乘法运算符。
最后一部分是实际的Fibonacci实现。
问题：
在答案中，hammar（回答者）提到取幂是由Num的默认实现处理的。 但是这意味着什么？这实际上是如何应用于这种类型的呢？ 我缺少一个隐含数字“字段”吗？ 它是否只对它包含的每个相应数字应用取幂？ 我假设它执行后者并最终得到这个C＃代码：
public static Ext operator ^(Ext x, int p) // "exponent" { // just apply across both parts of Ext? return new Ext(BigInt.Pow(xa, p), BigInt.Pow(xb, p)); // Ext (a^p) (b^p) }
然而，这与我如何理解为什么需要negate相冲突，如果实际发生这种情况就不需要它。
现在是代码的肉。 我读第一部分divide $ twoPhi^n - (2-twoPhi)^n为：
除以下表达式的结果：twoPhi ^ n – （2-twoPhi）^ n。
很简单。 将twoPhi提升到n次幂。 从中减去其余的结果。 这里我们正在进行二元减法，但我们只实现了一元否定。 或者我们不是吗？ 或者可以暗示二元减法，因为它可以组合加法和否定（我们有）？ 我假设后者。 这减轻了我对否定的不确定性。
最后一部分是实际除法： divide (Ext 0 b) = b `div` 2^n 。 这里有两个问题。 根据我的发现，没有除法运算符，只有`div`函数。 所以我只需要在这里划分数字。 它是否正确？ 或者是否有一个除法运算符，但是有一个单独的`div`函数可以执行其他特殊操作？
我不知道如何解释线的开头。 它只是一个简单的模式匹配？ 换句话说，这只适用于第一个参数为0吗？ 如果它不匹配（第一个非零），结果会是什么？ 或者我应该解释它，因为我们不关心第一个参数并无条件地应用函数？ 这似乎是最大的障碍，使用任何一种解释仍会产生不正确的结果。
我在任何地方做过任何错误的假设吗？ 或者它没事，我只是错误地实现了C＃？
码：
到目前为止，这是（非工作）翻译和 完整来源 （包括测试），以防任何人感兴趣。
// code removed to keep post size down // full source still available through link above
进展：
好的，看看目前为止的答案和评论，我想我知道从这里去哪里以及为什么。
指数刚才需要做它通常做的事情，在我们实现乘法运算的情况下乘以p倍。 从来没有想到我们应该做数学课一直告诉我们要做的事情。 具有加法和否定的隐含减法也是非常方便的特征。
在我的实现中也发现了一个拼写错误。 我添加的时候我应该成倍增加。
// (Ext ab) * (Ext cd) = Ext (a*c + 5*b*d) (a*d + b*c) public static Ext operator *(Ext x, Ext y) { return new Ext(xa * ya + 5*xb*yb, xa*yb + xb*ya); // ^ oops! }
结论：
所以现在它已经完成了。 我只对必要的运算符实现并重命名了一下。 以与复数相似的方式命名。 到目前为止，与递归实现一致，即使在非常大的输入。 这是最终的代码。
static readonly Complicated TWO_PHI = new Complicated(1, 1); static BigInt Fib_x(int n) { var x = Complicated.Pow(TWO_PHI, n) - Complicated.Pow(2 - TWO_PHI, n); System.Diagnostics.Debug.Assert(x.Real == 0); return x.Bogus / BigInt.Pow(2, n); } struct Complicated { private BigInt real; private BigInt bogus; public Complicated(BigInt real, BigInt bogus) { this.real = real; this.bogus = bogus; } public BigInt Real { get { return real; } } public BigInt Bogus { get { return bogus; } } public static Complicated Pow(Complicated value, int exponent) { if (exponent >= 1) { if ((mask & 0x1) != 0) result *= factor; factor *= factor; } return result; } public static implicit operator Complicated(int real) { return new Complicated(real, 0); } public static Complicated operator -(Complicated l, Complicated r) { var real = l.real - r.real; var bogus = l.bogus - r.bogus; return new Complicated(real, bogus); } public static Complicated operator *(Complicated l, Complicated r) { var real = l.real * r.real + 5 * l.bogus * r.bogus; var bogus = l.real * r.bogus + l.bogus * r.real; return new Complicated(real, bogus); } }
这是完全更新的来源 。
[…]，第一部分使用一个构造函数声明类型Ext，该构造函数将具有两个Integer参数（我想将inheritanceEq和Show类型/模块）。
Eq和Show是类型类 。 您可以将它们视为与C＃中的接口类似，但function更强大。 deriving是一个构造，可用于自动生成少数标准类型类的实现，包括Eq ， Show ， Ord等。 这减少了您必须编写的样板数量。
instance Num Ext部分提供Num类型类的显式实现。 你完成了这部分的大部分内容。
[回答者]提到取幂是由Num中的默认实现处理的。 但是这意味着什么？这实际上是如何应用于这种类型的呢？ 我缺少一个隐含数字“字段”吗？ 它是否只对它包含的每个相应数字应用取幂？
这对我来说有点不清楚。 ^不在类型类Num ，但它是完全根据Num方法定义的辅助函数，有点像扩展方法。 它通过二进制求幂实现对正整数幂的取幂 。 这是代码的主要“技巧”。
[…]我们正在进行二元减法，但我们只实现了一元否定。 或者我们不是吗？ 或者可以隐含二元减法，因为它可以组合加法和否定（我们有）？
正确。 二进制减号的默认实现是x - y = x + (negate y) 。
最后一部分是实际除法：
divide (Ext 0 b) = b `div` 2^n。 这里有两个问题。 从我发现的，没有除法运算符，只有div函数。 所以我只需要在这里划分数字。 它是否正确？ 或者是否有一个除法运算符，但是有一个单独的div函数可以执行其他特殊操作
Haskell中的运算符和函数之间只有语法差异。 可以通过将运算符写成括号(+)来将运算符视为函数，或者通过将函数写入`backticks`将函数视为二元运算符。
div是整数除法，属于类型类Integral ，因此它定义为所有类似整数的类型，包括Int （机器大小的整数）和Integer （任意大小的整数）。
我不知道如何解释线的开头。 它只是一个简单的模式匹配？ 换句话说，这只适用于第一个参数为0的情况吗？ 如果它不匹配（第一个非零），结果会是什么？ 或者我应该解释它，因为我们不关心第一个参数并无条件地应用函数？
确实只是一个简单的模式匹配来提取√5的系数。 整数部分与零匹配，以向读者表达我们确实期望它始终为零，并且如果代码中的某些错误导致程序不存在则使程序崩溃。
一点点改进
在原始代码中用Rational替换Integer ，你可以写得更接近Binet的公式 ：
fib n = divSq5 $ phi^n - (1-phi)^n where divSq5 (Ext 0 b) = numerator b phi = Ext (1/2) (1/2)
这将在整个计算过程中执行除法，而不是将其全部保存到最后。 当计算fib (10^6)时，这导致较小的中间数和约20％的加速。
首先， Num ， Show ， Eq是类型类，不是类型，也不是模块。 它们与C＃中的接口有点类似，但是静态解析而不是动态解析。
其次，取幂是通过与^的实现相乘来执行的， ^不是Num类型类的成员，而是一个单独的函数。
实施如下：
(^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 < 0 = error "Negative exponent" | y0 == 0 = 1 | otherwise = f x0 y0 where -- f : x0 ^ y0 = x ^ y fxy | even y = f (x * x) (y `quot` 2) | y == 1 = x | otherwise = g (x * x) ((y - 1) `quot` 2) x -- g : x0 ^ y0 = (x ^ y) * z gxyz | even y = g (x * x) (y `quot` 2) z | y == 1 = x * z | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)
这似乎是解决方案中缺失的部分。
你是正确的减法。 它通过添加和否定来实现。
现在，除非函数除以等于0，否则divide函数除以。否则我们得到模式匹配失败，表示程序中存在错误。
div函数是一个简单的整数除法，相当于/应用于C＃中的整数类型。 在Haskell中还有一个operator / ，但它表示实数除法。
在C＃中快速实现。 我使用square-and-multiply算法实现了取幂。
将具有formsa+b*Sqrt(5)这种类型与forms为a+b*Sqrt(-1)的复数进行比较是有启发性的。 加法和减法的工作方式相同。 乘法略有不同，因为i ^ 2不是-1而是+5。 分区稍微复杂一些，但也不应该太难。
指数定义为将数字与其自身相乘n次。 但当然这很慢。 因此我们使用((a*a)*a)*a与(a*a)*(a*a)并使用square-and-multiply算法重写的事实。 所以我们只需要log(n)乘法而不是n乘法。
只计算单个组件的指数不起作用。 那是因为你的类型下面的矩阵不是对角线。 将其与复数的属性进行比较。 您不能简单地分别计算实部和虚部的指数。
struct MyNumber { public readonly BigInteger Real; public readonly BigInteger Sqrt5; public MyNumber(BigInteger real,BigInteger sqrt5) { Real=real; Sqrt5=sqrt5; } public static MyNumber operator -(MyNumber left,MyNumber right) { return new MyNumber(left.Real-right.Real, left.Sqrt5-right.Sqrt5); } public static MyNumber operator*(MyNumber left,MyNumber right) { BigInteger real=left.Real*right.Real + left.Sqrt5*right.Sqrt5*5; BigInteger sqrt5=left.Real*right.Sqrt5 + right.Real*left.Sqrt5; return new MyNumber(real,sqrt5); } public static MyNumber Power(MyNumber b,int exponent) { if(!(exponent>=0)) throw new ArgumentException(); MyNumber result=new MyNumber(1,0); MyNumber multiplier=b; while(exponent!=0) { if((exponent&1)==1)//exponent is odd result*=multiplier; multiplier=multiplier*multiplier; exponent/=2; } return result; } public override string ToString() { return Real.ToString()+"+"+Sqrt5.ToString()+"*Sqrt(5)"; } } BigInteger Fibo(int n) { MyNumber num = MyNumber.Power(new MyNumber(1,1),n)-MyNumber.Power(new MyNumber(1,-1),n); num.Dump(); if(num.Real!=0) throw new Exception("Asser failed"); return num.Sqrt5/BigInteger.Pow(2,n); } void Main() { MyNumber num=new MyNumber(1,2); MyNumber.Power(num,2).Dump(); Fibo(5).Dump(); }