Вопросы по Haskell → Преобразование С#

Ответ 1

[...], первая часть объявляет тип Ext с конструктором, который будет иметь два параметра Integer (и, я думаю, наследует типы и модули Eq и Show).

Eq и Show являются типами классов. Вы можете считать их похожими на интерфейсы на С#, только более мощными. 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 еще ближе к формулу Binet:

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

Ответ 2

Во-первых, Num, Show, Eq являются типами классов, а не типами или модулями. Они немного похожи на интерфейсы в С#, но решаются статически, а не динамически.

Во-вторых, возведение в степень выполняется путем умножения на реализацию ^, который не является членом класса 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 представляет собой простое целочисленное деление, эквивалентное /, примененное к интегральным типам в С#. Существует также оператор / в Haskell, но он указывает на вещественное деление числа.

Ответ 3

Быстрая реализация на С#. Я реализовал возведение в степень с использованием алгоритма с квадратичным умножением.

Прозрачно сравнить этот тип, имеющий форму a+b*Sqrt(5) с комплексными числами, которые принимают вид a+b*Sqrt(-1). Сложение и вычитание работают одинаково. Умножение немного отличается, потому что я ^ 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();
}