Обновляемая версия с красивой подсветкой кода.

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

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

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

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

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

В блоге Jane Street тоже пишут про оптимизацию map, если кому интересно.
Суть вкратце — используем не-хвосторекурсивную версию на коротких списках, и переключаемся на хвосторекурсивную на больших.

Ок, уговорили, давайте сравним эти нищие неэффективные списки окамла и богатые, крутые и эффективные ленивые списки хаскеля.

Вот такой код:

import Data.List
import Data.Bits
 
qsort [] = []
qsort (x:xs) = qsort ys ++ x : qsort zs where (ys, zs) = partition (< x) xs

main = print . show $ (head res + last res) where
  res = reverse $ qsort lst 
  lst :: [Int]
  lst = [mod ((x .&. 65535) * 12343) 100000 | x <- [0..1999999]]

open ExtLib

let rec qsort = function
  | [] -> []
  | x::xs ->  let ys, zs = List.partition ((>) x) xs in (qsort ys) @ (x :: (qsort zs));;
 
let lst = List.init 2000000 (fun x-> (x land 65535) * 12343 mod 100000) in
let res = List.rev (qsort lst) in
print_int (List.hd res + List.last res)

Ноут 2 ГГц с Вистой, GHC 6.12.1, OCaml 3.10.2.
Haskell (с ключом -O2): 11.86 c
Ocaml (c ключом -inline 99): 8.98 c

Здравствуйте, Klapaucius, Вы писали:

K>Это "совершенствование реализации" нужно для устранения промежуточных списков. На работоспособности map — основной теме разговора это никак не сказывается.

мне казалось, что ты критиковал производительность ленивых списков тоже?

K>Функционал соотвествующий коду правил перезаписи и промежуточных функций для них в окамловской библиотеке вовсе отсутствует, так что и сравнивать не с чем.

это не отменяет того факта, что ghc добирался до нынешней произхводительности списков два десятка лет и нынешняя скорость обусловлена не мифическими достоинствами хаскела, а громадной работой над компилятором и библиотекой. но почему-то специальный фреймворк аж в 12 строк, заменяющий стандартные строки в окамле, ты считаешь огромной проблемой, а куда более навороченный фреймворк, на разработке которого люди пишут целые научные статьи, в хаскеле ты не замечаешь

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Klapaucius, Вы писали:


K>>Если вам факт не нравится — это еще не означает, что это абсурд. Это, разумеется, благоприятный случай для хаскеля (не для всех функций фьюжн хорошо работает), и он, в какой-то степени специально подобран — точно как и код из этого сообщения

Автор: D. Mon
Дата: 03.12.11

, вот только максимально благоприятный для окамла случай как-то отрывом не впечатляет.

FR>

>>time -p ./orig_tst
FR>false
FR>real 23.33
FR>user 20.54
FR>sys 2.64
>>Exit code: 0

>>time -p ./loop_tst
FR>false
FR>real 3.59
FR>user 3.56
FR>sys 0.01
>>Exit code: 0
FR>

K>>Не бывает никакого ленивого ФП. Бывают идиомы ФП и языки в которых поддерживается больше или меньше таких идиом. Ну и разное качество поддержки, разумеется.

FR>В теории да, на практике нет.

Забей спорить с этими фанатиками Там в хаскеле 7.0.3 тупо нету никакого списка. Компилятор (а не рантайм) тупо список [1..n] с цикл преобразует. Тоже мне рокет саенс. А ghc 6.12.3, где он этого не умеет, хаскель примерно на 25% медленнее.

P.S. Фанатикам хаскеля. В окамле нету такой оптимизации. Но если надо, я там вместо ленивого списка [1..n] я могу написать тупой императивный for и не париться по поводу, есть ли в компиляторе для меня подобная оптимизация или нету.

Здравствуйте, FR, Вы писали:

FR>Тут полный форум вопросов о том почему хаскель жрет память и тормозит

Это только в воображении уязвленных окамлистов. А если закрыть глаза, выровнять дыхание, сосчитать до ста и снова посмотреть на форум — морок развеется.

Здравствуйте, Klapaucius, Вы писали:

K>Но причина, по которой тема не взволновала джавистов, в общем, понятна. Им односвязные списки действительно не нужны — они без них как-то обходятся, в отличие от окамлистов, которым списки не нужны только в этом треде, а в реальности они их используют.

Окамлистам списки разумного размера нужны, они их используют (и я среди них). И все работает.
А неразумное применение списков и хаскеллистам не нужно:

иначе я бы и для 10к элементов не стал бы его использовать

— писал

Автор: BulatZiganshin
Дата: 03.12.11

выше Булат.
Хватит уже бред-то пороть про окамлистов и ненужность, сколько можно.

Здравствуйте, BulatZiganshin, Вы писали:

DM>>Ок, уговорили, давайте сравним эти нищие неэффективные списки окамла и богатые, крутые и эффективные ленивые списки хаскеля.

BZ>речь гла ведь о том, что ленивые списки в окамле очень тормозные, а энергичные — ограничены размером стёка

В первом же посте показано, что при использовании расширенных библиотек не ограничены.

DM>>Haskell (с ключом -O2): 11.86 c
DM>>Ocaml (c ключом -inline 99): 8.98 c

BZ>я правильно понял, что ленивые списки хаскела практически не отличаются по скорости от энергичных окамла???

В принципе, да. GHC из Haskell Platform 2010 с множеством оптимизаций и параллельным сборщиком мусора уже не очень сильно отстает от ocamlopt начала 2008 года с минимумом оптимизаций и полностью однопоточным рантаймом/сборщиком.

BZ>ты ниже на массивах скорость привёл, интересно ещё скорость сишной реализации

Это ты хорошо спросил, там совсем прикол:

#include "stdafx.h"
#include <vector>
#include <algorithm>

int _tmain(int argc, _TCHAR* argv[])
{
    const int N = 2000000;
    std::vector<int> arr(N);
    for(int x=0;x<N;x++)
        arr[x] = (x & 65535) * 12343 % 100000;
    std::sort(arr.begin(), arr.end());
    std::vector<int> res(arr.rbegin(), arr.rend());
    printf("%d ", res[0] + res[N-1]);
    return 0;
}

MSVC2005: 0.32 c.
Пока не знаю, почему такая огромная разница. Возможно, совсем разная сортировка, хотя по идее везде должен быть quicksort. Посмотрел на асм, никаких SSE не использовалось, простые and, mul, idiv. Смешно, конечно. А говоришь не баловство.

Здравствуйте, D. Mon, Вы писали:

BZ>>с точки зрения фанатика фортрана странным выглядит человек, вообще использующий рекурсию. подумай об этом

DM>Эта демагогия не изменит характеристик сложности алгоритмов над списками и не оправдает такой безответсвенный выбор структуры. Не, я понимаю, что в хаскеле много готовых функций для работы с ними, и использовать списки везде удобно. Просто не надо думать, что это удобство бесплатно и всегда оправдано.

забавно. меня сбило с толку то, что ты активно работаешь с различными ФЯП, но видимо для тебя это всё заведомое баловство, а практичным ты считаешь только свой рабочий инструмент — окамл. отсюда и все конструкции, выходящие за его парадигму — и даже реализацию! — воспринимаются тобой как неэффективные и следовательно вредные

так вот, "эта демагогия" известна как Blub Paradox. когда ты пишешь в своём блоге о том, что ленивые списки не нужны из-за своей неэффективности — ты демонстрируешь как раз этот эффект. на самом деле это отличный инструмент, потому что 90% прикладной программы вообще не нуждается в скорости работы и то, что они будут на ленивых списках вместо обычных — на скорости никак не скажется

в данном же топике я ведь ясно написал, что список, хоть и может содержать миллионы элементов, не использует операции, которые медленней чем на массивах — иначе я бы и для 10к элементов не стал бы его использовать. ограничение в 100к элементов, после которого ты считаешь неверным использовать списки — связано именно с проблемами окамловского рантайма, а не тем, что именно до этой границы можно терпеть O(n^2) алгоритмы

поэтому я написал, что создатель рантайма (не ты), который заявляет что его пользователь, использующий с O(n) операциями списки в миллион элементов — "странный человек", лукавит так же, как программист, который сделал архиватор и потом объявляет странным своего пользователя, если тот имеет больше 100к файлов. надо уметь сознаться, что проблема всё же в твоём рантайме, а не в пользователе, который "хочет странного"

Здравствуйте, D. Mon, Вы писали:

DM>И специально для считающих, что сортировка списков и массивов стоит одинаково:

Не выдумывайте — никто так не считает.

DM>2.53 с

Неожиданный поворот.

import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as Intro
import Data.Bits

main = do
        let arr = V.generate 2000000 (\x -> mod ((x .&. 65535) * 12343) 100000)
        let arr' = V.modify Intro.sort $ arr
        let res = V.reverse arr' 
        print $ res V.! 0 + res V.! (V.length res - 1)

Работает за 0,347 сек.
Это я еще не стал массив на месте сортировать, как вы, а копирую лишний раз.
Ваш код работает 1,788 сек.
GHC у меня 7.0.3, LLVM 2.9, а ocamlopt 3.13 (из репозитория, августовский, кажется) Оба x32.

Здравствуйте, Klapaucius, Вы писали:

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

Работает эффективно, стек не съедает, интерфейс имеет кошерный. Пользователь при желании может дописать еще таких функций. Все хорошо. В чем проблема? Или есть идея получше?

Здравствуйте, Klapaucius, Вы писали:

K>Но есть одна проблема: в случае spine-strict списка такая функция не работает для хоть сколько-нибудь значительной длинны списка.

Запустил repl окамла. На списке в 150 000 элементов обычный map работает. Для строгих списков длина значительная, нужно быть очень странным человеком, чтобы хотеть такие объемы обрабатывать в виде строгих списков в памяти.

PS. Ты тоже немерлист чтоле? Где вы все слово "длинна" взяли?

Здравствуйте, MigMit, Вы писали:

MM>Собственно, а не сделано ли это уже? У меня нет сейчас на машине окамля, и я не хочу его ставить специально для этого, но, может быть, там таки не переполняется стек?

Стандартная List.map таки стек переполняет. На 200К элементах уже.
Но поскольку на практике все используют расширенные стандартные библиотеки (батарейки, extLib, core..), в которых функции над списками все хвостаторекурсивные, то проблема не особо актуальна. Разве что для критиков-теоретиков.

Здравствуйте, D. Mon, Вы писали:

DM>Ненене, Дэвид Блейн. Это ты выбрал список в качестве способа хранения инфы про файлы, так что странным человеком быть тебе.

с точки зрения фанатика фортрана странным выглядит человек, вообще использующий рекурсию. подумай об этом

Здравствуйте, BulatZiganshin, Вы писали:

BZ>в хаскеле они не быстрее.

О, в хаскеле они намного быстрее.

BZ>помню, побайтовое чтение файла получалось раз в 70 медленнее поблочного

Были бы списки окамловские — получилось бы в 700 раз. Это не шутка, почитайте тесты в треде на который я ссылался.

Здравствуйте, FR, Вы писали:

FR>в win жестко зашивает линкером, так что можно только задать при компиляции вроде.

Это значение используется лишь как умолчание для процесса.
При ручном создании нити можно задать размер стека. Это очень странно, что они не протащили эту настройку.

Здравствуйте, D. Mon, Вы писали:

DM>Эта демагогия не изменит характеристик сложности алгоритмов над списками и не оправдает такой безответсвенный выбор структуры. Не, я понимаю, что в хаскеле много готовых функций для работы с ними, и использовать списки везде удобно. Просто не надо думать, что это удобство бесплатно и всегда оправдано.

Есть какая-то принципиальная разница между списком и любым другим рекурсивным типом данных (то, что написал Klapaucius справедливо для всех рекурсивных типов, а не только для списков) или вы считаете использование рекурсивных типов — безответственным?

Здравствуйте, D. Mon, Вы писали:

DM>2.53 с
DM>Разница более 3 раз.

я лично уверен, что можно сделать гораздо быстрее, чем на ленивых списках ghc. вот тут говорят, что ghc-шная быстрая сортировка массивов оказалась всего вдвое медленней сишной

а "Разница более 3 раз" неинформативно. ты взял библиотечную реализацию, так что дело может быть в чём угодно — лучше алгоритм, оптимизация, использование деталей реализации

Здравствуйте, BulatZiganshin, Вы писали:

