Skip to content

Instantly share code, notes, and snippets.

@v-kolesnikov
Forked from klapaucius/_post.md
Created April 17, 2017 10:23
Show Gist options
  • Save v-kolesnikov/5a63afe859f904669ee647ca1c29ad4f to your computer and use it in GitHub Desktop.
Save v-kolesnikov/5a63afe859f904669ee647ca1c29ad4f to your computer and use it in GitHub Desktop.
spine-strict_lists

Строгость и нищета списков.

Map и структурная рекурсия.

Применить функцию к каждому элементу списка - это просто: ###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

Но это скучное решение. Наш рассказ о веселом:

О том, как решать простые задачи сложными способами.

Rube Goldberg machine

Говоря о преимуществах ленивости обычно упоминают о модульности, возможности работы с бесконечными списками и обработки списков, занимая в каждый момент времени меньше памяти, чем занимает весь список. При этом как-то забывают, что даже если оставить за рамками обсуждения удобство использования списка как 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 

Толку от этого, правда, мало. Имеющие более крепкое сцепление с реальностью идут другим путем.

CPS-преобразование.

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"

Спасибо, Жак. Чумовая идея!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment