Применить функцию к каждому элементу списка — это просто:
GHC/Base.lhs
map _ [] = []
map f (x:xs) = f x : map f xs
Мы можем определить `map` и через правую свертку, но в итоге придем все равно к определению структурно-рекурсивной функции. Такую функцию просто читать, легко писать, можно выводить автоматически для любого алгебраического типа, доказывать корректность по индукции и т.д.
Но есть одна проблема: в случае spine-strict списка такая функция не работает для хоть сколько-нибудь значительной длинны списка. Строгость конструктора по второму аргументу преградила нам простой и естественный путь к цели. Что мы можем противопоставить этому вызову? И, (это, собственно, и является темой этого поста) что противопоставили этому авторы библиотек энергичных функциональных языков?
Игнорирование реальности.
Игнорирование реальности — решение, которое приняли авторы стандартной библиотеки OCaml. Действительно, можно сделать вид, что списки длиннее единиц тысяч элементов не нужны и, как ни в чем не бывало, писать :
std-lib/list.ml
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l
Но это скучное решение. Наш рассказ о веселом:
О том, как решать простые задачи сложными способами.
Говоря о преимуществах ленивости обычно упоминают о модульности, возможности работы с бесконечными списками и обработки списков, занимая в каждый момент времени меньше памяти, чем занимает весь список. При этом как-то забывают, что даже если оставить за рамками обсуждения удобство использования списка как control-structure, то эффективная работа с обыкновенным конечным списком является в энергичных языках нетривиальной проблемой, которая, забегая вперед, для иммутабельных списков и не решается вовсе. Для иллюстрации проблем мы приведем реализации функций `map` в разных библиотеках и на разных языках, объединенных одним свойством — энергичностью по-умолчанию. Нужно заметить, что проблемы эти касаются не только `map`, но и любых других функций для работы со списками за исключением левой свертки и хорошо ложащихся на левую свертку (`reverse`, `length`, `sum` — почти полный их перечень).
Встречаем реальность с открытыми глазами.
Авторы библиотек, поставляющихся с SML/NJ, постеснялись оставлять программиста наедине с холодным безразличием солипсизма. Они продемонстрировали теплоту и заботу, показали, что им не все равно:
init/pervasive.sml
fun map f = let
fun m [] = []
| m [a] = [f a]
| m [a, b] = [f a, f b]
| m [a, b, c] = [f a, f b, f c]
| m (a :: b :: c :: d :: r) = f a :: f b :: f c :: f d :: m r
in
m
end
Толку от этого, правда, мало. Имеющие более крепкое сцепление с реальностью идут другим путем.
Двойной проход.
Более реалистичный способ реализации `map` — это построить развернутый список результатов применения функции левой (хвосторекурсивной) сверткой, а потом развернуть его тем же способом. Такое решение предлагают авторы библиотеки, поставляемой с MLton:
basic/list.sml
fun revMap (l, f) = fold (l, [], fn (x, l) => f x :: l)
fun map (l, f) = rev (revMap (l, f))
`rev_map` есть и в библиотеке OCaml:
std-lib/list.ml
let rev_map f l =
let rec rmap_f accu = function
| [] -> accu
| a::l -> rmap_f (f a :: accu) l
in
rmap_f [] l
Видно, что уверенности в оптимизаторе у автора куда меньше. Разворачивание списка остается на усмотрение программиста.
На этом этапе у нас есть важный результат — работающая функция `map`. Радоваться, впрочем, пока рано — такая реализация делает много лишней работы, а следовательно и работает медленно. Как можно с этим справиться? Ну, чтоб получить результат лучше, у списка нужно переписывать хвост. Просто так взять и сделать односвязный список мутабельным нежелательно. Мы ведь позиционируем его иммутабельность и персистентность как преимущество, верно? Так что мутабельность все-таки следует ограничить.
Волшебные функции.
Некоторые функции равнее других — они, например, находятся с определением списка в одной сборке и имеют доступ к его `protected` полю, как в F#:
FSharp.Core\local.fs
(* optimized mutation-based implementation. This code is only valid in fslib, where mutation of private
tail cons cells is permitted in carefully written library code. *)let inline setFreshConsTail cons t = cons.(::).1 <- t
let inline freshConsNoTail h = h :: (# "ldnull" : 'T list #)
let rec mapToFreshConsTail cons f x =
match x with
| [] ->
setFreshConsTail cons [];
| (h::t) ->
let cons2 = freshConsNoTail (f h)
setFreshConsTail cons cons2;
mapToFreshConsTail cons2 f t
let map f x =
match x with
| [] -> []
| [h] -> [f h]
| (h::t) ->
let cons = freshConsNoTail (f h)
mapToFreshConsTail cons f t
cons
Пример из этой же категории — list comprehensions в Nemerle, которые также переписывают хвост списка за кадром.
Отлично! Теперь у нас есть быстрый `map` и некоторые другие функции для работы со строгими списками. Но есть и проблемы. Дело в том, что такое решение требует поддержки от авторов стандартной библиотеки — стороннему программисту в этой парадигме писать быстрые функции не полагается — нужно довольствоваться тем, что есть. Предполагается, что всем необходимым избранные всех остальных обеспечат. На практике, разумеется, они этого не делают. Напоминаем также, что некоторые разработчики языков и библиотек не собираются обеспечивать вообще ничем. Что остается делать практичному программисту на языке, авторы которого находятся, скажем так, на противоположном конце спектра практичности? Ответ очевиден:
Хак-хак-хак!
Проблемы, не решаемые в рамках правил, часто можно решить выйдя за эти рамки. Так и поступили авторы "Батареек" — альтернативной стандартной библиотеки для OCaml. Нам нужен мутабельный список? Не вопрос, объявляем:
(* Thanks to Jacques Garrigue for suggesting the following structure *)type 'a mut_list = {
hd: 'a;
mutable tl: 'a list
}
Теперь можно писать изменяющий хвост `map`:
batList.ml
let map f = function
| [] -> []
| h :: t ->
let rec loop dst = function
| [] -> ()
| h :: t ->
let r = { hd = f h; tl = [] } in
dst.tl <- inj r;
loop r t
in
let r = { hd = f h; tl = [] } in
loop r t;
inj r
Постойте, функция же возвращает обычный окамловский список. Как это достигается? Интерпретацией памяти, занимаемой мутабельным списком как памяти, занимаемой списком иммутабельным:
external inj : 'a mut_list -> 'a list = "%identity"
Спасибо, Жак. Чумовая идея!
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Но есть одна проблема: в случае spine-strict списка такая функция не работает для хоть сколько-нибудь значительной длинны списка.
Я правильно понимаю, что проблемой является переполнение стека? Но тогда это проблема реализации, а не самого языка, нет?
Здравствуйте, MigMit, Вы писали:
K>>Но есть одна проблема: в случае spine-strict списка такая функция не работает для хоть сколько-нибудь значительной длинны списка.
MM>Я правильно понимаю, что проблемой является переполнение стека? Но тогда это проблема реализации, а не самого языка, нет?
Я не эксперт, но выскажу мнение, чтобы товарищи поправили, если я ошибаюсь.
Насколько я понял, проблема в том, что эффективные алгоритмы применимы только для одного направления односвязного иммутабельного списка. А тип список в языке базовый и может иметь только одно направление (если оставлять ограничение иммутабльности). Хак в том, чтобы использовать мутабельный список интерпретируя его снаружи как иммутабельный.
К сожалению я плохо знаю внутренности окамла и не могу себе представить побочные эффекты такого хака.
Жалко, что подобные хаки невозможно использовать в том же .net.
Степанов обсуждает эту проблему в своих заметках по программированию.
The introduction of move_raw and UNDERLYING_TYPE dismayed many of you. They seemed to contradict common rules of software engineering, allowing us to violate type invariant and put our objects in an unsafe state. And so they do. That, of course, requires an explanation.
There are two main reasons why I choose to ignore commonly accepted software engineering strictures.
The first reason is that the goal of my quest in programming is to combine two seemingly irreconcilable desires:
to write programs in the most general terms, and
to write programs as efficient as the underlying hardware allows.
The desire to write programs in the most general terms forces me to extend my types system to be able to deal with complex data structures (such as fvector_int) as if they were built-in types. I would like to be able to store them in other data structures and use them with standard algorithms such as swap. That requires that certain operations such as copying and assignment preserve certain fundamental invariants.
Preserving invariants is, however, a costly activity. And sometimes I can ignore them if there is a rule that allows me to assure that a sequence of operations restores invariants. It is only acceptable to make a fundamental operation several times slower than it needs to be only to assure that all the intermediate states are valid. What is essential is that the validity is restored at the conclusion of an operation or when an exception occurs.
Здравствуйте, Ziaw, Вы писали:
Z>Здравствуйте, MigMit, Вы писали:
K>>>Но есть одна проблема: в случае spine-strict списка такая функция не работает для хоть сколько-нибудь значительной длинны списка.
MM>>Я правильно понимаю, что проблемой является переполнение стека? Но тогда это проблема реализации, а не самого языка, нет?
Z>Я не эксперт, но выскажу мнение, чтобы товарищи поправили, если я ошибаюсь.
Z>Насколько я понял, проблема в том, что эффективные алгоритмы применимы только для одного направления односвязного иммутабельного списка. А тип список в языке базовый и может иметь только одно направление (если оставлять ограничение иммутабльности). Хак в том, чтобы использовать мутабельный список интерпретируя его снаружи как иммутабельный.
Эффективно можно либо по мутабельным, либо по ленивым.
Z>К сожалению я плохо знаю внутренности окамла и не могу себе представить побочные эффекты такого хака.
Z>Жалко, что подобные хаки невозможно использовать в том же .net.
Можно подменить у объекта typeid в отрицательном смещении, приведется как миленький к чему угодно. Т.е. та же реинтерпретация сработает. unsafe только нужен, и не забывать менять тип обратно. Хак немного злее, чем в native.
Здравствуйте, Klapaucius, Вы писали:
K>Спасибо, Жак. Чумовая идея!
Работает эффективно, стек не съедает, интерфейс имеет кошерный. Пользователь при желании может дописать еще таких функций. Все хорошо. В чем проблема? Или есть идея получше?
Здравствуйте, Klapaucius, Вы писали:
K>Но есть одна проблема: в случае spine-strict списка такая функция не работает для хоть сколько-нибудь значительной длинны списка.
Запустил repl окамла. На списке в 150 000 элементов обычный map работает. Для строгих списков длина значительная, нужно быть очень странным человеком, чтобы хотеть такие объемы обрабатывать в виде строгих списков в памяти.
PS. Ты тоже немерлист чтоле? Где вы все слово "длинна" взяли?
Здравствуйте, D. Mon, Вы писали:
DM>Запустил repl окамла. На списке в 150 000 элементов обычный map работает. Для строгих списков длина значительная, нужно быть очень странным человеком, чтобы хотеть такие объемы обрабатывать в виде строгих списков в памяти.
Для скомпилированной программы лимит берется из настроек OS, в nix системах это легко настраивается,
в win жестко зашивает линкером, так что можно только задать при компиляции вроде.
DM>PS. Ты тоже немерлист чтоле? Где вы все слово "длинна" взяли?
Здравствуйте, D. Mon, Вы писали:
DM>Работает эффективно
Это смотря с чем сравнивать, но да, по сравнению с двойным проходом, например, эффективно.
DM>стек не съедает
Верно.
DM>интерфейс имеет кошерный.
Самый большой недостаток интерфейса — это то, что функция применяется к spine-strict списку и возвращает spine-strict список.
DM>Пользователь при желании может дописать еще таких функций. Все хорошо. В чем проблема?
Виноват, пост я написал длинный. Вы попробуйте перечитать самое начало, а потом сразу перемотать в конец. Тогда, по идее, должны броситься в глаза некоторые проблемы. Например, увеличение кода в 4-6 раз.
DM>Или есть идея получше?
Нет, это лучшее из того, что можно сделать (для строгого списка) — эту идею я, собственно, и собирался донести среди прочих в этом посте.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, D. Mon, Вы писали:
DM>Запустил repl окамла. На списке в 150 000 элементов обычный map работает.
Про это уже FR ответил.
DM>Для строгих списков длина значительная, нужно быть очень странным человеком, чтобы хотеть такие объемы обрабатывать в виде строгих списков в памяти.
Что же страшного в списках, которые обрабатываются за десятки миллисекунд и занимают единицы мегабайт в памяти, позвольте узнать?
DM>Где вы все слово "длинна" взяли?
Спасибо, обязательно исправлю.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Верно, проблема реализации. И?
"И" как бы не факт, что хорошая работа реализации в данном случае должна хоть как-то отражаться в исходном коде библиотек. В частности, подход окамля может быть и вполне разумным.
Здравствуйте, Klapaucius, Вы писали:
K>Самый большой недостаток интерфейса — это то, что функция применяется к spine-strict списку и возвращает spine-strict список.
Раз это недостаток, значит можно лучше? Какой интерфейс для функции map из модуля строгих списков подошел бы лучше?
K>Что же страшного в списках, которые обрабатываются за десятки миллисекунд и занимают единицы мегабайт в памяти, позвольте узнать?
Линейность доступа. Большинство нужных операций имеют неприличную сложность. Во многих случаях вместо строгих списков уместнее Map'ы, Set'ы, массивы и энумераторы (в зависимости от задачи).
Здравствуйте, MigMit, Вы писали:
MM>"И" как бы не факт, что хорошая работа реализации в данном случае должна хоть как-то отражаться в исходном коде библиотек. В частности, подход окамля может быть и вполне разумным.
Вот! Именно такие рассуждения я и назвал "игнорированием реальности". И map из std-lib — закономерный результат такого подхода, когда вместо того, чтоб писать библиотеку для конкретной (и, собственно, единственной) реализации окамла — пишут библиотеку для платоновской идеи реализации окамла, а то, что, скажем так, в тени этой идеи библиотечная функция не работает — ну, это проблема реализации, а не окамла.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, D. Mon, Вы писали:
DM>Раз это недостаток, значит можно лучше?
К сожалению, если что-то — недостаток, то это не всегда означает, что можно лучше.
DM>Какой интерфейс для функции map из модуля строгих списков подошел бы лучше?
По вашему, если выбор ограничен одним вариантом — т.е. его и нет вовсе — это означает, что этот единственный вариант и недостатком быть не может?
DM>Линейность доступа. Большинство нужных операций имеют неприличную сложность. Во многих случаях вместо строгих списков уместнее Map'ы, Set'ы, массивы и энумераторы (в зависимости от задачи).
Ну вот, уже доступ к n-му элементу появился. А если такой доступ не нужен или осуществляется однократно, например? Вы ведь взялись, как я понял, обосновывать ненужность списков больше того, для которого map из std-lib еще в стек умещается. А это задача сложная — тут такими отговорками не отделаться.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Не знал, что под виндовс ocamlopt можно размер стека указать. Думал только каким-нибудь editbin /stack:размер потом править (сам так не делал).
Ну ocamlopt линковкой не занимается, это делает в последних версиях flexlink.exe, но он тоже в свою очередь
вызывает линкер в зависимости от сборки или от VC или от Mingw/Cygwin, которые умеют задавать размеры стека.
Здравствуйте, Klapaucius, Вы писали:
K>К сожалению, если что-то — недостаток, то это не всегда означает, что можно лучше. K>По вашему, если выбор ограничен одним вариантом — т.е. его и нет вовсе — это означает, что этот единственный вариант и недостатком быть не может?
Ну, мне кажется странным считать фактически определение недостатком. Это как считать недостатком бита то, что у него всего два возможных значения.
DM>>Линейность доступа. Большинство нужных операций имеют неприличную сложность. Во многих случаях вместо строгих списков уместнее Map'ы, Set'ы, массивы и энумераторы (в зависимости от задачи).
K>Ну вот, уже доступ к n-му элементу появился. А если такой доступ не нужен или осуществляется однократно, например? Вы ведь взялись, как я понял, обосновывать ненужность списков больше того, для которого map из std-lib еще в стек умещается. А это задача сложная — тут такими отговорками не отделаться.
Ничего сложного. Если человек в качестве структуры для ста тыщ данных выбирает строгий список, это значит он не планирует ни обращаться к n-ному элементу, ни искать нужные элементы, ни брать куски этих данных, ни объединять несколько таких структур в одну, ни добавлять что-либо в конец или середину, ни удалять элементы из любых мест кроме начала. Ну т.е. вообще ничего практически не собирается делать. Это очень странный человек и довольно редкая ситуация. Обычно какие-то из этих операций все же нужны, а тогда использовать списки уже нет смысла, есть более подходящие структуры.
Есть одно хорошо подходящее для таких списков применение — стеки. А кроме них, что еще?
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, MigMit, Вы писали:
MM>>"И" как бы не факт, что хорошая работа реализации в данном случае должна хоть как-то отражаться в исходном коде библиотек. В частности, подход окамля может быть и вполне разумным.
K>Вот! Именно такие рассуждения я и назвал "игнорированием реальности". И map из std-lib — закономерный результат такого подхода, когда вместо того, чтоб писать библиотеку для конкретной (и, собственно, единственной) реализации окамла — пишут библиотеку для платоновской идеи реализации окамла, а то, что, скажем так, в тени этой идеи библиотечная функция не работает — ну, это проблема реализации, а не окамла.
Всё это было бы правильно, если бы речь шла о внешней библиотеке. Но стандартная библиотека обычно пишется примерно теми же людьми, которые пишут компилятор. И посему имеют возможность изменить и РЕАЛИЗАЦИЮ ТОЖЕ.
Собственно, а не сделано ли это уже? У меня нет сейчас на машине окамля, и я не хочу его ставить специально для этого, но, может быть, там таки не переполняется стек?
Здравствуйте, MigMit, Вы писали:
MM>Собственно, а не сделано ли это уже? У меня нет сейчас на машине окамля, и я не хочу его ставить специально для этого, но, может быть, там таки не переполняется стек?
Стандартная List.map таки стек переполняет. На 200К элементах уже.
Но поскольку на практике все используют расширенные стандартные библиотеки (батарейки, extLib, core..), в которых функции над списками все хвостаторекурсивные, то проблема не особо актуальна. Разве что для критиков-теоретиков.