BZ>речь гла ведь о том, что ленивые списки в окамле очень тормозные, а энергичные — ограничены размером стёка

Энергичные в окамле не чем не ограничены (кроме как размером памяти вообще как и везде), ограничены многие ФВП
их обрабатывающие из стандартной библиотеки они переполняют стек.
Но реально мало кто из-за убогости использует только стандартную библиотеку окамла. В альтернативных например
в батарейках (практически аналог буста из C++ по позиционированию) таких ограничений нет.

Здравствуйте, D. Mon, Вы писали:


DM>Пока не знаю, почему такая огромная разница. Возможно, совсем разная сортировка, хотя по идее везде должен быть quicksort. Посмотрел на асм, никаких SSE не использовалось, простые and, mul, idiv. Смешно, конечно. А говоришь не баловство.

Тут уже явно занятие фигней, std::sort не обязан быть quicksort, там бывает и несколько разных сортировок сразу.

Здравствуйте, MigMit, Вы писали:

MM>Так речь, вроде, шла о том, что SML/NJ использует не обычный стек. А для чего ещё делать такую оптимизацию — я не особо понимаю.

В SML/NJ не обычный стек, чтобы реализовать первоклассные продолжения. Там есть callcc.

Здравствуйте, Klapaucius, Вы писали:

K>Еще раз напоминаю, что проблема не решена, потому что...
K>

K>Обсуждаемая проблема заключается не в том, что используется нехвосторекурсивный map. Он, разумеется, не используется, потому как использовать его нельзя. Проблема заключается в том, что вместо структурно-рекурсивной функции нужно писать хвосторекурсивную, а вместо двух строк — 12.

В том то и дело что писать обычно не нужно, такие функции все-таки большей частью должны быть библиотечными.
Так что по моему если нам скажем дан библиотекой тип данных и все базовые ФВП которые его обслуживают, то
проблема возможно и не полностью но решена. Пример тот же Enum из батареек.

Здравствуйте, D. Mon, Вы писали:

DM>Сравнивать эффективность разных структуры данных на примере реализаций в разных языках мало смысла.

Смысла в этом достаточно. Сравнивая реализации структур данных, области применения которых пересекаются для разных языков мы сравниваем языки — только и всего. Или в сравнивании языков тоже смысла нет?

DM>А то так можно и на реболе каком-нибудь реализовать структуру, а потом говорить о ее неэффективности.

О ее неэффективности в реболе. И делать какие-то выводы из сравнения ребола и других языков.

DM>Я говорю, что когда список используется в качестве стека, для него не нужен map, а если это не так, то прошу привести примеры.

Но ведь все обсуждаемые тут реализации map используют список в качестве стека. Берут с вершины, убирают с вершины, кладут на вершину — ни в каком ином качестве они список не используют. Всякий раз, когда вы применяете map к списку — вы используете список в качестве стека. Вы же сами и пишете о том, что использовать список в другом качестве неправильно из-за того, что другие операции со списками не так дешево обходятся.

DM>То, что список может быть использован в качестве стека, не делает каждое использование списка использованием стека

Я не понимаю, что вы подразумеваете под "использован в качестве стека". Я подразумеваю под этим использование операции абстрактного типа данных "стек". Вы видимо требуете, чтоб использование было оформлено как некая языковая сущность — т.е. как интерфейс "стек" или класс типов "стек"?

DM>как структуры данных.

Стек — не структура данных. Структура данных — это односвязный список.

DM>Например, работу со строками в хаскеле (которые [Char]) вряд ли кто-то в своем уме будет называть работой со стеком.

Нет, видимо оформления стека как языковой сущности для его использования вы не требуете. иначе не считали бы работу с [Char] работой со строками, ведь абстрактный тип данных "строка" для них не оформлен. И почему тогда нельзя назвать работу с [Char] работой со стеком, если стековые операции используются?

Здравствуйте, Klapaucius, Вы писали:

FR>>В реальности если нужна максимальная оптимизация все-равно и в хасклеле и окамле будет модуль на Си/С++.

K>Я говорю сейчас не о 10% кода, где нужна максимальная оптимизация, а о 70% кода, которые дожны работать с разумной скоростью, а не тормозить в сотни раз на ровном месте.

Тут ты делаешь совершенно необоснованное допущение, никаких тормозов тем более в сотни раз для такого "70% кода" на окамле не наблюдается.
Возможно ты хочешь писать на окамле используя идиомы хаскеля, тогда да проблемы будут.

Здравствуйте, Klapaucius, Вы писали:

BZ>>в новой списки вроде стали гораздо быстрее

K>Это не списки стали быстрее, это оптимизатор от лишних списков избавляется.

это я к тому, что там не оптимизатор, а саму реализацию совершенствуют. и по сравнению с нынешней реализацией списков в ghc — те 12 строк, которые хотя бы понятны с первого взгляда, представляют собой детский лепет

и между прочим это считается достоинством — library-driven optimizations вместо compiler-driven. а если ты хочешь сравнить честную реализацию ленивых списков в ghc и ocaml — то лучше напиши их обе ручками в 2 строки

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, BulatZiganshin, Вы писали:

BZ>>мне казалось, что ты критиковал производительность ленивых списков тоже?

K>

K>Я для того и замерил версию без оптимизации. Никакой фьюжн там, разумеется не сработал. И все рано в разы быстрее, чем окамловские списки.

т.е. производительность ты тоже критиковал, нет?

а разхница в скорости объясняется имхо тем, что ghc сейчас вышел на использование оптимизирующих С-компиляторов, и тем что ленивые вычисления в нём встроены, а не реализованы средствами самого языка

BZ>>это не отменяет того факта, что ghc добирался до нынешней произхводительности списков два десятка лет и нынешняя скорость обусловлена не мифическими достоинствами хаскела, а громадной работой над компилятором и библиотекой.

K>Это и есть реальное достоинство хаскеля, а не какое-то там "мифическое".

согласен. хаскел как язык, даже несмотря на свою медлительность, оказался более притягателен чем ocaml. остальное было делом времени

K>Впрочем, до нынешней производительности именно списков — он не 20 лет добирался. На этом фронте все прорывы уже довольно давние.

ага. ты полагаешь, что использование llvm на ней никак не сказалось?

BZ>>но почему-то специальный фреймворк аж в 12 строк, заменяющий стандартные строки в окамле, ты считаешь огромной проблемой, а куда более навороченный фреймворк, на разработке которого люди пишут целые научные статьи, в хаскеле ты не замечаешь

K>Еще раз, для того, чтоб обычный map работал никакие "фреймворки" не нужны. Для этого достаточно, в случае ghc, эффективной реализации ленивости (это, разумеется, большая заслуга разработчиков рантайма). Но от разработчиков библиотек для этого ничего не требуется.
K>"Фреймворки", про которые статьи пишут, делают совсем не ту работу, которая обсуждается в первоначальном посте. Никаких аналогов этих "фреймворков" для окамла нет, а значит и сравнивать нечего.

а кроме начального поста в треде никаких других не было, да?

давай всё же вспомним — ты считаешь проблемой 12 тривиальных строк на ml, решающих проблему переполнения стёка, а целые научные статьи, решающие проблему скорости на хаскеле — это так, пустяки, дело житейское. видимо от того, что оно решает другую задачу, эти строки перестали нуждаться в поддержке, и их может реализовать каждый школьник, имеющий десяток публикаций в Science

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, Слоноежик, Вы писали:

K>Да, если работает оптимизация то никакого списка нет. Но я специально измерил и без оптимизации. GHC 6.12, кстати, от 7.0 в этом плане ни в чем не отличается.

Но спорят то тут о том, что хаскель всегда быстрее и что там мегакомпилятор с которым можно писать код и не думать, и всё равно он будет быстрее чем если писать код на окамле и думать. Приятно конечно писать такой код, и особенно приятно, когда он оптимизируется нормально, но только слишком уж специальные условия должны быть, чтобы эта оптимизация сработала. А когда она не сработает, то тут у хаскеля тоже не всё хорошо.

Здравствуйте, Klapaucius, Вы писали:

С>>В окамле нету такой оптимизации. Но если надо, я там вместо ленивого списка [1..n] я могу написать тупой императивный for и не париться по поводу, есть ли в компиляторе для меня подобная оптимизация или нету.

K>Согласен на 100%. Я тут летом о том и писал, что идиоматичный окамл — это писать императивный for. Но со мной окамлисты спорили. Приятно видеть окамлиста, который реалистично смотрит на вещи, а не витает в эмпиреях, представляя, что на окамл можно безнаказанно писать ФП-код.

Тут есть небольшая тонкость. Я смогу написать for. Но это абсолютно не значит что я его буду писать. С очень большой вероятностью я просто по другому напишу алгоритм. При этом он не будет похож на алгоритм на хаскеле, и всё ещё останется функциональным и будет работать быстро.

Здравствуйте, Слоноежик, Вы писали:

С>Тут есть небольшая тонкость. Я смогу написать for. Но это абсолютно не значит что я его буду писать.

Ну какое-то время можно себя в этом уверять, но в реальности именно это и означает. Ну или вместо фора будет хвосторекурсивная функция — разница, вообще говоря, не велика.

С>С очень большой вероятностью я просто по другому напишу алгоритм. При этом он не будет похож на алгоритм на хаскеле, и всё ещё останется функциональным и будет работать быстро.

Со стопроцентной вероятностью придется писать не как на хаскеле. Потому, что писать на окамле как на хаскеле — плохая идея. Годится только для форумных диспутов. В реальности придется писать как на паскале.

Здравствуйте, Klapaucius, Вы писали:


K>Это, конечно, упрощение. Моя позиция выражается так: GHC оптимизирует высокоуровневый код лучше ocamlopt и, не в последнюю очередь потому, что в хаскель-комьюнити считается, что нужно оптимизировать еще лучше и ведутся соотвествующие работы. В окамлокомьюнити, с другой стороны, считается, что "это все не нужно". В результате код на окамле получается более низкоуровневым, сложным и многословным — производительность-то имеет значение. Но когда на это указываешь — окамлисты почему-то обижаются и с еще большим жаром продолжают настаивать, что что-то "ненужно".

Более правильно сказать так — GHC оптимизирует код на хаскеле лучше чем осаmlopt оптимизирует код на хаскеле, зачем то переведённый на ocaml. И при этом обычно забывают что хаскель немножко ленивый, а ocaml немножко энергичный, и поэтому один и тот же алгоритм на хаскеле и на окамле будет выглядеть по разному. И оба будут при этом высокоуровневыми и быстрыми. И даже будут при этом будут немногословными, кроме самых клинических случаев. И вопрос — а зачем допустим оптимизировать Ленивые списки типа [1..n] в энергичном языке, где их исползуют 3 человека, и те пишут в основном не на окамле а на хаскеле.

P.S. Про основные проблемы ocaml-а окамлисты прекрасно знаем. И то что на нём нельзя писать как на хаскеле, это далеко не главная из них.

P.P.S. Не стоит призывать Сергея Губанова в эту тему.

Здравствуйте, Klapaucius, Вы писали:

K> Моя позиция выражается так: GHC оптимизирует высокоуровневый код лучше ocamlopt

А с этим мы и не спорим. Я сразу заметил, что в ocamlopt минимум оптимизаций, а в GHC их масса.

K> и, не в последнюю очередь потому, что в хаскель-комьюнити считается, что нужно оптимизировать еще лучше и ведутся соотвествующие работы. В окамлокомьюнити, с другой стороны, считается, что "это все не нужно".

Проблема в том, что долгое время над окамлом работало полчеловека из INRIA, комьюнити никак не участвовало в разработке компилятора и оптимизаций в нем по чисто бюрократическим причинам.

В итоге вместо заявленной темы (про строгость и списки) вы скатываетесь к сравнению двух конкретных компиляторов разных языков с очень разными историями. Смысл?

Здравствуйте, D. Mon, Вы писали:

DM>Окамлистам списки разумного размера нужны, они их используют (и я среди них). И все работает.

Как я и сказал. Не нужны — только в этом треде, в котором "разумный размер списка стремится к нулю".

DM>А неразумное применение списков и хаскеллистам не нужно:
DM>

иначе я бы и для 10к элементов не стал бы его использовать

— писал

Автор: BulatZiganshin
Дата: 03.12.11

выше Булат.

Мировой аттракцион — фантастическое редактирование.
Реальное мнение Булата о "разумном размере" противоположно вашему и совпадает с моим:

