在Haskell的问题 - > C＃转换 [英] Questions on a Haskell -> C# conversion

问题描述

背景：

我是拖进看到了这个问题：
的当笔者最初标记为许多其他语言，但后来集中到一个Haskell问题在Haskell 结果
斐波那契数的解析解。不幸的是我有任何哈斯克尔没有经验，所以我真的不能参加的问题。然而 吸引了我的眼球回答者转向何处的答案它变成一个纯粹的整数运算问题。这听起来真棒给我，让我不得不弄清楚它是如何工作的，并比较这对递归斐波那契执行，看看它的准确程度。我有一种感觉，如果我只记得涉及无理数，相关的数学，我也许能安排好一切，我（但我没有）。所以对我来说，第一步是将它移植到我熟悉的语言。在这种情况下，我做的C＃。

我不完全在黑暗幸运。我有另一种功能性语言（OCaml的），所以它的很多看起来有些熟悉，我很多经验。与转换开始了，一切都显得简单，因为它基本上定义了一个新的数值类型来帮助计算。不过，我已经打了一对夫妇在翻译的路障和我有麻烦完成它。 。我得到完全错误的结果。

分析：

下面是我翻译的代码：

 数据EXT =外部！整！整数
推导（EQ，展）
 
实例民外部，其中
 fromInteger一个分机= 0 
否定（分机AB）= EXT（-a）（-b）
（分机AB）+（分机CD）= EXT（A + C）（b + D）
（分机AB）*（分机CD）=分机（A * C + 5 * b * D）（A * D + b * C） - 便于工作在纸上
  - 剩下的不需要的实例方法
 
 FIB N = $分^ twoPhi N  - （2- twoPhi）^ N 
，其中twoPhi =扩展1 1 
除（分机0 b）= b'div` 2 ^ N  -  2 ^ N *开方5 
有效分 

所以，根据我的研究，我可以推断（纠正我，如果我错了任意位置），第一部分宣布键入外部有一个构造函数，将有两个整数参数（我猜将继承式和显示类型/模块）。

接下来是外部实施从<$ C $其中提炼出来 C>民。 fromInteger 执行从整数 A转换。 否定是一元否定和再有就是二进制加法和乘法运算符。

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

问题：

在答案，哈马尔（回答者）提到幂被处理在民默认实现。但是，这意味着什么以及如何实际应用到此类型？是否有一个隐含的一些场说我失踪？难道它只是应用幂它包含每个对应的数字？我认为它确实后者与此C＃代码结束：

<预类=郎-CS prettyprint-覆盖> 公共静态外部运营^（扩展X，INT p）//指数
{
//对面内线的两个部分申请？
返回新EXT（BigInt.Pow（x.a，P），BigInt.Pow（x.b，P））;
// EXT（一^ P）（B ^ P）
}


然而，这与冲突，我是如何看待为什么否定是必要的，如果实际情况，将不再需要它。

---

的代码现在肉。我读的第一部分鸿沟$ twoPhi ^ N - （2- twoPhi）^ N 为：

分以下表达式的结果：twoPhi ^ N - （2- twoPhi）^ N

很简单。募集 twoPhi 到 N 次方。从其余的结果中减去。在这里，我们正在做的二进制减法，但我们只执行一元否定。或者，难道我们没有？或者可以二进制减法暗示，因为它可以弥补组合除了和否定（我们有）？我认为是后者。 ，而这减轻了我对否定的不确定性

---

最后一部分是实际的划分：分（分机0 B ）= b'div` 2 ^ N 。两个问题在这里。从我发现，没有除法运算符，只有`div` 功能。所以，我只需要在这里划分的数字。它是否正确？或者是有一个除法运算符，但是，做别的东西特别的一个单独的`div` 功能？

我不知道如何解释该行的开头。难道仅仅是一个简单的模式匹配？换句话说，如果将第一个参数是一个这仅适用0 ？将结果是什么，如果它不匹配（第一次是非零）？或者我应该将其解释为，我们不关心第一个参数，并无条件地应用功能？这似乎是最大的障碍，它可以使用解释仍然产生不正确的结果。

我没有做任何错误的假设地方？抑或是没事，我只是实现了C＃不正确

代码：

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

<预类=郎-CS prettyprint-覆盖> //代码中删除，以保持后大小下来
//完整的源仍可通过上面的$ b​​ $ b链接

进展：

确定这样看答案和评论到目前为止，我想我知道在哪里可以从这里干吗去了。

乘方只是做它一般不会，乘考虑到我们已经实现了乘法运算 p 时代需要的。它从来没有想到过，我们应该做的数学课一直告诉我们的事情。不必添加和否定隐含的减法是一个非常方便的功能了。

另外我在执行发现一个错字。我说时，我应该已经成倍增加。

<预类=郎-CS prettyprint-覆盖> //（分机AB）*（EXT CD）= EXT（A * C + 5 * b * D）（A * D + b * C）
公共静态外部符*（外部X，外部Y）
{
返回新EXT（XA *雅+ 5 * XB * YB，XA * YB + XB *雅）;
// ^哎呀！
}


结论：

