Вопросы по конвертации на Haskell -> C#
Фон:
Меня "затянули", увидев этот вопрос: выражение Фибоначчи в замкнутой форме в Хаскеле
когда автор изначально помечал многими другими языками, но позже сосредоточился на вопросе о Хаскеле. К сожалению, у меня нет опыта работы с 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 типы / модули).
Далее идет реализация Ext который "происходит" от Num, fromInteger выполняет преобразование из Integer, negate это унарное отрицание, а затем есть бинарные операторы сложения и умножения.
Последняя часть - это фактическая реализация Фибоначчи.
Вопросы:
В ответе Хаммар (отвечающий) упоминает, что возведение в степень обрабатывается реализацией по умолчанию в 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);
}
}
А вот и полностью обновленный источник.
3 ответа
[...], первая часть объявляет тип 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),
Первый, 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), Сложение и вычитание работают точно так же. Умножение немного отличается, потому что я ^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();
}