?

Log in

No account? Create an account

[icon] /^.in$/
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (/me (домен, хотящийся в углу комнаты)).
Missed some entries? Then simply jump to the previous day or the next day.

Tags:
Security:
Subject:О лямбдо-графах. Tying the Knot
Time:01:13 am
Ещё не так давно на фразу:
— На вашей лямбде нельзя представить, например, граф без использования монады IO.
ответить ничего существенного я не мог.

Щас небось напридумываю своей терминологии, поскольку как оно всё по русски будет — я без понятия.

Действительно, казалось бы, что чисто-функциональной (pure) структурой можно представлять только рекурсивные вложенные конструкции типа списков, деревьев и т.п.
Оказывается, что и структуры со сложными связями тоже можно. И без всякого IO. Трюк называется «Tying the Knot».

Пусть мы хотим записать чисто-функциональной структурой граф, представляющий собой квадрат (пронумеруем его вершины индексами от 1 до 4), с двумя дополнительными связями 1-3 и 2-4. Проще говоря, полный граф с четырьмя вершинами.


Рисовал в гимпе от руки, так что ногами не бить.

Тянуть резину не буду. Сразу скажу, что построить такую структуру можно следующим образом:
> -- Параметры конструктора GNode: id узла, [ссылки на другие элементы]
> data GR a = GNode a [GR a]
> 
> buildSquare :: GR Integer
> buildSquare =
>     let node1 = GNode 1 [node4, node2, node3]
>         node2 = GNode 2 [node1, node3, node4]
>         node3 = GNode 3 [node2, node4, node1]
>         node4 = GNode 4 [node3, node1, node2]
>     in node1

В общем, хитрость в том, что мы используем ссылки на объекты, которых ещё нет, но поскольку вычисления ленивы, то всем на это плевать.

Пытаться печатать такой граф напрямую — глупо. Потому вот ещё «умный» обход в глубину:

> toList g = toList' [] g
> toList' alreadySeen (GNode a links)
> | any (==a) alreadySeen = alreadySeen
> | otherwise = foldl (\seen link -> toList' seen link) (a:alreadySeen) links
>
> main = putStrLn $ show $ toList buildSquare


Что меня в этом забавляет, так это то, что такие вычисления нельзя свести к строгим (или я чего-то не понимаю), стоит добавить строгость в какую-нибудь часть определения buildSquare и всё сломается.
Раньше подобные штуки я видел только при рассмотрении свойств свободных теорем (free theorems), которые могут меняться в зависимости от строгости аргументов функции.
withComments $ arr (take 11) >>> delay new

Tags:,
Security:
Subject:Школота наступаэ
Time:10:15 pm
Почему мне периодически какие-то незнакомые люди шлют письма типа «Помоги настроить X в Y», где X — это «vpn», «форвардинг портов», «вай-фай», ... а Y — например, «убунте», «мандриве», «ADSL-модеме» и т.п.?
Нет, ну проблемы у всех и всякие бывают, я всё понимаю, но, блин, почему письма и почему мне?
Ау, всякие списки рассылок там →

Так и прозреваю злобных спамеров, пытающихся оттроллить у меня кусок свободного времени, притворяясь блондинками, настраивающими vpn в мандриве.
withComments $ arr (take 28) >>> delay new

[icon] /^.in$/
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (/me (домен, хотящийся в углу комнаты)).
Missed some entries? Then simply jump to the previous day or the next day.