所以现在它的完成。我只实现基本运营，并更名为它一下。命名以类似的方式为复数。到目前为止，与递归实现一致的，即使在真正的大投入。这里是最终的代码

 静态只读复杂TWO_PHI =新的复杂的（1,1）; 
静态BigInt有Fib_x（INT N）
 {
变种X = Complicated.Pow（TWO_PHI，N） -  Complicated.Pow（2  -  TWO_PHI，N）; 
 System.Diagnostics.Debug.Assert（x.Real == 0）; 
返回x.Bogus / BigInt.Pow（2，N）; 
} 
 
结构复杂
 {
私人BigInt有真正的; 
私人BigInt有伪造的; 
 
公共复杂（BigInt有真实的，BigInt有假的）
 {
 this.real =真正的; 
 this.bogus =假; 
} 
公共BigInt有真正的{{返回现实; }} 
公共BigInt有虚假{{返回假的; }} 
 
公共静态复杂的Pow（复杂的价值，诠释指数）
 {
如果（指数℃下）
抛出新的ArgumentException（
唯一的非负指数的支持，
指数）; 
 
复杂的结果= 1; 
复杂系数=价值; 
为（INT面膜=指数;屏蔽= 0;！面膜>> = 1）
 {
如果（（面具和放大器;！为0x1）= 0）
结果* =因素; 
系数* =因素; 
} 
返回结果; 
} 
 
公共静态隐运营商复杂（INT实际）
 {
返回新的复杂（真实的，0）; 
} 
 
公共静态复杂的运营商 - （复杂升，复杂R）
 {
无功实= l.real  -  r.real; 
 VAR虚假= l.bogus  -  r.bogus; 
返回新的复杂（真实的，假的）; 
} 
 
公共静态复杂运算符*（复杂L，复杂的R）
 {
无功实= l.real * r.real + 5 * l.bogus * r.bogus; 
 VAR虚假= l.real * r.bogus + l.bogus * r.real; 
返回新的复杂（真实的，假的）; 
} 
} 
  

和这里的的全面更新源。

解决方案

[...]，第一部分声明了一个构造函数，将有两个整型参数输入分机（我猜将继承EQ和显示类型/模块）。

式和显示是的type类 的。你可以把它们看作类似于C＃的接口，只有更强大。 导出是可用于自动生成标准型类，包括一把实施式，<一个结构code>显示，奥德等。这样可以减少你写的样板的数量。

的

实例民分机部分提供了一个明确的实施民键入类。你有大部分的这部分权利。

[回答者]提到幂是由民​​默认实现处理。但是，这意味着什么以及如何实际应用到此类型？是否有一个隐含的一些场说我失踪？难道它只是应用幂它包含每个对应号码是多少？

这是我的一个有点不清楚。 ^ 不在类型类民，但它完全是在<$ C来定义一个辅助函数$ C>民方法，有点像一个扩展方法。它实现幂通过二进制幂正整数权力。这是代码的主要的猫腻。

[...]我们正在做的二进制减法，但我们只执行一元否定。或者，难道我们没有？或者可以二进制减法暗示，因为它可以由combinding除了和否定（我们有）？

正确的。二进制减去的默认实现 X - Y = X +（否定Y）

。

最后一部分是实际的划分：分（内线0 b）= b'div` 2 ^ N 。两个问题在这里。从我发现，没有除法运算符，只有一个div功能。所以，我只需要在这里划分的数字。它是否正确？或者是有一个除法运算符，但是，做别的东西特别独立的分区功能？