я ведь ясно написал, что список, хоть и может содержать миллионы элементов, не использует операции, которые медленней чем на массивах — иначе я бы и для 10к элементов не стал бы его использовать. ограничение в 100к элементов, после которого ты считаешь неверным использовать списки — связано именно с проблемами окамловского рантайма, а не тем, что именно до этой границы можно терпеть O(n^2) алгоритмы

DM>сколько можно.
Можно сколько угодно, а имеет смысл до тех пор, пока реакция есть.

Здравствуйте, Klapaucius, Вы писали:

K>Мировой аттракцион — фантастическое редактирование.
K>Реальное мнение Булата о "разумном размере" противоположно вашему и совпадает с моим:

Нет там противоположности. Он говорит, что не стал бы использовать длинные списки для операций, "которые медленнее чем на массивах". О том же и я говорю.

Здравствуйте, FR, Вы писали:

FR>По моему цена больше зависит от умения компилятора оптимизировать, а не от ленивости.

И от этого тоже. Но в данном случае компилятор победит рантайм с хорошей поддержкой ленивости, в общем случае, только при дефорестации вообще всего, анализе всей программы, суперкомпиляции. Что само по себе достаточно проблематично. Понятно, что избавляться от списков вовсе — лучшее решение, но на практке избавиться от всех списков не получается, и в таких случаях без эффективной поддержки ленивости дела принимают очень неприятный оборот.

FR>В Xаскель просто тупо вложено больше человеко-часов.

Верно. Эффективная реализация ленивости тоже, в общем-то, требует порядочно человекочасов. Я, кстати, считаю это недостатком ленивости номер один.

Здравствуйте, 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.

Здравствуйте, D. Mon, Вы писали:

DM>Запустил repl окамла. На списке в 150 000 элементов обычный map работает. Для строгих списков длина значительная, нужно быть очень странным человеком, чтобы хотеть такие объемы обрабатывать в виде строгих списков в памяти.

Для интерпретатора можно задавать размер стека с помощью OCAMLRUNPARAM
http://caml.inria.fr/pub/docs/manual-ocaml/manual024.html#toc96

Для скомпилированной программы лимит берется из настроек OS, в nix системах это легко настраивается,
в win жестко зашивает линкером, так что можно только задать при компиляции вроде.

DM>PS. Ты тоже немерлист чтоле? Где вы все слово "длинна" взяли?

Здравствуйте, MigMit, Вы писали:

MM>Я правильно понимаю, что проблемой является переполнение стека?

Правильно.

MM>Но тогда это проблема реализации, а не самого языка, нет?

Верно, проблема реализации. И?

Здравствуйте, D. Mon, Вы писали:

DM>Работает эффективно

Это смотря с чем сравнивать, но да, по сравнению с двойным проходом, например, эффективно.

DM>стек не съедает

Верно.

DM>интерфейс имеет кошерный.

Самый большой недостаток интерфейса — это то, что функция применяется к spine-strict списку и возвращает spine-strict список.

DM>Пользователь при желании может дописать еще таких функций. Все хорошо. В чем проблема?

Виноват, пост я написал длинный. Вы попробуйте перечитать самое начало, а потом сразу перемотать в конец. Тогда, по идее, должны броситься в глаза некоторые проблемы. Например, увеличение кода в 4-6 раз.

DM>Или есть идея получше?

Нет, это лучшее из того, что можно сделать (для строгого списка) — эту идею я, собственно, и собирался донести среди прочих в этом посте.

Здравствуйте, D. Mon, Вы писали:

DM>Запустил repl окамла. На списке в 150 000 элементов обычный map работает.

Про это уже FR ответил.

DM>Для строгих списков длина значительная, нужно быть очень странным человеком, чтобы хотеть такие объемы обрабатывать в виде строгих списков в памяти.

Что же страшного в списках, которые обрабатываются за десятки миллисекунд и занимают единицы мегабайт в памяти, позвольте узнать?

DM>Где вы все слово "длинна" взяли?

Спасибо, обязательно исправлю.

Здравствуйте, FR, Вы писали:

FR>в win жестко зашивает линкером, так что можно только задать при компиляции вроде.

Не знал, что под виндовс ocamlopt можно размер стека указать. Думал только каким-нибудь editbin /stack:размер потом править (сам так не делал).

Здравствуйте, Klapaucius, Вы писали:

K>Верно, проблема реализации. И?

"И" как бы не факт, что хорошая работа реализации в данном случае должна хоть как-то отражаться в исходном коде библиотек. В частности, подход окамля может быть и вполне разумным.

А вот SML-ный вариант — это да, смешно.

Здравствуйте, Klapaucius, Вы писали:

K>Самый большой недостаток интерфейса — это то, что функция применяется к spine-strict списку и возвращает spine-strict список.

Раз это недостаток, значит можно лучше? Какой интерфейс для функции map из модуля строгих списков подошел бы лучше?

K>Что же страшного в списках, которые обрабатываются за десятки миллисекунд и занимают единицы мегабайт в памяти, позвольте узнать?

Линейность доступа. Большинство нужных операций имеют неприличную сложность. Во многих случаях вместо строгих списков уместнее Map'ы, Set'ы, массивы и энумераторы (в зависимости от задачи).

Здравствуйте, MigMit, Вы писали:

MM>"И" как бы не факт, что хорошая работа реализации в данном случае должна хоть как-то отражаться в исходном коде библиотек. В частности, подход окамля может быть и вполне разумным.

Вот! Именно такие рассуждения я и назвал "игнорированием реальности". И map из std-lib — закономерный результат такого подхода, когда вместо того, чтоб писать библиотеку для конкретной (и, собственно, единственной) реализации окамла — пишут библиотеку для платоновской идеи реализации окамла, а то, что, скажем так, в тени этой идеи библиотечная функция не работает — ну, это проблема реализации, а не окамла.

Здравствуйте, D. Mon, Вы писали:

DM>Раз это недостаток, значит можно лучше?

К сожалению, если что-то — недостаток, то это не всегда означает, что можно лучше.

DM>Какой интерфейс для функции map из модуля строгих списков подошел бы лучше?

По вашему, если выбор ограничен одним вариантом — т.е. его и нет вовсе — это означает, что этот единственный вариант и недостатком быть не может?

DM>Линейность доступа. Большинство нужных операций имеют неприличную сложность. Во многих случаях вместо строгих списков уместнее Map'ы, Set'ы, массивы и энумераторы (в зависимости от задачи).

Ну вот, уже доступ к n-му элементу появился. А если такой доступ не нужен или осуществляется однократно, например? Вы ведь взялись, как я понял, обосновывать ненужность списков больше того, для которого map из std-lib еще в стек умещается. А это задача сложная — тут такими отговорками не отделаться.

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

MM>И посему имеют возможность изменить и РЕАЛИЗАЦИЮ ТОЖЕ.
Ну вот и пусть сначала реализацию изменят, а потом и пишут так, как позволяет писать новая реализация. А не наоборот.

MM>Собственно, а не сделано ли это уже? У меня нет сейчас на машине окамля, и я не хочу его ставить специально для этого, но, может быть, там таки не переполняется стек?
Нет, не сделано. А как вы себе представляете изменения в реализации Ocaml-а, которые позволят вот так писать? Это нужно отказываться от обычного стека и автоматически CPS-трансформировать весь код. Создатели ocaml на такое пойти не могут. Вот SML/NJ именно так и устроен и, соотвественно, простой map без всяких притопов и прихлопов в нем работает:

Standard ML of New Jersey v110.73 [built: Mon May 16 06:14:15 2011]
- fun map f [] = []
=   | map f (x::xs) = f x::map f xs
= ;;
val map = fn : ('a -> 'b) -> 'a list -> 'b list
- map (fn x => x + 1) (List.tabulate (1000000, fn i => i));;
val it = [1,2,3,4,5,6,7,8,9,10,11,12,...] : int list
- List.length it;;
val it = 1000000 : int

Вот только работает очень медленно — ни на что другое, кроме как быть REPL, совместно используемым с MLton, он и не годится.

Здравствуйте, D. Mon, Вы писали:

DM>Стандартная List.map таки стек переполняет. На 200К элементах уже.

Это зависит. Где-то стек 8M, а где-то и 1M.

DM>Но поскольку на практике все используют расширенные стандартные библиотеки (батарейки, extLib, core..), в которых функции над списками все хвостаторекурсивные, то проблема не особо актуальна. Разве что для критиков-теоретиков.

Обсуждаемая проблема заключается не в том, что используется нехвосторекурсивный map. Он, разумеется, не используется, потому как использовать его нельзя. Проблема заключается в том, что вместо структурно-рекурсивной функции нужно писать хвосторекурсивную, а вместо двух строк — 12. А эта проблема актуальна — еще как!

Здравствуйте, D. Mon, Вы писали:

K>>К сожалению, если что-то — недостаток, то это не всегда означает, что можно лучше.
K>>По вашему, если выбор ограничен одним вариантом — т.е. его и нет вовсе — это означает, что этот единственный вариант и недостатком быть не может?

DM>Ну, мне кажется странным считать фактически определение недостатком.

Это неожиданно, потому как к определениям вы разговор и свели. Речь идет о сравнении ленивого и строгого по хвосту списка.

DM>Это как считать недостатком бита то, что у него всего два возможных значения.

Ну и в чем проблема в данном случае? У бита, разумеется, два возможных значения по определению. Но двоичная система была выбрана на основании технических соображений. Были рассмотрены соотвествующие альтернативы — их преимущества и недостатки.

DM>Ничего сложного.

Очень сложно. Нужно ведь обосновать не то, что строгий список не особенно полезная структура данных — с этим я легко соглашусь и мой пост и об этом в том числе, а то, что начиная с какого-то размера список внезапно полностью, окончательно и бесповоротно перестает быть полезным. С особым удовольствием послушаю как вы обосновываете то, почему Максимальная Полезная Длина при одних настройках стека одна, а при других — другая.

DM>Если человек в качестве структуры для ста тыщ данных выбирает строгий список, это значит он не планирует ни обращаться к n-ному элементу, ни искать нужные элементы, ни брать куски этих данных, ни объединять несколько таких структур в одну, ни добавлять что-либо в конец или середину, ни удалять элементы из любых мест кроме начала. Ну т.е. вообще ничего практически не собирается делать. Это очень странный человек и довольно редкая ситуация. Обычно какие-то из этих операций все же нужны, а тогда использовать списки уже нет смысла, есть более подходящие структуры.
DM>Есть одно хорошо подходящее для таких списков применение — стеки. А кроме них, что еще?

1) Это все недостатки списка любого размера.
2) И что, теперь уже и стеки не нужны?
3) Понимаете ли вы разницу между "начиная с такого-то объема входных данных программа работает медленнее чем нам нужно" и "начиная с такого-то объема данных программа падает"?

Здравствуйте, D. Mon, Вы писали:

DM>Ничего сложного. Если человек в качестве структуры для ста тыщ данных выбирает строгий список, это значит он не планирует ни обращаться к n-ному элементу, ни искать нужные элементы, ни брать куски этих данных, ни объединять несколько таких структур в одну, ни добавлять что-либо в конец или середину, ни удалять элементы из любых мест кроме начала. Ну т.е. вообще ничего практически не собирается делать. Это очень странный человек и довольно редкая ситуация.

ну тогда и ты на своей машине не заводи больше 100к файлов, если не хочешь чтоб тебя считали "очень странным человеком"

в freearc список архивируемых файлов хранится именно в виде списка. сортировка, разбиение на группы на списках прекрасно работают

Здравствуйте, Klapaucius, Вы писали:

K>Это неожиданно, потому как к определениям вы разговор и свели. Речь идет о сравнении ленивого и строгого по хвосту списка.

Я думал, топик о строгих списках. Чего их сравнивать с ленивыми-то. Нужны ленивые — берешь ленивые и используешь.

K>Очень сложно. Нужно ведь обосновать не то, что строгий список не особенно полезная структура данных — с этим я легко соглашусь и мой пост и об этом в том числе, а то, что начиная с какого-то размера список внезапно полностью, окончательно и бесповоротно перестает быть полезным. С особым удовольствием послушаю как вы обосновываете то, почему Максимальная Полезная Длина при одних настройках стека одна, а при других — другая.

