Применить функцию к каждому элементу списка - это просто: ###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 Толку от этого, правда, мало. Имеющие более крепкое сцепление с реальностью идут другим путем.
let map_cps f l' =
let rec go l c =
match l with
| [] -> c []
| (x::xs) -> go xs (fun xs' -> c (f x :: xs'))
go l' (fun x -> x)Более реалистичный способ реализации 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Видно, что уверенности в оптимизаторе у автора куда меньше. Разворачивание списка остается на усмотрение программиста.
Комбинированное решение из ocaml-core
###core/lib/core_list.ml
let map_slow l ~f = List.rev (List.rev_map ~f l)
let rec count_map ~f l ctr =
match l with
| [] -> []
| [x1] ->
let f1 = f x1 in
[f1]
| [x1; x2] ->
let f1 = f x1 in
let f2 = f x2 in
[f1; f2]
| [x1; x2; x3] ->
let f1 = f x1 in
let f2 = f x2 in
let f3 = f x3 in
[f1; f2; f3]
| [x1; x2; x3; x4] ->
let f1 = f x1 in
let f2 = f x2 in
let f3 = f x3 in
let f4 = f x4 in
[f1; f2; f3; f4]
| x1 :: x2 :: x3 :: x4 :: x5 :: tl ->
let f1 = f x1 in
let f2 = f x2 in
let f3 = f x3 in
let f4 = f x4 in
let f5 = f x5 in
f1 :: f2 :: f3 :: f4 :: f5 ::
(if ctr > 1000
then map_slow ~f tl
else count_map ~f tl (ctr + 1))
let map l ~f = count_map ~f l 0На этом этапе у нас есть важный результат - работающая функция 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"Спасибо, Жак. Чумовая идея!