关于 Haskell 的问题 -> C# 转换

Question

背景：

我被“拖”到看到这个问题： Haskell 中的斐波那契闭式表达式
当作者最初用许多其他语言标记但后来关注 Haskell 问题时。不幸的是，我对 Haskell 没有任何经验，所以我无法真正参与这个问题。然而，答案之一引起了我的注意，回答者转身它变成了一个纯整数数学问题。这对我来说听起来太棒了，所以我必须弄清楚它是如何工作的，并将其与递归斐波那契实现进行比较，看看它有多准确。我有一种感觉，如果我只记住涉及无理数的相关数学，我也许能够自己解决所有问题（但我没有）。所以我的第一步是将其移植到我熟悉的语言。在本例中，我正在执行 C#。

幸运的是我并没有完全蒙在鼓里。我在另一种函数式语言（OCaml）方面拥有丰富的经验，因此其中很多内容对我来说看起来有些熟悉。从转换开始，一切看起来都很简单，因为它基本上定义了一个新的数字类型来帮助计算。然而，我在翻译过程中遇到了一些障碍，无法完成它。我得到完全错误的结果。

分析：

这是我正在翻译的代码：

data Ext = Ext !Integer !Integer
    deriving (Eq, Show)

instance Num Ext where
    fromInteger a = Ext a 0
    negate (Ext a b) = Ext (-a) (-b)
    (Ext a b) + (Ext c d) = Ext (a+c) (b+d)
    (Ext a b) * (Ext c d) = 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 参数（我猜会继承 Eq 和 Show 类型/模块）。

接下来是 Ext 的实现，它“派生”自 Num。 fromInteger 执行从 Integer 的转换。 negate 是一元否定，然后是二元加法和乘法运算符。

最后一部分是斐波那契的实际实现。

问题：

在答案中，hammar（回答者）提到求幂是由 Num 中的默认实现处理的。但这是什么意思？它实际上如何应用于这种类型？我是否缺少隐式数字“字段”？它只是将幂应用于它包含的每个相应数字吗？我假设它执行后者并最终得到此 C# 代码：

public static Ext operator ^(Ext x, int p) // "exponent"
{
    // just apply across both parts of Ext?
    return new Ext(BigInt.Pow(x.a, p), BigInt.Pow(x.b, p));
    //     Ext     (a^p)               (b^p)
}

但这与我理解为什么需要 negate 的方式相冲突，如果实际发生这种情况，它就不需要它。

---

Now the meat of the code. I read the first part divide $ twoPhi^n - (2-twoPhi)^n as:

将以下表达式的结果相除：twoPhi^n - (2-twoPhi)^n。

很简单。将 twoPhi 计算到 n 次方。从中减去其余的结果。这里我们进行二元减法，但只实现一元求反。或者我们没有？或者可以隐含二进制减法，因为它可以由加法和求反（我们有）组合而成？我认为是后者。这减轻了我对否定的不确定性。

---

The last part is the actual division: divide (Ext 0 b) = b `div` 2^n. Two concerns here. From what I've found, there is no division operator, only a `div` function. So I would just have to divide the numbers here. Is this correct? Or is there a division operator but a separate `div` function that does something else special?

我不确定如何解释该行的开头。这只是简单的模式匹配吗？换句话说，这是否仅适用于第一个参数为 0 的情况？如果不匹配（第一个非零）结果会是什么？或者我应该将其解释为我们不关心第一个参数并无条件应用该函数？这似乎是最大的障碍，使用任何一种解释仍然会产生不正确的结果。

我在任何地方做出了错误的假设吗？还是我只是错误地实现了 C#？

代码：

这是（非工作）翻译和完整源（包括测试）到目前为止，以防万一有人感兴趣。

// code removed to keep post size down
// full source still available through link above

进展：

好的，看看到目前为止的答案和评论，我想我知道从这里到哪里去以及为什么。

鉴于我们已经实现了乘法运算，求幂只需执行其通常的操作，即乘以 p 次。我从来没有想过我们应该做数学课上一直告诉我们要做的事情。加法和否定的隐含减法也是一个非常方便的功能。

在我的实现中还发现了一个拼写错误。当我应该乘数的时候我就加了。

// (Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c)
public static Ext operator *(Ext x, Ext y)
{
    return new Ext(x.a * y.a + 5*x.b*y.b, x.a*y.b + x.b*y.a);
    //                 ^ 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 < 0)
            throw new ArgumentException(
                "only non-negative exponents supported",
                "exponent");

        Complicated result = 1;
        Complicated factor = value;
        for (int mask = exponent; mask != 0; mask >>= 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);
    }
}

这是完全更新的源。

Answer 1

[...]，第一部分使用构造函数声明 Ext 类型，该构造函数将具有两个 Integer 参数（我猜将继承 Eq 和 Show 类型/模块）。

Eq 和 Show 是类型类。您可以将它们视为类似于 C# 中的接口，只是更强大。 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 中的运算符和函数之间仅存在语法差异。我们可以通过将运算符写在括号(+) 中将其视为函数，或者将函数写在`反引号` 中将其视为二元运算符。

div 是整数除法，属于类型类 Integral，因此它是为所有类似整数的类型定义的，包括 Int（机器大小）整数）和Integer（任意大小的整数）。

我不知道如何解释该行的开头。这只是简单的模式匹配吗？换句话说，这是否仅适用于第一个参数为 0 的情况？如果不匹配（第一个非零）结果会是什么？或者我应该将其解释为我们不关心第一个参数并无条件应用该函数？

确实只是一个简单的模式匹配来提取√5的系数。整数部分与零匹配，以向读者表达我们确实希望它始终为零，并且如果代码中的某些错误导致它不为零，则使程序崩溃。

---

一个小改进

将原代码中的Integer替换为Rational，您可以将fib n写得更接近比奈公式：

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%。

Answer 2

首先，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
          f x y | 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
          g x y z | even y = g (x * x) (y `quot` 2) z
                  | y == 1 = x * z
                  | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)

这似乎是解决方案中缺少的部分。

关于减法，你是对的。它是通过加法和否定来实现的。

现在，divide 函数仅当 a 等于 0 时才进行除法。否则我们会得到模式匹配失败，表明程序中存在错误。

div 函数是一个简单的整数除法，相当于 C# 中应用于整数类型的 /。 Haskell中还有一个运算符/，但它表示实数除法。

Answer 3

C# 中的快速实现。我使用平方乘算法实现了求幂。

将 a+b*Sqrt(5) 形式的这种类型与 a+b*Sqrt(-1) 形式的复数进行比较是有启发性的。加法和减法的工作原理是一样的。乘法略有不同，因为这里 i^2 不是 -1 而是 +5。除法稍微复杂一些，但也不会太难。

求幂被定义为将一个数与其自身相乘 n 次。但这当然很慢。因此，我们利用 ((a*a)*a)*a 与 (a*a)*(a*a) 相同的事实，并使用平方重写乘法算法。因此，我们只需要 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();
}