Она не зависит от размера стека. МПД близка к нулю в большинстве случаев. Просто когда элементов "мало", использование такой субоптимальной структруры еще можно простить, там разница между структурами несущественна, для малых n разница между O(n) и O(log n) мала.

K>1) Это все недостатки списка любого размера.

Именно. И чем больше размер, тем они сильнее выпирают.

K>2) И что, теперь уже и стеки не нужны?

Нужны иногда. Только для них не нужны map и многие другие операции.

K>3) Понимаете ли вы разницу между "начиная с такого-то объема входных данных программа работает медленнее чем нам нужно" и "начиная с такого-то объема данных программа падает"?

Да.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>Здравствуйте, D. Mon, Вы писали:

DM>>Ничего сложного. Если человек в качестве структуры для ста тыщ данных выбирает строгий список, это значит он не планирует ни обращаться к n-ному элементу, ни искать нужные элементы, ни брать куски этих данных, ни объединять несколько таких структур в одну, ни добавлять что-либо в конец или середину, ни удалять элементы из любых мест кроме начала. Ну т.е. вообще ничего практически не собирается делать. Это очень странный человек и довольно редкая ситуация.

BZ>ну тогда и ты на своей машине не заводи больше 100к файлов, если не хочешь чтоб тебя считали "очень странным человеком"

Ненене, Дэвид Блейн. Это ты выбрал список в качестве способа хранения инфы про файлы, так что странным человеком быть тебе. Я вот храню файлы в дереве (на базе B-Tree, если не ошибаюсь).

DM>Здравствуйте, Klapaucius, Вы писали:

DM>Я думал, топик о строгих списках. Чего их сравнивать с ленивыми-то.

Я уже заметил, что вы предпочитаете сравнения в парах из одного элемента (и, видимо, аплодисменты одной рукой). Но для меня это слишком уж высокоградусный дзен — я обычно сравниваю одно с другим. Например, строгие списки с ленивыми.

DM>Нужны ленивые — берешь ленивые и используешь.

Не везде доступны. К примеру, в ocaml они абсурдно тормозные

Автор: FR
Дата: 05.07.11

, что делает их практическое использование невозможным. Было бы можно ленивые использовать — кто бы стал извращаться вышеописанными способами?

DM>Она не зависит от размера стека. МПД близка к нулю в большинстве случаев.

Отлично! Теперь уже и списки не нужны.

DM>Только для них не нужны map и многие другие операции.

Просто поразительно, без скольких вещей вы можете обходиться!

K>>Понимаете ли вы разницу между "начиная с такого-то объема входных данных программа работает медленнее чем нам нужно" и "начиная с такого-то объема данных программа падает"?
DM>Да.

К чему тогда было заводить разговор о практичности std-lib-овской map?

Здравствуйте, Klapaucius, Вы писали:

K>Не везде доступны. К примеру, в ocaml они абсурдно тормозные

Автор: FR
Дата: 05.07.11

, что делает их практическое использование невозможным. Было бы можно ленивые использовать — кто бы стал извращаться вышеописанными способами?

в хаскеле они не быстрее. помню, побайтовое чтение файла получалось раз в 70 медленнее поблочного

Здравствуйте, BulatZiganshin, Вы писали:

BZ>с точки зрения фанатика фортрана странным выглядит человек, вообще использующий рекурсию. подумай об этом

О чем тут думать-то? Если программист на фортране будет думать, что рекурсия — это хорошо, то это не принесет ему никакой пользы — на фортране-то ему рекурсивную функцию все равно не написать (начиная с Fortran 90 можно, но разговор не об этом). Это только сделает его несчастнее. Поэтому и естественная защитная реакция: рекурсия не нужна. Та же ситуация и со списками и ocaml-ом. Работать с ними трудно (что я показал выше), да и код со списками на окамле работает медленно (работай так медленно хаскельный код со списками — я думаю и вы бы их использовали меньше). Поэтому реакция D. Mon совершенно нормальная — списки не нужны.

Здравствуйте, Klapaucius, Вы писали:

K>Были бы списки окамловские — получилось бы в 700 раз. Это не шутка, почитайте тесты в треде на который я ссылался.

я там увидел 50-кратную разницу между самым медленным вариантом и prefilled list

Здравствуйте, BulatZiganshin, Вы писали:

BZ>с точки зрения фанатика фортрана странным выглядит человек, вообще использующий рекурсию. подумай об этом

Эта демагогия не изменит характеристик сложности алгоритмов над списками и не оправдает такой безответсвенный выбор структуры. Не, я понимаю, что в хаскеле много готовых функций для работы с ними, и использовать списки везде удобно. Просто не надо думать, что это удобство бесплатно и всегда оправдано.

Здравствуйте, Klapaucius, Вы писали:

DM>>Здравствуйте, Klapaucius, Вы писали:

DM>>Я думал, топик о строгих списках. Чего их сравнивать с ленивыми-то.

K>Я уже заметил, что вы предпочитаете сравнения в парах из одного элемента (и, видимо, аплодисменты одной рукой). Но для меня это слишком уж высокоградусный дзен — я обычно сравниваю одно с другим. Например, строгие списки с ленивыми.

Ок, если угодно, можно сравнить с ленивыми. Вот, чуть ниже пользователь Klapaucius написал, что ленивые списки "абсурдно тормозные" (в том языке, о котором шла речь в ветке). Спасибо ему за проделанную работу, на этом сравнение можно закончить.

DM>>Только для них не нужны map и многие другие операции.

K>Просто поразительно, без скольких вещей вы можете обходиться!

Покажите мне, пожалуйста, реальный пример, где для стека применяется map. Именно для стека, не просто для списка.

K>>>Понимаете ли вы разницу между "начиная с такого-то объема входных данных программа работает медленнее чем нам нужно" и "начиная с такого-то объема данных программа падает"?
DM>>Да.

K>К чему тогда было заводить разговор о практичности std-lib-овской map?

Попробуйте собрать обе части высказанной выше мысли. Тезис был таким: для тех размеров, где списки имеет смысл использовать, стандартный map вполне рабочий. В этой идее две части: 1) строгие списки разумно использовать для небольшого числа элементов (где O(n) и O(log n) отличаются не так разительно), и 2) для таких n стандартный map работает. Так понятнее? Вопросы для самопроверки: на каких списках работает стандартный List.map окамла? На каких размерах списки — практичная структура данных? Как соотносятся между собой эти размеры?

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, MigMit, Вы писали:

MM>>Всё это было бы правильно, если бы речь шла о внешней библиотеке. Но стандартная библиотека обычно пишется примерно теми же людьми, которые пишут компилятор.
K>Вообще — не обязательно, но это так, к слову.

Конечно, не обязательно. Я и не написал "всегда".

MM>>И посему имеют возможность изменить и РЕАЛИЗАЦИЮ ТОЖЕ.
K>Ну вот и пусть сначала реализацию изменят, а потом и пишут так, как позволяет писать новая реализация. А не наоборот.

Согласен.

MM>>Собственно, а не сделано ли это уже? У меня нет сейчас на машине окамля, и я не хочу его ставить специально для этого, но, может быть, там таки не переполняется стек?
K>Нет, не сделано. А как вы себе представляете изменения в реализации Ocaml-а, которые позволят вот так писать? Это нужно отказываться от обычного стека и автоматически CPS-трансформировать весь код.

М-м-м, не думаю. По-моему, можно ограничиться конструкторами.

K>Создатели ocaml на такое пойти не могут. Вот SML/NJ именно так и устроен и, соотвественно, простой map без всяких притопов и прихлопов в нем работает:

А зачем тогда там эту фигню нагородили?

Здравствуйте, MigMit, Вы писали:

MM>А зачем тогда там эту фигню нагородили?

В примере на SML простой ручной loop unrolling сделан, чтобы чуть побыстрее был, а суть исходная — прямой map без хвостовой рекурсии.

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Есть какая-то принципиальная разница между списком и любым другим рекурсивным типом данных (то, что написал Klapaucius справедливо для всех рекурсивных типов, а не только для списков) или вы считаете использование рекурсивных типов — безответственным?

Всевозможные деревья — тоже обычно рекурсивные типы, но сложность операций с ними другая. Их я не считаю непрактичными, но про них Klapaucius не писал, просто так на них его пост не обобщается, вроде.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>в данном же топике я ведь ясно написал, что список, хоть и может содержать миллионы элементов, не использует операции, которые медленней чем на массивах

Сорри, не увидел такого. Были упомянуты сортировка и группировка, но вряд ли это были единственные операции.

BZ>- иначе я бы и для 10к элементов не стал бы его использовать.

Вот и я об этом.

BZ> ограничение в 100к элементов, после которого ты считаешь неверным использовать списки — связано именно с проблемами окамловского рантайма, а не тем, что именно до этой границы можно терпеть O(n^2) алгоритмы

Не, я не ставлю такого ограничения в 100к. Я сказал, что МПД близка к нулю, и что практичны/эффективны списки на "малом" числе элементов. Поэтому окамловских 150-200к хватает с головой.

BZ>поэтому я написал, что создатель рантайма (не ты), который заявляет что его пользователь, использующий с O(n) операциями списки в миллион элементов — "странный человек", лукавит так же, как программист, который сделал архиватор и потом объявляет странным своего пользователя, если тот имеет больше 100к файлов. надо уметь сознаться, что проблема всё же в твоём рантайме, а не в пользователе, который "хочет странного"

Да, сознаюсь, проблема есть. Уже писал об этом выше. И о том, что она неактуальна, будучи решена в расширенных библиотеках, тоже.

И специально для считающих, что сортировка списков и массивов стоит одинаково:

let arr = Array.init 2000000 (fun x-> (x land 65535) * 12343 mod 100000) in
Array.sort compare arr;
let res = Array.rev arr in
print_int (res.(0) + res.(Array.length res - 1));;

2.53 с
Разница более 3 раз.

Здравствуйте, BulatZiganshin, Вы писали:

BZ> видимо для тебя это всё заведомое баловство

Ну вот будет FreeArc целиком написан на хаскеле, а не только тонкая прослойка между GTK и сишными либами компрессии, тогда будет не баловство.

Здравствуйте, Klapaucius, Вы писали:

K>Не везде доступны. К примеру, в ocaml они абсурдно тормозные

Автор: FR
Дата: 05.07.11

, что делает их практическое использование невозможным. Было бы можно ленивые использовать — кто бы стал извращаться вышеописанными способами?

Ты мягко говоря преувеличиваешь, они вполне годны для использования, по этой же ссылке видно что самый
шустрый аналог ленивого списка Seq из батареек всего в два раз медленнее предварительно заполненного
строгого списка.
Ну и даже тормоза самого удобного варианта Enum всего в 4 раза от строгого, тоже не являются стоп фактором
в большинстве случаев.

Здравствуйте, D. Mon, Вы писали:

DM>Ок, уговорили, давайте сравним эти нищие неэффективные списки окамла и богатые, крутые и эффективные ленивые списки хаскеля.

речь гла ведь о том, что ленивые списки в окамле очень тормозные, а энергичные — ограничены размером стёка

DM>Haskell (с ключом -O2): 11.86 c
DM>Ocaml (c ключом -inline 99): 8.98 c

я правильно понял, что ленивые списки хаскела практически не отличаются по скорости от энергичных окамла???

ты ниже на массивах скорость привёл, интересно ещё скорость сишной реализации

Здравствуйте, D. Mon, Вы писали:

DM>Ноут 2 ГГц с Вистой, GHC 6.12.1, OCaml 3.10.2.
DM>Haskell (с ключом -O2): 11.86 c
DM>Ocaml (c ключом -inline 99): 8.98 c

Ленивые списки быстрее не из-за какого-то чуда, а из-за того, что, например, мемори-футпринт у них может быть меньше чем у строгих. Если подобрать задачу вроде такой — разница будет определяться только настройками сборщика мусора (типа множителя увеличения хипа и его начального размера).
На моей машине результаты такие:

blah-blah-blah$ time ./hlist.exe
"99997"

real    0m7.242s
user    0m0.015s
sys     0m0.000s
blah-blah-blah$ time ./olist.exe
99997
real    0m6.432s
user    0m0.031s
sys     0m0.000s
blah-blah-blah$ time ./hlist.exe +RTS -H512M
"99997"

real    0m6.261s
user    0m0.000s
sys     0m0.016s

Т.е. меняем настройки сборщика — разницы нет.

Здравствуйте, Klapaucius, Вы писали:

K>Работает за 0,347 сек.

