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

Question

背景:

我被"拖累"看到这个问题: 当作者最初用许多其他语言标记但后来专注于Haskell问题时,Fibonacci在Haskell中的Closed-form表达式
.不幸的是,我对Haskell没有任何经验,所以我无法真正参与这个问题.然而,其中一个答案引起了我的注意,应答者把它变成了纯整数学问题.这对我来说听起来很棒,所以我必须弄清楚它是如何工作的,并将其与递归的Fibonacci实现进行比较,以了解它的准确性.我有一种感觉,如果我只记得涉及非理性数字的相关数学,我可能能够自己解决所有问题(但我没有).因此,对我而言,第一步是将其移植到我熟悉的语言中.在这种情况下,我正在做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是一元否定,然后是二元加法和乘法运算符.

最后一部分是实际的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(x.a, p), BigInt.Pow(x.b, 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 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中的运算符和函数之间只有语法差异.可以通过编写括号将操作符视为函数(+),或者通过写入函数将函数视为二元运算符`backticks`.

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)

这将在整个计算过程中执行除法,而不是将其全部保存到最后.这导致较小的中间数和计算时的约20%的加速fib (10^6).

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中还有一个运算符,但它表示实数除法.