Вопросы по преобразованию Haskell в C #

Предпосылки:

Я был «втянут» в этот вопрос: Выражение в замкнутой форме Фибоначчи в 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 types / модули).

Далее следует реализация 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)
}

Однако это противоречит тому, как я понимаю, почему отрицание необходимо, оно не понадобится, если это действительно произойдет.

Теперь суть кода. Я прочитал первую часть 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);
    }
}

А вот полностью обновленный исходный код .