немного математики, логики и программирования

[avva]

1. Эта запись о работе со степенными рядами в Хаскеле напомнила мне, почему я влюбился в этот язык, когда изучал его два года назад (увы, с тех пор с ним не работал). Это неверноятно прекрасно - когда можешь определить функции вот так, и оно просто будет работать:

integral fs = 0 : (int1 fs 1) where
    int1 (g:gs) n = g/n : (int1 gs (n+1))

expx = 1 + (integral expx)

sinx = integral cosx
cosx = 1 - (integral sinx)

2. Знаете ли вы, что можно составить сархивированный файл, который разворачивается сам в себя? Ссылка на файл selfgz.gz в этом старом сообщении не работает, но его можно скачать отсюда.

3. Вот эта запись в n-category cafe, и особенно статья, которую она упоминает - очень и очень интересны, но бедный мой мозг, кажется, с ними сейчас не справляется. Сносит крышу.

Comments

[shmel39.livejournal.com]

Интересно. Вот только лично у меня этот фрагмент ругается и сильно материться. Если оставить только функцию integral, то вывод типов порождает следующее:
GHCi, version 6.8.1:
*Main> :t integral
integral :: (Fractional t) => [t] -> [t]

Как мы можем передавать функцию вместо [t]? Если добавить еще и экспоненту, то получаю:

Main.hs:10:7:
    No instance for (Num [t])
      arising from the literal `1' at Main.hs:10:7
    Possible fix: add an instance declaration for (Num [t])
    In the first argument of `(+)', namely `1'
    In the expression: 1 + (integral expx)
    In the definition of `expx': expx = 1 + (integral expx)

Моих знаний Хаскелля не хватает, чтобы разобраться с этим, однако все равно видно, что в int1 первый аргумент разбирается как лист. Попытка изменить expx так, чтобы она возращала лист, хоть и скомпилировалась, но показывает погоду на Марсе. У Вас этот фрагмент кода скомпилировался?

[deni-ok.livejournal.com]

http://swtch.com/powser.hs

[avva.livejournal.com]

Или это, верно.

[shmel39.livejournal.com]

Спасибо, этот код работает.

[avva.livejournal.com]

Да, тут идея в том, что мы представляем фунцкию в виде степенного ряда, и работаем со списком коэффициентов при x^n. Чтобы скомпилировалось, нужно научить Хаскель складывать, умножать и делить такие списки. Посмотрите на код в http://www.cs.dartmouth.edu/~doug/powser1.hs, он должен компилироваться без проблем; определение интеграла (int) там несколько другое, более компактное и возможно менее интуитивное, но можно вместо него подставить определение отсюда.

[shmel39.livejournal.com]

Спасибо. Написать арифметику для списков я не догадался :-))

[ex-tws5249.livejournal.com]

забавно

можно на питоне подобное написать, с генераторами вместо ленивых списков.
получается, правда, не так красиво:

integral = lambda s, c0=0: chain([c0], (c/(n+1.) for n,c in enumerate(s)))

def exp():
    for x in integral(exp(), 1.):
        yield x

[ex-tws5249.livejournal.com]

хотя умножение рядов с одними генераторами уже не получается

[avva.livejournal.com]

ага, что наглядно демонстрирует ограниченность генераторов.

[spamsink.livejournal.com]

2. Интроспективную программу можно написать на любом достаточно мощном языке. Язык Лемпель-Зивовских подстановок, видать, достаточно мощный. :)

1)

[master-nemo.livejournal.com]

ой
что это за страх такой?
для чего-нибудь из фортрана или его друзей?

Re: 1)

[migmit.vox.com (from livejournal.com)]

Ну как же. Просто пишем интегральное уравнение - и оно автоматически решается.

[robel.livejournal.com]

Внимание!! selfgz.gz на Мас не открывать! Уходит в луп!

[avva.livejournal.com]

Это шутка или правда что ли? :)

> Это шутка или правда что ли? :)

[poige.livejournal.com]

Это «и». :-)

$ gzcat selfgz.gz > selfgz
$ uname -mr
8.11.0 Power Macintosh

— работает.

[robel.livejournal.com]

Не шутка. Если открывть в Finder то он начнёт подхватывать разархивированный файл и открывать его.

[aa-kir.livejournal.com]

Про n-category cafe: связь языка тензорных категорий, физики и топологии и правда весьма интересна (и хороша изучена) - а вот логика мне там кажется сильно притянутой за уши.

[avva.livejournal.com]

Они еще не написали как следует про логику - может, будет убедительнее со временем :)

[aa-kir.livejournal.com]

Возможно, но мне сомнительно. Правда, я не профессионал в логике - но зато профессионал в тензорных категориях

[ivan-gandhi.livejournal.com]

Статья эта, конечно, миленькая, но там большая карусель в голове, и сказывается непрофессионализм авторов. Сколько слов о моноидальных категориях, и ни слова ни о Маклейне ни хотя бы о Соловьёве. А связь когерентности в моноидальных категориях с логикой именно они обсуждали. Потом... что там с топосами и семантикой Крипке-Жуаяля? Или это слишком сложно? Без них, по-моему, сложновато будет что-то серьёзное из логики связывать с категориями. Зато масса смешных картинок, не относящихся к делу; а уж Фейнман пристёгнут, имхо, только потому что у него "тоже диаграммы".

Изучать же категории я по-прежнему рекомендую по Categories for the Working Mathematician.

[malaya-zemlya.livejournal.com]

Любители Хаскеля меня не поддержат, но мне казалось, что самое веселое в Computer Science начинается как раз тогда, когда стирается грань между программами и типами данных. Тогда получается, что вычисоения и числа - это одно и тожн, любую вычислимую функцию можно применить к любому аргументу и т п.
Соответственно, вся Розетта схлопывается в точку, что не есть интересно.

[roma.livejournal.com]

про 3: С большой натяжкой можно сказать, что именно это мы это и пытаемся тут понимать (вместо логики "производная алгебраическая геометрия", про которую тоже, наверняка,
в блогах пишут или скоро напишут). Только где там у них в статье содержание? На первый взгляд -- известные общие мутные идеи + куски из учебников?

[avva.livejournal.com]

Да это и должна быть обзорная статья, как я понимаю.

[roma.livejournal.com]

я не к тому, чтобы на них напасть -- от текста скорее польза, чем вред, даже если там много мусора. Просто если бы были некие нетривиальные идеи, подкрепляющие эти параллели и аналогии, то можно было бы на них посмотреть, а так непонятно куда в этом тексте смотреть -- от поверхностного взгляда желание углубляться не возникает,
т.к. кажется, что некуда. Но если есть какое-то конкретное место, в которое можно было бы, то скажи какое, буду всячески благодарен.

[avva.livejournal.com]

Я понимаю. Нет, я не знаю - для меня вообще сами эти параллели и аналогии внове, так что я профан совершенный в этом.

[pawa.livejournal.com]

2. Казалось бы факт существования такого файла легко следует из теоремы о неподвижной точке для любого сжимающего отображения ;)

[avva.livejournal.com]

Архиваторы не всегда сжимают.

[alexcohn.livejournal.com]

... а решать дифференциальные уравнения учиться необязательно, достаточно вместо этого сослаться на теорему существования?

[(Anonymous)]

А откуда известно, что zip (gzip) отображение сжимающее? Для того, чтобы отображение было сжимающим необходимо определить как мы вычисляем расстояние между файлами (т.е. элементами множества). Также необходимо найти такое действительное число q: 0 <= q < 1, что d(zip(x), zip(y)) <= q*d(x, y) для любых файлов x и y, где d(,) - функция расстояния.

[algebraic-brain.livejournal.com]

3. Очень приятно, что кому-то русскоговорящему это тоже интересно :)