> хрена се. Это при каких задачах такое возникает?

Да хоть в каких, длина абсолютного пути 4095 байт, значит на это надо и рассчитывать.

> до меня, кажется, дошло. ты имеешь в виду определение монады через fmap/join?

вроде того... например, для Eq ведь есть методы (==) (/=), определенные друг через друга, вручную достаточно указать один

просто иногда возникает диссонанс: на фоне общей consistency небольшие мелочи могут раздражать, ибо выделяются)

Рассчитывать надо на расширяемость, а не на 4095 байт

Согласен, хотел написать «минимум на это» и чото затупил

например, для Eq

ну, здесь несколько не тот случай. или твой исходный вопрос был задан неверно: интересен не сам класс Functor, а зависимость Functor => Monad (кстати, в Haskell 1.4 вроде бы такая зависимость была)

на фоне общей consistency небольшие мелочи могут раздражать, ибо выделяются)

к счастью, наиболее значимые - исправляются

1000 это очень мало. Я потестил, тупо в с++ функция:

int f(x)

{

if{f (x > 0) return f(x-1)+rand() % 16;

else return 0;

}

функция начинает падать где то в районе x=65000. rand пришлось добавлять потому что иначе шибко умный компилятор оптимизировал выражение ( return f(x-1)+1 работало даже на x=1млн).

тьфу, неправильно скопировал. Вот тело функции:

if (x > 0)

return f(x-1)+(rand() % 16);

else return 0;

> также смущает отделение functor в отдельный класс: ведь для монады можно было бы сделать fmap по умолчанию

Исторически сложилось.

Простите, что вмешиваюсь. А каковы ныне доходы у знатоков Haskell? В чем профит? Или это как изучение эсперанто?

> ну, здесь несколько не тот случай. или твой исходный вопрос был задан неверно: интересен не сам класс Functor, а зависимость Functor => Monad (кстати, в Haskell 1.4 вроде бы такая зависимость была)

Была? Как я понял из typeclassopedia, то, что этой зависимости нет (вернее, должно быть Applicative => Monad) - исключительно исторические причины: монады появились в Хаскелле раньше функторов. Но, может, в будущем пофиксят.

Кстати. Если уж тебя так сильно пугает переполнение стека, что мешает сделать так:

F(int n, ..... (другие параметры)) { if (n == 0) return; .... F(n-1, ......) }

тогда при вызове F(N,....) глубина рекурсии будет ограничена N.

>каковы ныне доходы у знатоков

Кому доходы - в наркотиками, или порнухой заниматься. Профит в мозгах.

Зачет!

А про статику динамику там одинаковая картинка.

> Простите, что вмешиваюсь. А каковы ныне доходы у знатоков Haskell? В чем профит? Или это как изучение эсперанто?

Профит прямой. Знания можно приложить при программировании на Scala (Java) и F# (.NET). Там без хаскеля сложно понять некоторые вещи.

> Добавлением еще одного аргумента. Механизм аналогичный развороту ункции из просто рекурсивной в хвосторекурсивную.

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

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

чтобы не писать чушь про структуры данных в функциональных языках можно почитать книжку Криса Окасаки =)

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

> чтобы не писать чушь про структуры данных в функциональных языках можно почитать книжку Криса Окасаки =)

ну так поведай, как обойтись без log n

> Знания можно приложить при программировании на Scala (Java) и F# (.NET).

Востребованность на рынке которых немногим более чем у хаскелля, а популярность (по TIOBE) так и меньше.

И кому этот хаскель нужен, кроме как ПроФФессору, дабы самоутвердиться?

>какой-нить контейнер, который мутировать нельзя, и поэтому он при вставке нового элемента копирует log n узлов дерева?

Вообще иммутабельные контейнеры делают для того чтобы _не_ копировать ничего. Ман клевые картинки обяснения списковых структур лиспа и добавление в голову.

ну тогда поздравляю

Рано.

Хаскелл прекрасен как proof-of-concept, исследовательский проект и язык для обучения ФП.

А вот практического применения нет. Не говоря уже о серьезном рынке труда.

> А вот практического применения нет. Не говоря уже о серьезном рынке труда.

Оно уществует в ограниченном виде. Но не потому что язык плохой а потому что a) за ним нет мощной платформы и корпорации b) в ВУЗах учат «сям и делфям». Потому эти грибы плохо раснут.

ну так поведай, как обойтись без log n

Finger Tree, Data.Sequence

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

И кому этот хаскель нужен, кроме как ПроФФессору, дабы самоутвердиться?

из того, что могу сказать по личному опыту - инвестиционным банкам

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

Поведайте еще почему за 20 лет ни одна корпорация не вложилась в серьезную раскрутку хаскелла.

>Ман клевые картинки обяснения списковых структур лиспа и добавление в голову.

я так понял, ты из детского сада еще не выбрался, вместе с qnikst

при добавлении в голову время доступа будет O(n)

> из того, что могу сказать по личному опыту - инвестиционным банкам

Скольки банкам: одному, двум?

А сколько миллионов банков сидит на джаве и не думает слезать?

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

Легко: создается два списка - список посещенных каталогов и список каталогов которые надо посетить. В список каталогов, которые надо посетить помещается корневая директория. Затем начинается цикл:

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

2. Поместить выбранную директорию в список посещенных каталогов. Считать все поддиректории выбранной директории и поместить в список каталогов, которые надо посетить.

3. Перейти к шагу 1.

И вообще, любая, подчеркиваю ЛЮБАЯ, рекурсия легко превращается в итеративный алгоритм с явным выделением памяти. Просто надо будет в явном виде выделить память под переменные фрэйм стэков активных рекурсивных вызовов.

