You are viewing lionet

Previous Entry | Next Entry


Иван gliv показал, как он решал задания для #aiclass. На Хаскеле.
$ cat hw2_1.hs 

p("a") = 0.5
p("~a") = 1 - p("a")
p("b|a") = 0.2
p("b|~a") = 0.8

p("b") = p("b|a") * p("a") + p("b|~a") * p("~a") -- = 0.5

p("a|b") = p("b|a") * p("a") / p("b") -- = 0.2

res = p("a|b")

С точки зрения тупого усиления интеллекта, это гениальная вещь в своей простоте. Использовать паттерн-матчинг в качестве механизма макросов. Оценил.

Расскажу тогда, как я таким же крестьянско-пролетарским способом решал лямбда-пазл сами знаете откуда. Для того, чтобы фан не выдавать, приведённый ниже хаскелевый код содержит ошибки.

Итак, имеем .Net экзешник, который в рефлекторе выглядит вот так:


(клик!)

Как это может выглядеть на исходном языке, я даже представить не берусь: мои знания C# заканчиваются на версии ECMA C# 2.0, и этих ваших лямбд там не было, насколько я помню. Но понятно, что примерно семантику этих Func<int,int> можно самым циничным образом угадать: один из аргументов (какой?) является возвращаемым значением, другой(-ие) — входными параметрами.

В итоге, потихоньку читая .Net код в рефлекторе, начал записывать мою интерпретацию в текстовый файл... который сразу оказался в Хаскелевой нотации почему-то. Чисто случайно, так сказать.
b3 n = b4
    where
        b4 f x = f (n f x)

b5 n m = b6
    where
        b6 f x = n f (m f x)

toint n = n b0 0

Написав такое, я понял, что его, наверное, можно просто скомпилировать, и не ошибся. Дописав файл и запустив его в интерпретаторе ghci, получил нужный результат.
main = putStrLn $ "bit.ly/" ++ show num
  where
    f = b2
    f2 = b3
    f3 = b5
    n = f2 $ f2 $ f2 f
    f5 = f2 $ f3 n n 
    f6 = f2 $ f2 $ f3 f5 f5
    f7 = f2 $ f3 f6 f6
    f8 = f2 $ f2 $ f3 f7 f7
    f9 = f2 $ f3 f8 f8
    num = ((((toint(n) * toint(f5)) * toint(f6)) * toint(f7)) * toint(f8)) * toint(f9)

Интересно, как это записывалось изначально в исходниках (C#?) этого .Net экзешника? Неужто также коротко? Или там какой-нибудь Nemerle? Потому что Рефлектор демонстрирует совсем что-то негуманное.

Tags:

Comments

( 42 comments — Leave a comment )
_slw
Oct. 26th, 2011 09:20 am (UTC)
первая часть вызывает ассоциации с байесом, а вторая -- с дозорами.
lionet
Oct. 26th, 2011 09:29 am (UTC)
Будешь смеяться, первая — и есть байес.
si14
Oct. 26th, 2011 01:16 pm (UTC)
Почему смеяться?
antilamer
Oct. 26th, 2011 09:32 am (UTC)
То же самое, только с явными типами. Например, Func<int,Func<int,int>> adder = x => y => x + y;
lionet
Oct. 26th, 2011 09:59 am (UTC)
А-а-а! XML в исходниках!
blackyblack
Oct. 26th, 2011 10:03 am (UTC)
Ха! Лиспер детектед.
antilamer
Oct. 26th, 2011 10:03 am (UTC)
И не говори - еще и невалидный.
jakobz
Oct. 26th, 2011 10:17 am (UTC)
Зачем типы явно? Они выводятся же.
antilamer
Oct. 26th, 2011 10:21 am (UTC)
Вопрос к дизайнерам C# :-| Думаю, из-за inheritance.
jakobz
Oct. 26th, 2011 11:04 am (UTC)
Типы в C# выводятся внутри методов же. Типы полей класса и методов внутри класса нужно указывать явно - это да, но в вышеприведенном примере, в изначальном коде, явно ничего указывать не было не нужно - все это вывелось бы.
antilamer
Oct. 26th, 2011 11:11 am (UTC)
Не внутри методов, а только для объявлений локальных переменных, кроме лямбда-выражений.
jakobz
Oct. 26th, 2011 11:17 am (UTC)
Блин, вру. Не умеет оно выводить тип лямбд при присваивании их к var. Только внутри выражений умеет, гадина.
w00dy
Oct. 26th, 2011 02:11 pm (UTC)
внутри выражений тип лямбд обычно известен, так что для лямбд вывод не работает никак.
antilamer
Oct. 26th, 2011 10:22 am (UTC)
Ну и собственно какой тут тип надо было бы вывести? int,int,int; double,double,double; или string,string,string?
jakobz
Oct. 26th, 2011 11:07 am (UTC)
Где конкретно?
antilamer
Oct. 26th, 2011 11:12 am (UTC)
Func
[Error: Irreparable invalid markup ('<int,func<int,int>') in entry. Owner must fix manually. Raw contents below.]

Func<int,Func<int,int>> adder = x => y => x + y;
jakobz
Oct. 26th, 2011 11:19 am (UTC)
Не умеет, да. Хотя не ясно почему, можно же также как и в хаскеле делать. Думаю специально не сделали - чтобы не выворачивать мозг индусам ошибками вывода типа а-ля хаскель :)
Игорь Петров
Oct. 27th, 2011 08:19 am (UTC)
Да дело тут даже не в этом, если писать (int x) => (int y) => x + y он все равно не выведет тип, потому что не знает, Func это или Expression потому что цитирование в шарпе никак синтаксически не выделяется.
jakobz
Oct. 26th, 2011 10:28 am (UTC)
Кстати мне синтаксис лямбд в C# даже больше по душе:
\() -> 0   <=>  () => 0
\x -> x    <=>  x => x
\x y -> x + y  <=>  (x,y) => x + y


