Вопросы по Haskell -> конвертация C#

[...], первая часть объявляет тип Ext с конструктором, который будет иметь два целочисленных параметра (и я предполагаю, что он унаследует типы/модули 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).

Во-первых, 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 также есть оператор /, но он указывает на деление действительных чисел.

Быстрая реализация на 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();
}