Objective Caml - Суббота, 25 сентября 2010

Objective Caml

ocaml@conference.jabber.ru

Суббота, 25 сентября 2010< ^ >

Конфигурация комнаты

Участники комнаты

GMT+4
[00:18:41] Kakadu вышел(а) из комнаты
[00:22:56] ygrek вышел(а) из комнаты
[01:21:41] gds вышел(а) из комнаты: Replaced by new connection
[01:21:42] gds вошёл(а) в комнату
[01:44:28] Typhon вышел(а) из комнаты
[01:57:51] arhibot вышел(а) из комнаты
[09:55:55] Kakadu вошёл(а) в комнату
[10:47:15] iNode вышел(а) из комнаты
[11:09:37] serp256 вошёл(а) в комнату
[11:28:29] serp256 вышел(а) из комнаты
[11:28:42] serp256 вошёл(а) в комнату
[11:35:32] Typhon вошёл(а) в комнату
[11:45:08] arhibot вошёл(а) в комнату
[11:45:43] arhibot вышел(а) из комнаты
[11:54:56] ygrek вошёл(а) в комнату
[11:55:51] ygrek вышел(а) из комнаты
[11:58:07] Kakadu вышел(а) из комнаты
[11:58:12] Kakadu вошёл(а) в комнату
[11:58:56] serp256 вышел(а) из комнаты
[12:02:42] ygrek вошёл(а) в комнату
[12:09:00] arhibot вошёл(а) в комнату
[12:17:29] serp256 вошёл(а) в комнату
[12:20:06] serp256 вышел(а) из комнаты
[13:13:14] komar вошёл(а) в комнату
[14:13:26] ygrek вышел(а) из комнаты
[14:13:27] ygrek вошёл(а) в комнату
[14:18:00] ygrek вышел(а) из комнаты
[14:18:22] ygrek вошёл(а) в комнату
[15:08:52] Typhon вышел(а) из комнаты
[15:12:46] arhibot вышел(а) из комнаты
[17:24:40] ermine вошёл(а) в комнату
[17:36:39] Kakadu вышел(а) из комнаты
[17:38:31] Kakadu вошёл(а) в комнату
[17:58:07] <Kakadu> Есть задача. В бинарном дереве минимизировать расстояние до листа. Можно это написать с continuationами?
[18:00:03] gds вышел(а) из комнаты: Replaced by new connection
[18:00:05] gds вошёл(а) в комнату
[18:05:58] <ygrek> в смысле минимизировать? переместить этот лист поближе к корню? а зачем здесь continuation'ы?
[18:06:18] <Kakadu> най ти минимальное расстояние до листа
[18:06:57] <Kakadu> я спрашиваю, уместны ли тут continuation'ы?
[18:07:26] <Kakadu> надо реализовать эффективно
[18:07:47] <ygrek> это зависит от того какой алгоритм решения, я не знаю
[18:08:12] <Kakadu> тьфу блин
[18:08:25] <Kakadu> в камле есть глобалные переменные тогда нет проблем
[18:08:44] <Kakadu> препод на хаскеле хотел бы
[18:09:06] <Kakadu> но можно на камле без "глобальных" переменных
[18:09:15] Kakadu несет чушь. наверное
[18:09:51] <Kakadu> я думаю как бы так извратиться чтобы без глобальных переменных. И красиво
[18:17:33] <gds> то есть, дано бинарное дерево и один из его листов, и надо найти расстояние до него, или вообще что?  Я тут совершенно не понял задачу.
[18:21:35] <Kakadu> надо найти расстояния до листов и выбрать минимальное.
[18:23:41] <gds> fold подойдёт?
[18:24:50] <Kakadu> немного сложнее
[18:25:14] <gds> структурная рекурсия проще или ок?
[18:25:17] <Kakadu> если мы нашли расстояние 2, то заходить в поддеревья глубиной болше двух не надо. минимума там не будет
[18:26:31] <Kakadu> при folde мы вроде не сможем так сделать
[18:27:20] <gds> тогда так: пишем функцию, берущую [ленивый] список всех узлов на текущем уровне, и если там лист, возвращаем это значение.
[18:28:58] <Kakadu> и там будет List.concat, который будет переделывать списки и тормозить? я так умею
[18:30:09] <gds> порядок не важен, т.е. можно tail-rec вариант concat'а взять.
хотя можно и подумать (нам обоим).
[18:31:01] <Kakadu> я тут всё думаю насчет continuation'ов
[18:31:31] <Kakadu> может можно нормально осматривать левое поддерево, а правое откладывать на потом в continuation't?
[18:31:59] <gds> имхо тут будет всё равно опуск в левое-глубокое.
[18:32:24] <Kakadu> ну это как повезет и смотря какое дерево
[18:32:46] <Kakadu> или поиск в ширину будет эффективнее в среднем?
[18:33:02] <Kakadu> мне почему то кажется чтоcontinuation'ы эффективнее
[18:35:23] <gds> я слабо представляю подобный поиск через continuations.  Может родил бы что-то подобное zippers, только "в одну сторону".
[18:37:38] <Kakadu> ОК, тогда я не буду извращаться и напишу сам по-простому. Спасибо
[18:40:21] <gds> а как? :]
[18:40:40] <Kakadu> какойнить аккуратный поиск в ширину
[18:45:21] <gds> а как именно?  либо идём "вглупь"(tm) и тратим время, либо идём вширь, и тратим память.
[18:46:06] <Kakadu> второе
[18:46:44] <Kakadu> может забить вообще на этот хаскель-изврат-стайл
[18:47:04] <Kakadu> хотя будет тоже самое почти
[18:47:07] <Kakadu> черт
[18:47:39] <gds> имхо варианта ровно два.  Можно ещё "диагональный" взять, но пофиг.
[19:06:40] ygrek вышел(а) из комнаты
[19:07:00] ygrek вошёл(а) в комнату
[19:07:01] ygrek вышел(а) из комнаты
[19:29:03] ygrek вошёл(а) в комнату
[19:40:38] Typhon вошёл(а) в комнату
[19:57:41] Typhon вышел(а) из комнаты: Replaced by new connection
[19:57:44] Typhon вошёл(а) в комнату
[19:59:49] Typhon вышел(а) из комнаты: Replaced by new connection
[19:59:53] Typhon вошёл(а) в комнату
[20:00:06] Typhon вышел(а) из комнаты
[20:04:25] Typhon вошёл(а) в комнату
[20:07:17] Typhon вышел(а) из комнаты: Replaced by new connection
[20:07:21] Typhon вошёл(а) в комнату
[20:08:35] zert вошёл(а) в комнату
[20:09:59] Typhon вышел(а) из комнаты: Replaced by new connection
[20:10:03] Typhon вошёл(а) в комнату
[20:10:16] Typhon вышел(а) из комнаты
[20:10:37] Typhon вошёл(а) в комнату
[20:11:48] Typhon вышел(а) из комнаты
[20:12:13] Typhon вошёл(а) в комнату
[20:32:27] olegfink вышел(а) из комнаты
[20:49:35] olegfink вошёл(а) в комнату
[21:44:09] ermine вышел(а) из комнаты
[21:50:42] digital_curse вошёл(а) в комнату
[22:06:37] ygrek вышел(а) из комнаты
[22:22:31] Kakadu вышел(а) из комнаты: Replaced by new connection
[22:22:32] Kakadu вошёл(а) в комнату
[22:31:41] serp256 вошёл(а) в комнату
[22:42:44] Kakadu вышел(а) из комнаты
[22:48:12] Kakadu вошёл(а) в комнату
[22:48:39] serp256 вышел(а) из комнаты
[22:58:14] gds вышел(а) из комнаты
[23:03:54] zert вышел(а) из комнаты
[23:04:47] serp256 вошёл(а) в комнату
[23:21:22] serp256 вышел(а) из комнаты
[23:21:29] serp256 вошёл(а) в комнату
[23:35:16] Kakadu вышел(а) из комнаты