Как по мне палка эта в хаскеле, имитирующая собственно лямбду, создает визуальный шум. Так и хочется постоянно как-нибудь композицию извернуть чтобы ее убрать.
lionet
Oct. 26th, 2011 10:41 am (UTC)
Дополнительная горизонтальная палка (- vs =) тоже шумит.
Игорь Петров
Oct. 27th, 2011 08:24 am (UTC)
> \x y -> x + y <=> (x,y) => x + y

Это неверная трансляция. Синтаксического сахара для каррированных лямбд в шарпе нет (как и в SML, например), так что:

\x y -> x + y <=> x => y => x + y
\(x, y) -> x + y <=> (x, y) => x + y
blackyblack
Oct. 26th, 2011 10:02 am (UTC)
Что-то там задачка на бумажке глупая :)
jakobz
Oct. 26th, 2011 10:21 am (UTC)
А что такое p("blabla")?
lionet
Oct. 26th, 2011 10:27 am (UTC)
Вероятность блаблы.
jakobz
Oct. 26th, 2011 11:37 am (UTC)
А... Это он так переменные с нестандартными названиями заводит. Забавно.
versusvoid
Oct. 26th, 2011 12:35 pm (UTC)
Так исходник этого чуда лежал на каком-то файлообменнике. Собственно первая ссылка, если вбить имя экзешника в google. И вроде как вполне красиво. И чистый C#, кстати.
Ааа, вот и он:
public class Church_numerals_will_help_you______I_hope
{
// Methods
private static void Main()
{
Console.WriteLine("Введите ключ:");
Func
[Error: Irreparable invalid markup ('<func<int,>') in entry. Owner must fix manually. Raw contents below.]

Так исходник этого чуда лежал на каком-то файлообменнике. Собственно первая ссылка, если вбить имя экзешника в google. И вроде как вполне красиво. И чистый C#, кстати.
Ааа, вот и он:
public class Church_numerals_will_help_you______I_hope
{
// Methods
private static void Main()
{
Console.WriteLine("Введите ключ:");
Func<Func<int, int>, int, int> arg = (f, x) => x;
Func<Func<Func<int, int>, int, int>, Func<Func<int, int>, int, int>> func2 = n => (f, x) => f(n(f, x));
Func<Func<Func<int, int>, int, int>, Func<Func<int, int>, int, int>, Func<Func<int, int>, int, int>> func3 = (n, m) => (f, x) => n(f, m(f, x));
Func<Func<int, int>, int, int> func4 = func2(func2(func2(arg)));
Func<Func<int, int>, int, int> func5 = func2(func3(func4, func4));
Func<Func<int, int>, int, int> func6 = func2(func2(func3(func5, func5)));
Func<Func<int, int>, int, int> func7 = func2(func3(func6, func6));
Func<Func<int, int>, int, int> func8 = func2(func2(func3(func7, func7)));
Func<Func<int, int>, int, int> func9 = func2(func3(func8, func8));
int num = ((((ToInt(func4) * ToInt(func5)) * ToInt(func6)) * ToInt(func7)) * ToInt(func8)) * ToInt(func9);
string str = Console.ReadLine();
if (num.ToString() == str)
{
Console.WriteLine("Бинго! http://bit.ly/" + str);
}
else
{
Console.WriteLine("Это не ключ. Настоящий ключ в яйце, яйцо в утке, утка в зайце, заяц в шоке!");
Console.WriteLine("Нужно просто заглянуть внутрь.");
}
}

private static int ToInt(Func<Func<int, int>, int, int> n)
{
return n(x => x + 1, 0);
}
}
lionet
Oct. 26th, 2011 04:14 pm (UTC)
Ну значит, задача была ещё легче, чем казалось, и рефлектор нафиг был не нужен.
si14
Oct. 26th, 2011 01:16 pm (UTC)
Фу как неспортивно хацкелем считать.
demmonoid
Oct. 26th, 2011 02:21 pm (UTC)
Неспортивно Mathematica или Matlab. Даже Octave'ом, если подумать, не очень спортивно.
Удобно, но неспортивно.

А хацкель под такие задачи меньше заточен, плюс сам по себе прокачивает.
si14
Oct. 26th, 2011 02:24 pm (UTC)
Нет, я про другое. Это просто в некотором смысле решение «брутфорсом»; в противовес этому в одном из ответов излагался замечательный способ, которым можно рассчитывать очень легко и быстро (2 test cancer, кажется). Если решать брутфорсом, он не нужен; но если где-то применять, где важна производительность (или считать на бумажке) — нужен.
demmonoid
Oct. 26th, 2011 02:40 pm (UTC)
Если внимательно посмотреть на те таблицы, которые были в 2 test cancer, то можно заметить, что вычисление ровно такое же, просто таблица нагляднее.
Таблицы и другие подобные упрощения хороши, когда уже хорошо понимаешь общий метод. Чтобы не выписывать по сто раз одно и то же.
si14
Oct. 26th, 2011 02:42 pm (UTC)
Да, но мне именно эти таблицы помогли понять, к чему он вообще говорил про «сложно вычисляемый знаменатель» :)
_winnie
Oct. 26th, 2011 01:59 pm (UTC)
В данном случае совсем не видна польза pattern matching, тоже самое получается с хеш-таблицей. От pattern matching можно было бы ожидать пользы в возможности писать c подстановками и в любом порядке, типа p(a|b) = p(a*b) / p(b)
_winnie
Oct. 26th, 2011 02:00 pm (UTC)
хеш-таблица:

p = {}
p["a"] = 0.5
p["~a"] = 1 - p["a"]
p["b|a"] = 0.2
p["b|~a"] = 0.8

p["b"] = p["b|a"] * p["a"] + p["b|~a"] * p["~a"] # = 0.5

p["a|b"] = p["b|a"] * p["a"] / p["b"] # = 0.2

res = p["a|b"]

print res
cp_poster
Oct. 26th, 2011 05:13 pm (UTC)
А можно просто мутабельными переменными посчитать? На любом практически языке.
lionet
Oct. 26th, 2011 05:14 pm (UTC)
Ну конечно. Только выглядеть это ужасно будет:
Pab = Pba * Pa + Pbna * Pna.
d_e_n_o_m
Oct. 26th, 2011 04:08 pm (UTC)
есть вопрос
Что такое b0 и b2

toint n = n b0 0

f = b2

lionet
Oct. 26th, 2011 04:12 pm (UTC)
Re: есть вопрос
b0 и b2 я не привёл, чтобы не давать людям готовое решение головоломки.
vzaliva
Oct. 26th, 2011 04:54 pm (UTC)
Mathematica
Забавно конечно, но это всего лишь приукрашанный калькулятор :) На Математике кстати это работает тоже если заметить круглые скобки на квадратные:

p["a"] = 0.5
p["~a"] = 1 - p["a"]
p["b|a"] = 0.2
p["b|~a"] = 0.8
p["b"] = p["b|a"]*p["a"] + p["b|~a"]*p["~a"]
p["a|b"] = p["b|a"]*p["a"]/p["b"]
res = p["a|b"]

далет 0.2

Гораздно интереснее это делать с символьном виде, например заменив p(a) на неизвестную переменную z:





v_serov
Oct. 28th, 2011 12:57 am (UTC)
числа
Прикольно, в SICP-е про эти "числа" было написано, и у Душкина, надо же как неожиданно, первый раз где-то пригодилось :)
Эта так быстро решилась, предыдущая весь мозг выела, даже стандарт прочитал(по диагонали), пока не понял, что не тем занимаюсь
lionet
Oct. 28th, 2011 05:30 am (UTC)
Re: числа
Так в задаче же не нумералы Чёрча. Это просто название такое.
v_serov
Oct. 28th, 2011 09:56 am (UTC)
Re: числа
А мне кажется именно они, ну во всяком случае что бы решить мне понадобилось только понять что такое func2 и func3 и это становится просто если посмотреть на нумералы. Эх, а название я и не прочитал.
( 42 comments — Leave a comment )