ljr - Юра Бронников - Программистское

ljr - Юра Бронников - Программистское

Юра Бронников

[	userinfo	\|	ljr userinfo	]
[	archive	\|	journal archive	]

Программистское	[Jul. 14th, 2003\|12:02 am]
В выходные развлекался чтением диссертации Криса Окасаки (она же, судя по всему, основа книги). Оччень хорошо. И при этом особенно ясно возникает чувство, как много я еще в своей профессии не знаю, и насколько я все-таки больше mister Macho, machine coder, чем человек из computer science. В частности, очень мало я понимаю в ленивых языках и программах. Надо бы найти себе задачку под какой-нибудь Haskell. (Вот еще и в монадах я ничего не понимаю.) И еще: все-таки нет никакого чисто функционального аналога для массивов и, соответственно, для хэш-таблиц. То есть нет структуры-словаря с временем доступа O(1) и временем записи элемента O(1).
Link	Leave a comment

Comments:

From:	mariek@lj
Date:	July 13th, 2003 - 09:08 am

(Link)

Если ты мало понимаешь?!..

(Reply to this) (Thread)

From:	gogabr@lj
Date:	July 14th, 2003 - 01:25 am

(Link)

Видишь ли, мне есть с кем сравнивать.

(Reply to this) (Parent)

From:	mashaaaa@lj
Date:	July 14th, 2003 - 03:45 am

(Link)

Машк, не вмешивайся ты в эти вдохновенные монологи ;->

(Reply to this) (Parent)

From:	frogbot_@lj
Date:	September 7th, 2003 - 08:44 am

(Link)

>И еще: все-таки нет никакого чисто функционального аналога для массивов и, соответственно, для хэш-таблиц. То есть нет структуры-словаря с временем доступа O(1) и временем записи элемента O(1).

Не для всякой хэш-таблицы выборка всегда O(1). Скорее наоборот -- это в случае массива выборка такая, потому как фактически адресная арифметика ;-)

Но вроде как ничего не мешает реализовать O(1) для чтения, даже в чистом функциональном (по-крайней мере на фон-неймановской архитектуре, какой-нибудь ad-hoc в компиляторе). С записью, разумеется не получится, ибо мутабельность. Но если не заморачиваться на чистоте то и запись, например используя ref в ML:

- val x = [ref 0];
> val x = [ref 0] : int ref list

(Reply to this)