фи, хаскел даже медленней чем C

Здравствуйте, Klapaucius, Вы писали:

DM>>2.53 с

K>Неожиданный поворот.

Вот такой вариант

let arr = Array.init 2000000 (fun x-> (x land 65535) * 12343 mod 100000) in
Array.stable_sort (-) arr;
let res = ExtArray.Array.rev arr in
print_int (res.(0) + res.(Array.length res - 1));;

у меня работает 1.07 с, что все равно медленно, конечно. Другой метод сортировки и отказ от полиморфной и нешустрой compare.

Здравствуйте, Klapaucius, Вы писали:

K>Ленивые списки быстрее не из-за какого-то чуда, а из-за того, что, например, мемори-футпринт у них может быть меньше чем у строгих.

Может меньше, а может больше, зависит от задачи. Меньше в случае, когда данные одноразовые, такие случаи в окамле делаются энумераторами без лишних аллокаций. Если данные не одноразовые, т.е. вычисленные значения хранятся, а не сразу выбрасываются, то ленивые списки и памяти жрут больше, и работы. Если повезет, и оптимизатор догадается работать с ними строго, получается то же самое. Мы это все уже обсуждали здесь, чего повторяться.

Здравствуйте, MigMit, Вы писали:

K>>Нет, не сделано. А как вы себе представляете изменения в реализации Ocaml-а, которые позволят вот так писать? Это нужно отказываться от обычного стека и автоматически CPS-трансформировать весь код.
MM>М-м-м, не думаю. По-моему, можно ограничиться конструкторами.

Да, для map этого достаточно, но для foldr, например, уже нет.

MM>А зачем тогда там эту фигню нагородили?

Это общеполезные оптимизации. Worker/wrapper-трансформация и анроллинг. Но если использовать такую функцию с реализацией, использующей обычный стек — надышать перед сметью получиться больше, разве нет?

Здравствуйте, FR, Вы писали:

FR>шустрый аналог ленивого списка Seq

Seq не является аналогом ленивого списка.

FR>Ну и даже тормоза самого удобного варианта Enum

И Enum аналогом ленивого списка не является.

Здравствуйте, D. Mon, Вы писали:

DM>Да, сознаюсь, проблема есть. Уже писал об этом выше. И о том, что она неактуальна, будучи решена в расширенных библиотеках, тоже.

Еще раз напоминаю, что проблема не решена, потому что...

Обсуждаемая проблема заключается не в том, что используется нехвосторекурсивный map. Он, разумеется, не используется, потому как использовать его нельзя. Проблема заключается в том, что вместо структурно-рекурсивной функции нужно писать хвосторекурсивную, а вместо двух строк — 12.

Здравствуйте, D. Mon, Вы писали:

DM>В принципе, да. GHC из Haskell Platform 2010 с множеством оптимизаций и параллельным сборщиком мусора уже не очень сильно отстает от ocamlopt начала 2008 года с минимумом оптимизаций и полностью однопоточным рантаймом/сборщиком.

Во-первых, оптимизировать в вашем благоразумно подобранном примере просто нечего. Если оптимизировать есть что — разница будет соотвествующей:
Компилятор,который

Автор: Klapaucius
Дата: 30.06.11

оптимизирует.

Автор: Klapaucius
Дата: 01.07.11

Компилятор, который не оптимизирует.

Автор: FR
Дата: 01.07.11

Да, тут не списки, но тот кто тестировал явно считал, что со списками будет медленнее. Я сам это проверю, когда время на это будет.
Во-вторых, многопоточный рантайм на однопоточной задаче будет работать медленнее однопоточного. Вы линкуете программу на хаскеле с однопоточным рантаймом. Поэтому противопоставлять тут нечего.

DM>Пока не знаю, почему такая огромная разница. Возможно, совсем разная сортировка, хотя по идее везде должен быть quicksort.

Непонятно, по какой идее должен быть quicksort? Быстрая сортировка, скажем так, не особенно практичный алгоритм. В нормальной реализации stl std::sort — это introsort. Но это не "совсем разная" сортировка — это быстрая сортировка для больших блоков, хипсорт для малых и вставками для особенно малых.

const int _ISORT_MAX = 32;

template<class _RanIt,
    class _Diff,
    class _Pr> inline
    void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
    {    // order [_First, _Last), using _Pred
    _Diff _Count;
    for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
        {    // divide and conquer by quicksort
        _STD pair<_RanIt, _RanIt> _Mid =
            _Unguarded_partition(_First, _Last, _Pred);
        _Ideal /= 2, _Ideal += _Ideal / 2;    // allow 1.5 log2(N) divisions

        if (_Mid.first - _First < _Last - _Mid.second)
            {    // loop on second half
            _Sort(_First, _Mid.first, _Ideal, _Pred);
            _First = _Mid.second;
            }
        else
            {    // loop on first half
            _Sort(_Mid.second, _Last, _Ideal, _Pred);
            _Last = _Mid.first;
            }
        }

    if (_ISORT_MAX < _Count)
        {    // heap sort if too many divisions
        _STD make_heap(_First, _Last, _Pred);
        _STD sort_heap(_First, _Last, _Pred);
        }
    else if (1 < _Count)
        _Insertion_sort(_First, _Last, _Pred);    // small
    }

Здравствуйте, D. Mon, Вы писали:

DM>Меньше в случае, когда данные одноразовые, такие случаи в окамле делаются энумераторами без лишних аллокаций.

Но когда мы это обсуждали — вдруг выяснилось, что производительность у них, мягко говоря, не блестящая.

DM>Если данные не одноразовые, т.е. вычисленные значения хранятся, а не сразу выбрасываются, то ленивые списки и памяти жрут больше, и работы.

Помимо двух экстремальных случаев "ничего не храним" и "все храним". Есть еще промежуточные варианты, когда хранится то, что требуется, а что не требуется — не хранится. Попробуйте написать на окамле ваш же собственный бенчмарк из статьи про clean (там, где простые числа вычисляются) — сразу поймете, что я имею в виду.

DM>Если повезет, и оптимизатор догадается работать с ними строго, получается то же самое.

Не нужно фантазировать — оптимизатор никогда не "догадывается" работать строго с ленивыми конструкторами. Анализатор строгости вообще вычисляет строгость паттерн-матчинга, а не параметров конструктора. Если бы такой "догадыватель" действительно существовал — и делал бы из ленивых списков строгие — то функции просто перестали бы в стек умещаться — вот и все радости.

DM>Мы это все уже обсуждали здесь, чего повторяться.

Ну вот видите, обсуждали, а толку, судя по этому вашему посту, никакого.

Здравствуйте, D. Mon, Вы писали:

DM>Ок, если угодно, можно сравнить с ленивыми. Вот, чуть ниже пользователь Klapaucius написал, что ленивые списки "абсурдно тормозные" (в том языке, о котором шла речь в ветке).

В ветке речь идет, как минимум, о 4-х языках.

DM>Покажите мне, пожалуйста, реальный пример, где для стека применяется map. Именно для стека, не просто для списка.

Какое-то галюциногенное противопоставление. Стек — это абстрактный тип данных — три операции: положить на вершину, взять с вершины, убрать с вершины. Односвязный список — это структура данных, которая, разумеется, является стеком потому, что для нее определены три вышеупомянутые операции: cons, head, tail. И, соответственно, map для списка, который как раз эти операции и использует — это map для стека.

DM>Попробуйте собрать обе части высказанной выше мысли. Тезис был таким: для тех размеров, где списки имеет смысл использовать, стандартный map вполне рабочий. В этой идее две части: 1) строгие списки разумно использовать для небольшого числа элементов (где O(n) и O(log n) отличаются не так разительно), и 2) для таких n стандартный map работает. Так понятнее?

Вы почему-то старательно выбираете как раз такие операции, которые для списка хуже, чем для дерева, а вот добавление элемента в начало, например, такая операция, сложность которой для списка меньше (ну, у finger tree это тоже константа, но константа намного большая). Так понятнее?

DM>Вопросы для самопроверки: на каких списках работает стандартный List.map окамла?

Зависит от настройки размера стека.

DM>На каких размерах списки — практичная структура данных?

По вашей мысли — на таких, которая позволит вам оправдать солиптический map из std-lib. В реальности — зависит от того, что с этими списками делать.

DM>Как соотносятся между собой эти размеры?

Никак.

Здравствуйте, Klapaucius, Вы писали:

K>В ветке речь идет, как минимум, о 4-х языках.

Сравнивать эффективность разных структуры данных на примере реализаций в разных языках мало смысла. А то так можно и на реболе каком-нибудь реализовать структуру, а потом говорить о ее неэффективности.

K>Какое-то галюциногенное противопоставление.

Вы, кажется, потеряли нить разговора. Напомню:

DM> Есть одно хорошо подходящее для таких списков применение — стеки. А кроме них, что еще?
K> И что, теперь уже и стеки не нужны?
DM> Нужны иногда. Только для них не нужны map и многие другие операции.
K> Просто поразительно, без скольких вещей вы можете обходиться!
DM> Покажите мне, пожалуйста, реальный пример, где для стека применяется map. Именно для стека, не просто для списка.

Я говорю, что когда список используется в качестве стека, для него не нужен map, а если это не так, то прошу привести примеры.

То, что список может быть использован в качестве стека, не делает каждое использование списка использованием стека как структуры данных. Например, работу со строками в хаскеле (которые [Char]) вряд ли кто-то в своем уме будет называть работой со стеком.

Остальное поскипано, топчетесь на месте.

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, MigMit, Вы писали:

K>>>Нет, не сделано. А как вы себе представляете изменения в реализации Ocaml-а, которые позволят вот так писать? Это нужно отказываться от обычного стека и автоматически CPS-трансформировать весь код.
MM>>М-м-м, не думаю. По-моему, можно ограничиться конструкторами.

K>Да, для map этого достаточно, но для foldr, например, уже нет.

А при чём тут foldr? В общем случае, он и в ленивом языке стек переполняет (если список длинный).

MM>>А зачем тогда там эту фигню нагородили?

K>Это общеполезные оптимизации. Worker/wrapper-трансформация и анроллинг. Но если использовать такую функцию с реализацией, использующей обычный стек — надышать перед сметью получиться больше, разве нет?

Так речь, вроде, шла о том, что SML/NJ использует не обычный стек. А для чего ещё делать такую оптимизацию — я не особо понимаю.

Здравствуйте, Klapaucius, Вы писали:

K>И Enum аналогом ленивого списка не является.

Не важно, области применения у них сильно пересекаются с областью применения
ленивых списков.

Здравствуйте, Klapaucius, Вы писали:

K>Еще раз напоминаю, что проблема не решена, потому что...
K>

K>Обсуждаемая проблема заключается не в том, что используется нехвосторекурсивный map. Он, разумеется, не используется, потому как использовать его нельзя. Проблема заключается в том, что вместо структурно-рекурсивной функции нужно писать хвосторекурсивную, а вместо двух строк — 12.

И не забываем что кроме примитивных случаев, эта короткая функция нам никак ни гарантирует что у нас не будет переполнения памяти.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>я там увидел 50-кратную разницу между самым медленным вариантом и prefilled list

Да, там измерения по всему треду разбросаны, так что я решил повторить замеры и сделать сводную таблицу.

or_modern = foldr (||) False

any_modern p = or_modern . map p

test n = any_modern (> n) [1..n]
    
n = 100000000 :: Int

main = print $ test n

open BatStd
open BatList (* BatSeq, BatEnum, BatLazyList *)

let or_modern = reduce (||) (* для LazyList использован fold_left *)

let any_modern p = or_modern -| map p

let n = 100_000_000

let test n = any_modern (fun x -> x > n) <| init n (fun x -> x);;

Printf.printf "%b\n" <| test n

win 7, core i7-860, ghc 7.0.3 x32, llvm 2.9, ocamlopt 3.13 x32 mingw

haskell -O2	0.101s
ocaml Enum	2.134s
ocaml Seq	3.294s
haskell -O0	5.222s
ocaml List	22.957s
ocaml LazyList	27.945s

Измерения не особо точные, конечно, но тут такие различия, что это и не важно.

Ну вот и судите теперь сами — стали бы вы в окамле списки использовать также широко, как в хаскеле?

P.S. как-то контринтуитивно, что Enum оказался быстрее Seq — я этот вопрос, думаю, еще провентилирую.

Здравствуйте, MigMit, Вы писали:

MM>А при чём тут foldr? В общем случае, он и в ленивом языке стек переполняет (если список длинный).

В общем случае да, но достаточно случаев, когда все будет работать нормально — для любой функции, которая ленива по второму аргументу. К ленивости списка это, впрочем, не имеет отношения — только к ленивости языка.

MM>Так речь, вроде, шла о том, что SML/NJ использует не обычный стек. А для чего ещё делать такую оптимизацию — я не особо понимаю.

Ну, анроллед функция с воркером, в который константные аргументы враппера передаются не через аргументы, обычно работает быстрее.

Здравствуйте, Klapaucius, Вы писали:

K>Я не понимаю, что вы подразумеваете под "использован в качестве стека".

Я подразумеваю смысл и способ использования структуры. Он относится не к языку, а к алгоритму. В одном алгоритме нам нужна последовательность элементов, и для нее мы можем задействовать разные структуры — список, массив, deque, queue.. В другом нужно отображение одних данных в другие, для него тоже можно задействовать разные структуры — список пар, массив пар, дерево, хэш-таблицу, еще что-то. А бывает, что алгоритм подразумевает использование стека, например при реализации автомата с магазинной памятью для парсинге чего-то. Для стека тоже можно использовать разные структуры — список, массив, еще что-то. Так же и строки — мы можем их представить массивом символов, списком символов, деревом из массивов, еще чем-то, но это все будут строки.
И вот я говорю, что когда в алгоритме нам нужен стек, для него хорошо подойдут списки. Но когда нам в алгоритме нужен стек, нам обычно не нужна операция map для него.

Здравствуйте, D. Mon, Вы писали:

DM>Я подразумеваю смысл и способ использования структуры. Он относится не к языку, а к алгоритму.

Ну значит вы подразумеваете то же, что и я. Если вы используете список, применяя к нему операции cons, head, tail — то способ такого использования струтуры "список" называется "использован в качестве стека". В чем тогда недопонимание-то заключается?

DM>В одном алгоритме нам нужна последовательность элементов, и для нее мы можем задействовать разные структуры — список, массив, deque, queue.

Список и мессив — структуры. Deque, queue — абстрактные типы. Что за структура такая deque? Deque — это набор операций, а структура может быть finger tree или этот, как бишь его? ну, gap buffer наоборот, когда не в центре буфера пустое пространство, а в начале и в конце. Последовательность элементов — это абстрактный тип данных, фактически расширяет deque добавляя еще операции, deque расширяет стек, а стек расширяет перечислитель, позволяющий только брать и убирать первый элемент. Вы же систематически путаете абстрактные типы данных — просто наборы операций и их конкретные реализации — структуры данных.

DM> В другом нужно отображение одних данных в другие, для него тоже можно задействовать разные структуры — список пар, массив пар, дерево, хэш-таблицу, еще что-то.

О! Тут вы уже их не путаете. Делаете успехи!

DM> А бывает, что алгоритм подразумевает использование стека, например при реализации автомата с магазинной памятью для парсинге чего-то. Для стека тоже можно использовать разные структуры — список, массив, еще что-то.

Правильно.

DM>Так же и строки — мы можем их представить массивом символов, списком символов, деревом из массивов, еще чем-то, но это все будут строки.

Совершенно верно.

DM>И вот я говорю, что когда в алгоритме нам нужен стек, для него хорошо подойдут списки.

Все правильно.

DM>Но когда нам в алгоритме нужен стек, нам обычно не нужна операция map для него.

Ну и с чего вы это взяли? Видели когда-нибудь код, в котором встречается fold и map одновременно? Вычисление модуля вектора, например? Для операции fold нужны только стековые операции. Значит перед вами реализация алгоритма который требует поддержки стековых операций и в котором применяется map.

Вы сейчас, конечно, пуститесь в объяснения, что говорили "обычно". Но в этом направлении можете разговор не развивать — предупреждаю сразу. Или обосновываете что "списки не нужны" или заканчиваем разговор, потому что "обычно не нужны" подавляющее большинство структур данных и это никак не является оправданием для падучих функций, которые с ними работают.

Здравствуйте, FR, Вы писали:

FR>Не важно, области применения у них сильно пересекаются с областью применения
FR>ленивых списков.

Сила пересечения в том, что область применения ленивых списков полностью их в себя включает. Но область применения у них мизерная — единственный случай, фактически, это связывание функций в простой линейный конвейер. Шаг влево — шаг вправо и Seq выпадает вообще из-за взорвавшейся асимптотической сложности, а с Enum начинается закат солнца вручную.

Здравствуйте, FR, Вы писали:

FR>В том то и дело что писать обычно не нужно, такие функции все-таки большей частью должны быть библиотечными.

Должны, но не будут. В библиотеке же они не волшебным образом появятся — их кто-то будет писать и поддерживать. И если они будут писать и поддерживать по 12 вместо двух — у вас седая борода отрастет, пока вы их дождетесь. Скудный батареечный набор, например, подоспел всего-то лет через десять после выкатывания окамла из ангара.
Комбинации библиотечных функций тоже придется реализовывать, осуществляя ручной инлайн и фьюжн — ведь без оптимизации сочетания "базовых" функций ужасно тормозят, а тормозной код часто приходится переписыватьв код нетормозной.

FR>Так что по моему если нам скажем дан библиотекой тип данных и все базовые ФВП которые его обслуживают, то
FR>проблема возможно и не полностью но решена. Пример тот же Enum из батареек.

Это в том случае, когда базовый набор полон, а элементы базового набора хорошо комбинируются. В реальности же нет ни того, ни другого.

Здравствуйте, FR, Вы писали:

FR>И не забываем что кроме примитивных случаев, эта короткая функция нам никак ни гарантирует что у нас не будет переполнения памяти.

Каких еще примитивных случаев? Какого переполнения памяти? Вы о чем вообще?

Здравствуйте, Klapaucius, Вы писали:

K>Сила пересечения в том, что область применения ленивых списков полностью их в себя включает. Но область применения у них мизерная — единственный случай, фактически, это связывание функций в простой линейный конвейер. Шаг влево — шаг вправо и Seq выпадает вообще из-за взорвавшейся асимптотической сложности, а с Enum начинается закат солнца вручную.

Угу и эта мизерная область применения чуть менее чем полностью покрывает то что называется функциональным стилем программирования

Здравствуйте, Klapaucius, Вы писали:

K>Должны, но не будут. В библиотеке же они не волшебным образом появятся — их кто-то будет писать и поддерживать. И если они будут писать и поддерживать по 12 вместо двух — у вас седая борода отрастет, пока вы их дождетесь. Скудный батареечный набор, например, подоспел всего-то лет через десять после выкатывания окамла из ангара.
K>Комбинации библиотечных функций тоже придется реализовывать, осуществляя ручной инлайн и фьюжн — ведь без оптимизации сочетания "базовых" функций ужасно тормозят, а тормозной код часто приходится переписыватьв код нетормозной.

Слишком много предположений, хотя во многом ты и прав.

FR>>Так что по моему если нам скажем дан библиотекой тип данных и все базовые ФВП которые его обслуживают, то
FR>>проблема возможно и не полностью но решена. Пример тот же Enum из батареек.

K>Это в том случае, когда базовый набор полон, а элементы базового набора хорошо комбинируются. В реальности же нет ни того, ни другого.

В реальности если нужна максимальная оптимизация все-равно и в хасклеле и окамле будет модуль на Си/С++.
Хотя учитывая область применения до реальности доходит редко

Здравствуйте, Klapaucius, Вы писали:

FR>>И не забываем что кроме примитивных случаев, эта короткая функция нам никак ни гарантирует что у нас не будет переполнения памяти.

K>Каких еще примитивных случаев? Какого переполнения памяти? Вы о чем вообще?

Тут полный форум вопросов о том почему хаскель жрет память и тормозит

Здравствуйте, FR, Вы писали:

FR>Угу и эта мизерная область применения чуть менее чем полностью покрывает то что называется функциональным стилем программирования

Ну это явная неправда. Функциональное программирование — это область более широкая. Там, представьте себе, широко используется рекурсия, например. Я уже в этом треде советовал переписать на окамле бенчмарк из статьи про clean

Автор: D. Mon
Дата: 19.08.11

primes = 2:3:filter isPrime [4..]
isPrime x = all (/=0) . map (x `mod`) . takeWhile ((<=x).(^2)) $ primes
main = print . length . takeWhile (<=5000000) $ primes

после этого сразу понятнее станет, о чем я говорил.

Здравствуйте, FR, Вы писали:

FR>В реальности если нужна максимальная оптимизация все-равно и в хасклеле и окамле будет модуль на Си/С++.

Я говорю сейчас не о 10% кода, где нужна максимальная оптимизация, а о 70% кода, которые дожны работать с разумной скоростью, а не тормозить в сотни раз на ровном месте.
Еще процентов для 20 кода, соглашусь, скорость значения вообще не имеет. Но идиоматический код хотелось бы писать не в 20% случаев, а в 90%.

Здравствуйте, Klapaucius, Вы писали:

K>Должны, но не будут. В библиотеке же они не волшебным образом появятся — их кто-то будет писать и поддерживать. И если они будут писать и поддерживать по 12 вместо двух — у вас седая борода отрастет, пока вы их дождетесь. Скудный батареечный набор, например, подоспел всего-то лет через десять после выкатывания окамла из ангара.
K>Комбинации библиотечных функций тоже придется реализовывать, осуществляя ручной инлайн и фьюжн — ведь без оптимизации сочетания "базовых" функций ужасно тормозят, а тормозной код часто приходится переписыватьв код нетормозной.

кстати,

----------------------------------------------
--              map     
----------------------------------------------

-- | 'map' @f xs@ is the list obtained by applying @f@ to each element
-- of @xs@, i.e.,
--
-- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
-- > map f [x1, x2, ...] == [f x1, f x2, ...]

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