Хотя, как правило, итерационную программу отлаживать легче. Легче завершить программу в случае ошибки (без бросания каких-либо исключений). И многим легче итеративную программу понимать.

А сколько миллионов банков сидит на джаве

понятия не имею. тебе нужен ответ на вопрос или повод потрясти воспалённым ънтерпрайзом?

> Finger Tree

O(log n) append

Data.Sequence Zipper

а Data.Sequence разве ассоциативный? каким боком они здесь, для хранения обойденных директориев?

>> ну тогда поздравляю

Рано.

т.е. ты все еще надеешься написать код на хаскеле всего в О(1) раз хуже имеративного? ну я жду.

при добавлении в голову время доступа будет O(n)

время доступа куда? чего?

а Data.Sequence разве ассоциативный?

Data.Sequence - это реализация Finger Tree в GHC. я тебе специально дал ссылку на update с указанной сложностью операции

детский сад на прогулке

время добавления в голову O(1)

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

время добавления в хвост O(n) данная проблема решается разделением списка на 2 составляющие (R,T), R содержит 1 элемент, а T содержит остальные элементы в развёрнутом виде, в этом случае добавление в хвост осуществляется за O(1) т.к. это добавление в голову T.

Далее если всё честно считать, то времена доступов как худшее так и амортизированное (в случае ленивых вычислений), будут O(1).

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

Т.е. правильно вашу фразу стоит читать так:

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

Т.е. правильно вашу фразу стоит читать так:

не угадал

начнем с того, что ты вообще не назвал структуру данных, про которую исписал целую простынку

есть вполне определенная задача — хранить уже обойденные иноды (целые числа) в неком контейнере; нужно проверить, есть ли в контейнере это целое число за время О(log n), и добавлять его в контейнер за О(log n) времени и О(1) памяти

вариант задачи — все О(1)

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

P.S. я недавно писал у себя про вакансии для F#/Haskell (http://alexott-ru.blogspot.com/2010/06/blog-post_15.html). И за последние полгода это уже не первое предложение работы на хаскеле

> Ты представляешь, сколько должно быть элементов в бинарном дереве, чтобы переполнить стек?

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

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

и каков примерно будет коэффициент у О

> за последние полгода это уже не первое предложение работы на хаскеле

Хаскель можно смело записывать в мейнстрим :-)

Хаскель можно смело записывать в мейнстрим :-)

нельзя. и это очень, очень хорошо

> время добавления в хвост O(n) данная проблема решается разделением списка на 2 составляющие (R,T), R содержит 1 элемент, а T содержит остальные элементы в развёрнутом виде, в этом случае добавление в хвост осуществляется за O(1) т.к. это добавление в голову T.

что-то Вы чушь по-моему пишите, в случае «чистого» добавления все равно придётся добавлять в хвост R, иначе R и T будут разными и никак не смогут обозначать один и тот же список.

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

что приходит на ум Data.HashTable, или hashset с O(1), коэффициенты не скажу. ИМХО будет на какую-то константу хуже чем в сишном hash хранилище.

В самом простом варианте (тут не будет O(1)).

Для элементов списка (1,2,3,4,5,6) будет, что-то вроде ((1,2,3),(6,5,4)) при доставании головы происходит тупо выдаётся 1 O(1). При выборе tail происходит следующее ((2,3, $rev (6,5,4)), ()), где $ обозначает то, что операция производится лениво. Соответственно тут существует инвариант R=[] => T[]. поэтому при добавлении элемента за ним нужно следить.

Как я уже написал худшее время здесь не будет O(1), но амортизированное будет. Можно усложнить данную структуру данных, чтобы и худшее время было O(1), но с большей константой.

> что приходит на ум Data.HashTable, или hashset с O(1), коэффициенты не скажу. ИМХО будет на какую-то константу хуже чем в сишном hash хранилище.

где ссылка?

а вот тут http://www.haskell.org/ghc/docs/6.12.2/html/libraries/containers-0.3.0.0/Data... по твоему Окасаки сделали IntSet

member O(min(n,W)). Is the value a member of the set?

insert O(min(n,W)). Add a value to the set.

пусть W=64; про расход памяти как-то стыдливо умалчивается, но если при вставке хаскель чем-то занят аж О(64) времени, то вероятно он создает 64 ячейки (ведь мутировать-то хаскель не умеет), так что разумно предположить, что расход памяти будет в районе О(64*8) байт, в то время как сишному хэшу для норм. оперирования хватит 8*8 байт без всякого О.

Сишное множество в виде бин. дерева из даже из n=1 000 000 даст всего 20 обращений к памяти и 8+4 байт против О(64) тактов и предположительных О(64*8) байт у хаскеля.

> где ссылка? http://hackage.haskell.org/package/hashmap, http://cvs.haskell.org/Hugs/pages/libraries/base/Data-HashTable.html

Data.IntSet — это не то, о чём я говорил.

пусть W=64; .. вероятно.. разумно..

Отличная аргументация :) правда я в исходники и бенчмарки не хочу лезть.

про си - поиск по готовому сбалансированному бин дереву даст O(log(n)) и т.д. обращений.. добавление элемента будет за log(n).

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

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

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

В отличие от обхода бинарного дерева, рекурсивная реализация (без хвоста) --- не лучший выбор для QuickSort.

> Data.IntSet — это не то, о чём я говорил.

ну так запость ссылку на то, о чем ты говорил, и да, меня память интересует — хаскель ее требует больше, чем си, в О(log n) или всего лишь в 8-10 раз, а не то, что там «можно»

для boxed values он требует больше, для unboxed столько же. По дефолту в фп работают с permatent immutable данными, в рамках этой парадигмы догнать си в такой задаче не реально, тут мне спорить бессмысленно.

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