有只有运算符和函数之间的语法差异在Haskell。人们可以通过写它圆括号（+）把运营商作为函数，或在`一段单列写它把一个函数作为一个二元运算符。

DIV 是整数除法，并属于类型类积分，所以它是所有类似于整数类型，包括内部（机大小的整数）和定义整数（任意大小的整数）。

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

这的确只是一个简单的模式匹配，提取的√5系数。的组成部分，是对一个零匹配表达对读者说，我们确实希望它永远是零，使程序崩溃，如果在代码中的一些错误是导致它并非如此。

---

小的改进

更换整数与的Rational 的原代码，你可以写 FIBñ更接近<一个HREF =htt​​p://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression>比奈公式：

  FIB N = divSq5 $披^ N  - （1-PHI）^ N 
，其中divSq5（内线0 b）=分子b 
 =披EXT（1/2​​）（1/2） 
  

这整个计算执行，而不是拯救一切，为年底的分歧。这导致较小的中间号码和20％的增速计算，当 FIB（10 ^ 6）。

Background:

I was "dragged" into seeing this question: Fibonacci's Closed-form expression in Haskell
when the author initially tagged with many other languages but later focused to a Haskell question. Unfortunately I have no experience whatsoever with Haskell so I couldn't really participate in the question. However one of the answers caught my eye where the answerer turned it into a pure integer math problem. That sounded awesome to me so I had to figure out how it worked and compare this to a recursive Fibonacci implementation to see how accurate it was. I have a feeling that if I just remembered the relevant math involving irrational numbers, I might be able to work everything out myself (but I don't). So the first step for me was to port it to a language I am familiar with. In this case, I am doing C#.

I am not completely in the dark fortunately. I have plenty experience in another functional language (OCaml) so a lot of it looked somewhat familiar to me. Starting out with the conversion, everything seemed straightforward since it basically defined a new numeric type to help with the calculations. However I've hit a couple of roadblocks in the translation and am having trouble finishing it. I'm getting completely wrong results.

Analysis:

Here's the code that I'm translating:

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

So based on my research and what I can deduce (correct me if I'm wrong anywhere), the first part declares type Ext with a constructor that will have two Integer parameters (and I guess will inherit the Eq and Show types/modules).

Next is the implementation of Ext which "derives" from Num. fromInteger performs a conversion from an Integer. negate is the unary negation and then there's the binary addition and multiplication operators.

The last part is the actual Fibonacci implementation.

Questions:

In the answer, hammar (the answerer) mentions that exponentiation is handled by the default implementation in Num. But what does that mean and how is that actually applied to this type? Is there an implicit number "field" that I'm missing? Does it just apply the exponentiation to each corresponding number it contains? I assume it does the latter and end up with this C# code:

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)
}

However this conflicts with how I perceive why negate is needed, it wouldn't need it if this actually happens.

---

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

divide the result of the following expression: twoPhi^n - (2-twoPhi)^n.

Pretty simple. Raise twoPhi to the nth power. Subtract from that the result of the rest. Here we're doing binary subtraction but we only implemented unary negation. Or did we not? Or can binary subtraction be implied because it could be made up combining addition and negation (which we have)? I assume the latter. And this eases my uncertainty about the negation.

---

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?

I'm not sure how to interpret the beginning of the line. Is it just a simple pattern match? In other words, would this only apply if the first parameter was a 0? What would the result be if it didn't match (the first was non-zero)? Or should I be interpreting it as we don't care about the first parameter and apply the function unconditionally? This seems to be the biggest hurdle and using either interpretation still yields the incorrect results.

Did I make any wrong assumptions anywhere? Or is it all right and I just implemented the C# incorrectly?

Code:

Here's the (non-working) translation and the full source (including tests) so far just in case anyone is interested.

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

Progress:

Ok so looking at the answers and comments so far, I think I know where to go from here and why.

The exponentiation just needed to do what it normally does, multiply p times given that we've implemented the multiply operation. It never crossed my mind that we should do what math class has always told us to do. The implied subtraction from having addition and negation is a pretty handy feature too.

Also spotted a typo in my implementation. I added when I should have multiplied.

// (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!
}

Conclusion:

So now it's completed. I only implemented to essential operators and renamed it a bit. Named in a similar manner as complex numbers. So far, consistent with the recursive implementation, even at really large inputs. Here's the final code.

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);
    }
}

And here's the fully updated source.

解决方案

[...], the first part declares type Ext with a constructor that will have two Integer parameters (and I guess will inherit the Eq and Show types/modules).

Eq and Show are type classes. You can think of them as similar to interfaces in C#, only more powerful. deriving is a construct that can be used to automatically generate implementations for a handful of standard type classes, including Eq, Show, Ord and others. This reduces the amount of boilerplate you have to write.

The instance Num Ext part provides an explicit implementation of the Num type class. You got most of this part right.

[the answerer] mentions that exponentiation is handled by the default implementation in Num. But what does that mean and how is that actually applied to this type? Is there an implicit number "field" that I'm missing? Does it just apply the exponentiation to each corresponding number it contains?

This was a bit unclear on my part. ^ is not in the type class Num, but it is an auxilliary function defined entirely in terms of the Num methods, sort of like an extension method. It implements exponentiation to positive integral powers through binary exponentiation. This is the main "trick" of the code.

[...] we're doing binary subtraction but we only implemented unary negation. Or did we not? Or can binary subtraction be implied because it could be made up combinding addition and negation (which we have)?

Correct. The default implementation of binary minus is x - y = x + (negate y).

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?

There is only a syntactic difference between operators and functions in Haskell. One can treat an operator as a function by writing it parenthesis (+), or treat a function as a binary operator by writing it in `backticks`.

div is integer division and belongs to the type class Integral, so it is defined for all integer-like types, including Int (machine-sized integers) and Integer (arbitrary-size integers).

I'm not sure how to interpret the beginning of the line. Is it just a simple pattern match? In other words, would this only apply if the first parameter was a 0? What would the result be if it didn't match (the first was non-zero)? Or should I be interpreting it as we don't care about the first parameter and apply the function unconditionally?

It is indeed just a simple pattern match to extract the coefficient of √5. The integral part is matched against a zero to express to readers that we indeed expect it to always be zero, and to make the program crash if some bug in the code was causing it not to be.

---

A small improvement

Replacing Integer with Rational in the original code, you can write fib n even closer to Binet's formula:

fib n = divSq5 $ phi^n - (1-phi)^n
  where divSq5 (Ext 0 b) = numerator b
        phi = Ext (1/2) (1/2)

This performs the divisions throughout the computation, instead of saving it all up for the end. This results in smaller intermediate numbers and about 20% speedup when calculating fib (10^6).

这篇关于在Haskell的问题 - &GT; C＃转换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！