-- Note eta expanded
mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
{-# INLINE [0] mapFB #-}
mapFB c f x ys = c (f x) ys

-- The rules for map work like this.
-- 
-- Up to (but not including) phase 1, we use the "map" rule to
-- rewrite all saturated applications of map with its build/fold 
-- form, hoping for fusion to happen.
-- In phase 1 and 0, we switch off that rule, inline build, and
-- switch on the "mapList" rule, which rewrites the foldr/mapFB
-- thing back into plain map.  
--
-- It's important that these two rules aren't both active at once 
-- (along with build's unfolding) else we'd get an infinite loop 
-- in the rules.  Hence the activation control below.
--
-- The "mapFB" rule optimises compositions of map.
--
-- This same pattern is followed by many other functions: 
-- e.g. append, filter, iterate, repeat, etc.

{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g) 
  #-}

и это у меня очень старая версия исходников, в новой списки вроде стали гораздо быстрее

Здравствуйте, Klapaucius, Вы писали:

K>Ну это явная неправда. Функциональное программирование — это область более широкая. Там, представьте себе, широко используется рекурсия, например. Я уже в этом треде советовал переписать на окамле бенчмарк из статьи про clean

Автор: D. Mon
Дата: 19.08.11

K>

K>primes = 2:3:filter isPrime [4..]
K>isPrime x = all (/=0) . map (x `mod`) . takeWhile ((<=x).(^2)) $ primes
K>main = print . length . takeWhile (<=5000000) $ primes
K>

K>после этого сразу понятнее станет, о чем я говорил.

Мемоизация спасет.

Здравствуйте, Klapaucius, Вы писали:

DM>>Я подразумеваю смысл и способ использования структуры. Он относится не к языку, а к алгоритму.

K>Ну значит вы подразумеваете то же, что и я. Если вы используете список, применяя к нему операции cons, head, tail — то способ такого использования струтуры "список" называется "использован в качестве стека". В чем тогда недопонимание-то заключается?

Вы все перевернули с ног на голову. Вы идете от конечных операций, а я от алгоритма. Я говорю: "список" называется "использован в качестве стека", когда исходный алгоритм оперирует стеком, а список выбран в качестве реализации стека. Если список выбран в качестве реализации множества или строки, то это не "использован в качестве стека".

Покажите мне алгоритм, где используется стек (не уточняя, какой структурой данных он представлен), и к этому стеку применяют map.

DM>>Но когда нам в алгоритме нужен стек, нам обычно не нужна операция map для него.

K>Ну и с чего вы это взяли? Видели когда-нибудь код, в котором встречается fold и map одновременно?

Да.

K> Для операции fold нужны только стековые операции. Значит перед вами реализация алгоритма который требует поддержки стековых операций и в котором применяется map.

Нет.
Использует ли алгоритм обращения списка адресную арифметику? По-моему, нет. По-вашему, да.

Здравствуйте, FR, Вы писали:

FR>Тут ты делаешь совершенно необоснованное допущение, никаких тормозов тем более в сотни раз для такого "70% кода" на окамле не наблюдается.

Смотрим здесь

Автор: Klapaucius
Дата: 06.12.11

. Код типичный? Типичный — сами же говорите, что ФП чуть менее, чем полностью из такого и состоит. Место ровное? Ровное. Тормоза есть? Есть. В хаскеле, разумеется, не все идеально, но там проблемы осознаются как проблемы и в здоровом темпе исправляются. Реакцию окамлиста на проблемы мы в этом треде видели — "списки не нужны".

FR>Возможно ты хочешь писать на окамле используя идиомы хаскеля, тогда да проблемы будут.

Не идиомы хаскеля, а идиомы функционального программирования.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>в новой списки вроде стали гораздо быстрее

Это не списки стали быстрее, это оптимизатор от лишних списков избавляется.
Но к хаскелю у меня таких претензий и нет. Там как раз успехи с оптимизацией таких комбинаций базовых функций неплохие. И, главное, работы ведутся (хотя многолетнее равнодушие к #915 особо не радует).

Здравствуйте, BulatZiganshin, Вы писали:

BZ>это я к тому, что там не оптимизатор, а саму реализацию совершенствуют. и по сравнению с нынешней реализацией списков в ghc — те 12 строк, которые хотя бы понятны с первого взгляда, представляют собой детский лепет

Это "совершенствование реализации" нужно для устранения промежуточных списков. На работоспособности map — основной теме разговора это никак не сказывается.
Функционал соотвествующий коду правил перезаписи и промежуточных функций для них в окамловской библиотеке вовсе отсутствует, так что и сравнивать не с чем.

BZ>а если ты хочешь сравнить честную реализацию ленивых списков в ghc и ocaml — то лучше напиши их обе ручками в 2 строки

А смысл? Я для того и замерил версию без оптимизации. Никакой фьюжн там, разумеется не сработал. И все рано в разы быстрее, чем окамловские списки. Разница со всякими Seq и Enum, в том числе и за счет того, что без оптимизаций Int и Bool не анбоксятся и полиморфные функции не оптимизируются до праймопов.

Здравствуйте, Klapaucius, Вы писали:

FR>>Тут ты делаешь совершенно необоснованное допущение, никаких тормозов тем более в сотни раз для такого "70% кода" на окамле не наблюдается.

K>Смотрим здесь

Автор: Klapaucius
Дата: 06.12.11

. Код типичный? Типичный — сами же говорите, что ФП чуть менее, чем полностью из такого и состоит. Место ровное? Ровное. Тормоза есть? Есть.

Код типичный, но доведенный до абсурда практически. И явно 70% кода к подобному при всем желании не отнести.

K>В хаскеле, разумеется, не все идеально, но там проблемы осознаются как проблемы и в здоровом темпе исправляются. Реакцию окамлиста на проблемы мы в этом треде видели — "списки не нужны".

Списки конечно нужны, но и делать выводы на основе синтетического теста со списком с "типичной" длиной в сто миллионов элементов тоже не стоит.

FR>>Возможно ты хочешь писать на окамле используя идиомы хаскеля, тогда да проблемы будут.

K>Не идиомы хаскеля, а идиомы функционального программирования.

Скорее идиомы ленивого ФП.

Здравствуйте, FR, Вы писали:

FR>Мемоизация спасет.

Ну это очевидно. Теперь понятно, почему Seq не годится, а с Enum будут закаты вручную?

Здравствуйте, Klapaucius, Вы писали:

FR>>Мемоизация спасет.

K>Ну это очевидно. Теперь понятно, почему Seq не годится, а с Enum будут закаты вручную?

Это если не учитывать игру вне правил http://martin.jambon.free.fr/309/pa_memo.ml.html

Здравствуйте, FR, Вы писали:

FR>Код типичный, но доведенный до абсурда практически.

Если вам факт не нравится — это еще не означает, что это абсурд. Это, разумеется, благоприятный случай для хаскеля (не для всех функций фьюжн хорошо работает), и он, в какой-то степени специально подобран — точно как и код из этого сообщения

Автор: D. Mon
Дата: 03.12.11

, вот только максимально благоприятный для окамла случай как-то отрывом не впечатляет.

FR>И явно 70% кода к подобному при всем желании не отнести.

Я за числа цепляться не собираюсь. А принципиально тут ничего не поменять. Ведь и 30% идиоматического кода лучше, чем 20% не обязательно 90.

FR>Списки конечно нужны, но и делать выводы на основе синтетического теста со списком с "типичной" длиной в сто миллионов элементов тоже не стоит.

Длина в 100 миллионов для того, чтоб можно было измерять производительность утилитой time. А оверхед от комбинирования базовых функций будет накапливаться, суммироваться и замедлять все, если, конечно, функции комбинировать.

FR>Скорее идиомы ленивого ФП.

Не бывает никакого ленивого ФП. Бывают идиомы ФП и языки в которых поддерживается больше или меньше таких идиом. Ну и разное качество поддержки, разумеется.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>мне казалось, что ты критиковал производительность ленивых списков тоже?

Я для того и замерил версию без оптимизации. Никакой фьюжн там, разумеется не сработал. И все рано в разы быстрее, чем окамловские списки.

BZ>это не отменяет того факта, что ghc добирался до нынешней произхводительности списков два десятка лет и нынешняя скорость обусловлена не мифическими достоинствами хаскела, а громадной работой над компилятором и библиотекой.

Это и есть реальное достоинство хаскеля, а не какое-то там "мифическое". Впрочем, до нынешней производительности именно списков — он не 20 лет добирался. На этом фронте все прорывы уже довольно давние.

BZ>но почему-то специальный фреймворк аж в 12 строк, заменяющий стандартные строки в окамле, ты считаешь огромной проблемой, а куда более навороченный фреймворк, на разработке которого люди пишут целые научные статьи, в хаскеле ты не замечаешь

Еще раз, для того, чтоб обычный map работал никакие "фреймворки" не нужны. Для этого достаточно, в случае ghc, эффективной реализации ленивости (это, разумеется, большая заслуга разработчиков рантайма). Но от разработчиков библиотек для этого ничего не требуется.
"Фреймворки", про которые статьи пишут, делают совсем не ту работу, которая обсуждается в первоначальном посте. Никаких аналогов этих "фреймворков" для окамла нет, а значит и сравнивать нечего.

Здравствуйте, Klapaucius, Вы писали:


K>Если вам факт не нравится — это еще не означает, что это абсурд. Это, разумеется, благоприятный случай для хаскеля (не для всех функций фьюжн хорошо работает), и он, в какой-то степени специально подобран — точно как и код из этого сообщения

Автор: D. Mon
Дата: 03.12.11

, вот только максимально благоприятный для окамла случай как-то отрывом не впечатляет.

Но вполне позволяет писать идиомотично для окамла.

K>Я за числа цепляться не собираюсь. А принципиально тут ничего не поменять. Ведь и 30% идиоматического кода лучше, чем 20% не обязательно 90.

Угу, но уже не так впечатляет.

K>Длина в 100 миллионов для того, чтоб можно было измерять производительность утилитой time. А оверхед от комбинирования базовых функций будет накапливаться, суммироваться и замедлять все, если, конечно, функции комбинировать.

Тут 100 лямов принципиальны для строгого списка, тормоза возникают из-за памяти, столько в кеш процессора не лезет, вот иллюстрация:

open BatStd
open BatList (* BatSeq, BatEnum, BatLazyList *)

let or_modern = reduce (||) (* для LazyList использован fold_left *)

let any_modern p = or_modern -| map p

let n = 1_000

let test n = any_modern (fun x -> x > n) <| init n (fun x -> x)

for i = 1 to 100_000 - 1 do
  ignore(test n)
  done

let r = test n

let _ = Printf.printf "%b\n" <| r

>time -p ./orig_tst
false
real 23.33
user 20.54
sys 2.64
>Exit code: 0

>time -p ./loop_tst
false
real 3.59
user 3.56
sys 0.01
>Exit code: 0

Разница очень прилична.

FR>>Скорее идиомы ленивого ФП.

K>Не бывает никакого ленивого ФП. Бывают идиомы ФП и языки в которых поддерживается больше или меньше таких идиом. Ну и разное качество поддержки, разумеется.

В теории да, на практике нет.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>т.е. производительность ты тоже критиковал, нет?

Критиковал. И именно поэтому сделал замер без оптимизаций, чтоб показать превосходство даже в случае отключения дефорестации и сравнивать именно списки, а не списки с их отсутствием. Но это не помогло.

BZ>а разхница в скорости объясняется имхо тем, что ghc сейчас вышел на использование оптимизирующих С-компиляторов,

GHC, вообще-то, наоборот ушел от использования C-компиляторов.

BZ>и тем что ленивые вычисления в нём встроены, а не реализованы средствами самого языка

Ну, технически, поддержка со стороны языка для явно аннотированной ленивости в виде синтаксических расширений языка в окамле есть. Но поддержка со стороны рантайма просто никакая — в этом и разница.

BZ>ага. ты полагаешь, что использование llvm на ней никак не сказалось?

Я не полагаю, а из опыта знаю, что не сказалось. Заметная польза от LLVM появляется при числодроблении, работе с массивами и вообще в коде, работающем с регистрами в уютном цикле, а не бьющемся головой о стену памяти. Т.е. польза появляется когда от списков избавились. Коду из моего бенчмарка без дефорестации -fllvm производительности не добавляет.

BZ>а кроме начального поста в треде никаких других не было, да?

Было, конечно, но это не повод смешивать разные ветви обсуждения.

BZ>давай всё же вспомним — ты считаешь проблемой 12 тривиальных строк на ml, решающих проблему переполнения стёка, а целые научные статьи, решающие проблему скорости на хаскеле — это так, пустяки, дело житейское. видимо от того, что оно решает другую задачу, эти строки перестали нуждаться в поддержке, и их может реализовать каждый школьник, имеющий десяток публикаций в Science

Да, я считаю, что 12 строк вместо 2 — это проблема.
Давайте стравним реализацию дефорестации списков в GHC.Base с аналогичными реализациями из библиотек других языков — я только за. Вы какие знаете?
А то, что реализация на хаскеле имеет больше строк чем отсутствующая реализация на окамле — это очевидно. На то она и отсутствующая.
Если же вы под аналогом хаскельной дефорестации понимаете использование всяких Seq/Enum — то сравнение выйдет явно не в пользу окамла и по объему кода и по его сложности и по удобству интерфейса и, особенно, по производительности ради которой все и затевалось.
Статьями тоже никого пугать не надо. По этой теме там ничего особо сложного не написано.

Здравствуйте, FR, Вы писали:

FR>Но вполне позволяет писать идиомотично для окамла.

Идиоматично для окамла — легко верю. Это ведь я летом отставивал точку зрения, что батарейки написаны на идиоматичном окамле, а в фп-стиле писать на нем тяжело и в перспективе плохо заканчивается. А со мной спорили.

K>>Я за числа цепляться не собираюсь. А принципиально тут ничего не поменять. Ведь и 30% идиоматического кода лучше, чем 20% не обязательно 90.
FR>Угу, но уже не так впечатляет.

Ну, меня 30% впечатляет в полтора раза сильнее чтом в 20%. Особенно, когда альтернатива — "списки не нужны".

FR>Тут 100 лямов принципиальны для строгого списка, тормоза возникают из-за памяти, столько в кеш процессора не лезет, вот иллюстрация:

Это и без иллюстрации понятно. Какие еще причины для окамловских списков торомозить почти как окамловским ленивым спискам? А на почве ненужности списков не влезающих в кеш вы можете объединиться с D.Mon — тем более, что размеры стека и кеша сопоставимы (второй даже и меньше, обычно). Серьезная заявка на победу!

K>>Не бывает никакого ленивого ФП. Бывают идиомы ФП и языки в которых поддерживается больше или меньше таких идиом. Ну и разное качество поддержки, разумеется.
FR>В теории да, на практике нет.

Нет такой теории. То, о чем я говорил — это как раз практика.

Здравствуйте, FR, Вы писали:

FR>Это если не учитывать игру вне правил http://martin.jambon.free.fr/309/pa_memo.ml.html

Боюсь, что такое решение вам в этих случаях не особенно поможет. Ничего особо "вне правильного" я в нем не заметил, правда. Обычное окамловское решение.

Здравствуйте, Слоноежик, Вы писали:

С>Там в хаскеле 7.0.3 тупо нету никакого списка. Компилятор (а не рантайм) тупо список [1..n] с цикл преобразует. Тоже мне рокет саенс. А ghc 6.12.3, где он этого не умеет, хаскель примерно на 25% медленнее.

Да, если работает оптимизация то никакого списка нет. Но я специально измерил и без оптимизации. GHC 6.12, кстати, от 7.0 в этом плане ни в чем не отличается.

С>В окамле нету такой оптимизации. Но если надо, я там вместо ленивого списка [1..n] я могу написать тупой императивный for и не париться по поводу, есть ли в компиляторе для меня подобная оптимизация или нету.

Согласен на 100%. Я тут летом о том и писал, что идиоматичный окамл — это писать императивный for. Но со мной окамлисты спорили. Приятно видеть окамлиста, который реалистично смотрит на вещи, а не витает в эмпиреях, представляя, что на окамл можно безнаказанно писать ФП-код.

Здравствуйте, D. Mon, Вы писали:

DM>Покажите мне алгоритм, где используется стек (не уточняя, какой структурой данных он представлен), и к этому стеку применяют map.

DM>Использует ли алгоритм обращения списка адресную арифметику? По-моему, нет. По-вашему, да.

Вы уже сами с собой договоритесь, где вы имеете в виду алгоритм, а где его реализацию на конкретном языке. Потому, что ни один алгоритм "операции map" не требует — большинство записываются на некоем псевдоязыке без всяких мапов. Но при реализации алгоритмов мап, разумеется, присутствовать может. Я вам привел практически полезный алгоритм не требующий никаких операций кроме стековых и использующий при реализации map. Что вам еще нужно-то? Или вы будете на все отвечать "нет", пока я не соглашусь, что списки и мап не нужны? Ну так это малопермпективное направление разговора.

Здравствуйте, Слоноежик, Вы писали:

С>Но спорят то тут о том, что хаскель всегда быстрее

Нет, не всегда.

С>Приятно конечно писать такой код, и особенно приятно, когда он оптимизируется нормально, но только слишком уж специальные условия должны быть, чтобы эта оптимизация сработала.

Я бы не сказал, что условия слишком уж специфические. Для foldr/build плохой консьюмер — левая свертка и производные функции. Для stream fusion плохой продьюсер — concatMap.

С>А когда она не сработает, то тут у хаскеля тоже не всё хорошо.

Но даже если она в каких-то случаях не срабатывает — в других-то она сработает и это положительно скажется на производительности кода.

С> и что там мегакомпилятор с которым можно писать код и не думать, и всё равно он будет быстрее чем если писать код на окамле и думать.

Это, конечно, упрощение. Моя позиция выражается так: GHC оптимизирует высокоуровневый код лучше ocamlopt и, не в последнюю очередь потому, что в хаскель-комьюнити считается, что нужно оптимизировать еще лучше и ведутся соотвествующие работы. В окамлокомьюнити, с другой стороны, считается, что "это все не нужно". В результате код на окамле получается более низкоуровневым, сложным и многословным — производительность-то имеет значение. Но когда на это указываешь — окамлисты почему-то обижаются и с еще большим жаром продолжают настаивать, что что-то "ненужно".

Здравствуйте, Слоноежик, Вы писали:

С>Более правильно сказать так — GHC оптимизирует код на хаскеле лучше чем осаmlopt оптимизирует код на хаскеле, зачем то переведённый на ocaml.

Можно и так сказать — исключительно чтоб пилюлю подсластить. Смысл от этого не поменяется.

С>И при этом обычно забывают что хаскель немножко ленивый, а ocaml немножко энергичный, и поэтому один и тот же алгоритм на хаскеле и на окамле будет выглядеть по разному.

Ну, об этом в головном посте треда и написано. И продемонстровано как код делающий одно и то же выглядит в разных языках и библиотеках.

С>И оба будут при этом высокоуровневыми и быстрыми.

К сожалению, высокоуровневыми оба не будут. Более-менее быстрыми да, будут.

С>И даже будут при этом будут немногословными, кроме самых клинических случаев.

Насколько клиничны случаи работы со списками?

С>И вопрос — а зачем допустим оптимизировать Ленивые списки типа [1..n] в энергичном языке, где их исползуют 3 человека, и те пишут в основном не на окамле а на хаскеле.

Оптимизировать "только ленивые списки типа [1..n]" особого смысла нет. Имеет смысл оптимизировать сборку одной функции из других, в чем, собственно, функциональное программирование и зуключается. список в данном случае просто control-structure.

С>то что на нём нельзя писать как на хаскеле, это далеко не главная из них.

Это не сама проблема — это следствие проблем.

С>P.P.S. Не стоит призывать Сергея Губанова в эту тему.

Он-то здесь при чем?

Здравствуйте, Klapaucius, Вы писали:

DM>>Покажите мне алгоритм, где используется стек (не уточняя, какой структурой данных он представлен), и к этому стеку применяют map.

K>Вы уже сами с собой договоритесь, где вы имеете в виду алгоритм, а где его реализацию на конкретном языке.

Я везде в этой ветке про стеки и map имею в виду алгоритм.

K>Потому, что ни один алгоритм "операции map" не требует — большинство записываются на некоем псевдоязыке без всяких мапов.

В этом псевдоязыке оно может называться "преобразование", "морфизм" или еще как. Смысл останется тем же — применение некоего преобразования поэлементно.

K> Я вам привел практически полезный алгоритм не требующий никаких операций кроме стековых и использующий при реализации map.

Где? Модуль вектора? Нет там никакого стека.

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, Слоноежик, Вы писали:



С>>И при этом обычно забывают что хаскель немножко ленивый, а ocaml немножко энергичный, и поэтому один и тот же алгоритм на хаскеле и на окамле будет выглядеть по разному.
K>Ну, об этом в головном посте треда и написано. И продемонстровано как код делающий одно и то же выглядит в разных языках и библиотеках.
Ага — написан кода на хаскеле, и код на хаскеле, но зачем то написанный в синтаксисе ocaml-а. Nice move

С>>то что на нём нельзя писать как на хаскеле, это далеко не главная из них.
K>Это не сама проблема — это следствие проблем.
Странно, почему никто не считает проблемой что граматика китайского отличайется от граматики японского, и не кричит на форумах что я пишу на японском, как на китайском, но меня никто не понимает.

С>>P.P.S. Не стоит призывать Сергея Губанова в эту тему.
K>Он-то здесь при чем?
Тема скатывается в очередной сезон Синтаксического Оверхеда. Только вместо паскаля тут хаскель.

Здравствуйте, D. Mon, Вы писали:

K>> Я вам привел практически полезный алгоритм не требующий никаких операций кроме стековых и использующий при реализации map.
DM>Где? Модуль вектора? Нет там никакого стека.

Ну вот я и говорю, что не понимаю, что вы подразумеваете под "алгоритм импользует стек". Я подразумеваю под этим "алгоритм использует стековые операции". Если алгоритм обходится только стековыми операциями — он использует стек. Не очередь, не словарь, не последовательность. Стек. Для того, чтоб посчитать модуль вектора — стековых операций достаточно. Но вам их, по какой-то причине, не достаточно — вот я и спрашиваю, в который раз уже, что именно вам не хватает? Вы разницу между моим и вашим, не названным, определением назвать отказываетесь, а я что, по-вашему телепат?

Здравствуйте, Слоноежик, Вы писали:

С>Ага — написан кода на хаскеле, и код на хаскеле, но зачем то написанный в синтаксисе ocaml-а. Nice move

Я, собственно, достаточно ясно написал в первом посте что я думаю о коде "на хаскеле в синтаксисе окамл" из std-lib.

С>Странно, почему никто не считает проблемой что граматика китайского отличайется от граматики японского, и не кричит на форумах что я пишу на японском, как на китайском, но меня никто не понимает.

Я не языковед и никак не могу это прокомментировать. Я программист и отлично понимаю разницу в уровне между разными языками программирования.

С>Тема скатывается в очередной сезон Синтаксического Оверхеда.

Сезон синтаксического оверхеда был бы, если бы сравнивались функции отличающиеся только синтаксически, т.е.

map _ []     = []
map f (x:xs) = f x : map f xs

,

fun map f []      = []
  | map f (x::xs) = f x::map f xs

и

let rec map f = function
    [] -> []
  | a::l -> let r = f a in r :: map f l

Но я-то как раз сравниваю функции, главные различия между которыми совсем не синтаксические.

Здравствуйте, D. Mon, Вы писали:

DM>Проблема в том, что долгое время над окамлом работало полчеловека из INRIA, комьюнити никак не участвовало в разработке компилятора и оптимизаций в нем по чисто бюрократическим причинам.

Кстати, интересный вопрос, как думаете, почему самым популярным ML-ем стал окамл, а не SML, если борократы комьюнити улучшать реализацию не давали? Что, к тому времени, когда NEC выпустил mlton на свободу (это ведь был где-то 99-2000 год?) комьюнити уже слишком большую энерцию набрало, чтоб переметнуться? Нет, я отдаю себе отчет в том, что ocaml и sml языки не особенно похожие, но основные принципы-то у них общие. Это не хаскель, где надо сознание перестраивать и все что выучил — обратно разучивать.

DM>В итоге вместо заявленной темы (про строгость и списки) вы скатываетесь к сравнению двух конкретных компиляторов разных языков с очень разными историями. Смысл?

К обсуждению производительности мы пришли двумя путями.
В первом случая я заговорил о производительности, когда объяснял Булату, почему использовать списки в окамле — плохая идея. Он-то, как и всякий хаскелист, вероятно, в первую очередь использовал их как control-structure для связывания функций. В хаскеле это относительно дешево, но в окамле-то ситуация другая.
Во втором случае я упоминул производительность, когда отвечал на возражение, что 12-истрочная функция вместо двухстрочной — не проблема. Проблема в том числе и потому, что дешево комбинировать готовые функции не получится, а значит придется фьюзить их вручную, т.е. самому писать страшные многострочные функции с хаками.

Здравствуйте, Klapaucius, Вы писали:

FR>>Но вполне позволяет писать идиомотично для окамла.

K>Идиоматично для окамла — легко верю. Это ведь я летом отставивал точку зрения, что батарейки написаны на идиоматичном окамле, а в фп-стиле писать на нем тяжело и в перспективе плохо заканчивается. А со мной спорили.

Ты не прав.
Для своего класса, энергичного жестко статически типизированного языка, окамл очень хорошо поддерживает ФП стиль.

FR>>Тут 100 лямов принципиальны для строгого списка, тормоза возникают из-за памяти, столько в кеш процессора не лезет, вот иллюстрация:

K>Это и без иллюстрации понятно. Какие еще причины для окамловских списков торомозить почти как окамловским ленивым спискам? А на почве ненужности списков не влезающих в кеш вы можете объединиться с D.Mon — тем более, что размеры стека и кеша сопоставимы (второй даже и меньше, обычно). Серьезная заявка на победу!

Я думаю не стоит так нервничать, здоровье оно дороже любых списков.

Здравствуйте, Klapaucius, Вы писали:

FR>>Это если не учитывать игру вне правил http://martin.jambon.free.fr/309/pa_memo.ml.html

K>Боюсь, что такое решение вам в этих случаях не особенно поможет. Ничего особо "вне правильного" я в нем не заметил, правда. Обычное окамловское решение.

Ты похоже главного не заметил это модуль для Camlp4 так что поможет, притом практически без усложнений в прикладном коде.

Здравствуйте, FR, Вы писали:

FR>Ты не прав.
FR>Для своего класса, энергичного жестко статически типизированного языка, окамл очень хорошо поддерживает ФП стиль.

Ваше слово против реального кода на окамле? Ничего личного, но я верю коду.
Была, впрочем, оговорка про энергичность... Нет, даже и со скидкой на энергичность — все равно неубедительно.

FR>Я думаю не стоит так нервничать, здоровье оно дороже любых списков.

Ну так а я о чем? Глубже дышать надо.