функциональный отворот.
Это заклинение ещё не показывает лист компрехеншонс! Кстати, q там не совсем в тему, потому что quicksort она всё-таки inplace.
По-моему, очарование хаскела не в лаконичности этой записи, а в
1. том, что он (по крайней мере если без экстеншенов) базируется на строгом математическом фундаменте, а не на кучке хаков и адхоков, как некоторые другие языки;
2. тех возможностях по организации программ, которые даёт функциональность и ленивость (например, возможности вернуть бесконечный список, а потом уже отрезать от него конечный кусок (впрочем, генераторы конкретно в этом случае дают то же самое
По-моему, очарование хаскела не в лаконичности этой записи, а в
1. том, что он (по крайней мере если без экстеншенов) базируется на строгом математическом фундаменте, а не на кучке хаков и адхоков, как некоторые другие языки;
2. тех возможностях по организации программ, которые даёт функциональность и ленивость (например, возможности вернуть бесконечный список, а потом уже отрезать от него конечный кусок (впрочем, генераторы конкретно в этом случае дают то же самое
которые даёт функциональность и ленивость (например, возможности вернуть бесконечный список, а потом уже отрезать от него конечный кусок (впрочем, генераторы конкретно в этом случае дают то же самоеага, функциональные структуры данных такие функциональные, замечательные и бесконечные. Только вот что делать с простеньким алгоритмом генерации суффиксного дерева? Не получается у меня как-то линейная сложность, не смотря на все красивости. Может они бесполезны?
Впрочем n*log(n) у меня получается запросто - мы берём тип IndexedSpace = Map Int Dynamic, делаем его из него State монаду и адаптируем итеративный алгоритм - получаем чистый и ленивый алгоритм, хотя и не слишком красивый
Чего ты мозги паришь, функциональный <> Haskell.
окей, функциональный - это не только хаскель. Попробуй на лиспе написать в функциональном стиле (без использования переменных). Всё равно не получится, а если получится - тот же самый алгоритм не сложно будет перевести и на хаскель. Иными словами, отсутствие ссылок и mutable переменных - это основная фича функциональных структур данных, но она сильно ограничивает гибкость применения оных. И я нашёл пример, где это ограничение фатально (гугл не знает ни одной реализации алгоритма за O(n) - как в императивном случае, лучшее что находит гугл - это O(n*log(n ).
Я мог ещё понять, когда за красоту, простоту и понятность алгоритма жертвуют константой времени исполнения (хаскель медленнее си на алгебраических тестах раза в два). Но некоторые сложные алгоритмы просто не реализуются разумным образом на функциональных языках вообще, и тут жертвовать уже приходится асимптотикой - а это никуда не годится.
Основной аргумент функциональных программистов - функциональные языки могут то же, но по-другому. И это по-другому типо круто, потому как позволяет глубокую оптимизацию и математические доказательства. А оказалось, что даже небольшой задачи решить на них нельзя, пусть это задача и достаточно сложно. Простой quicksort не теряет своего времени при переносе на функциональные языки, а вот более сложный алгоритм построения суффиксного дерева на функциональны языки перевести так и не смогли. Конечное сложные (где высока концентрация сложности на единицу кода) алгоритмы редко используются на практике, гораздо чаще приходится писать просто большие приложения, каждый модуль которых быть может и не сложен, но совокупная сложность получается ещё выше чем у обсуждаемого алгоритма, и что-то я не видел достаточно больших проектов на чистом функциональном языке (без переменных в лиспе или IORef в хаскеле а значит сама практика доказала нежизнеспособность теории функциональных языков. Они годятся только в учебных целях, в качестве первого языка программирования, например, да и учебники подходящие для этого есть - тот же самый SICP.
Я мог ещё понять, когда за красоту, простоту и понятность алгоритма жертвуют константой времени исполнения (хаскель медленнее си на алгебраических тестах раза в два). Но некоторые сложные алгоритмы просто не реализуются разумным образом на функциональных языках вообще, и тут жертвовать уже приходится асимптотикой - а это никуда не годится.
Основной аргумент функциональных программистов - функциональные языки могут то же, но по-другому. И это по-другому типо круто, потому как позволяет глубокую оптимизацию и математические доказательства. А оказалось, что даже небольшой задачи решить на них нельзя, пусть это задача и достаточно сложно. Простой quicksort не теряет своего времени при переносе на функциональные языки, а вот более сложный алгоритм построения суффиксного дерева на функциональны языки перевести так и не смогли. Конечное сложные (где высока концентрация сложности на единицу кода) алгоритмы редко используются на практике, гораздо чаще приходится писать просто большие приложения, каждый модуль которых быть может и не сложен, но совокупная сложность получается ещё выше чем у обсуждаемого алгоритма, и что-то я не видел достаточно больших проектов на чистом функциональном языке (без переменных в лиспе или IORef в хаскеле а значит сама практика доказала нежизнеспособность теории функциональных языков. Они годятся только в учебных целях, в качестве первого языка программирования, например, да и учебники подходящие для этого есть - тот же самый SICP.
1) По моему мнению главная фишка функциональных языков не иммъютабельность данных, а возможность оперировать функциями как обычными данными. Хаскель тут вообще изгой, большинство ФЯ позволяют менять состояние и поэтому твоей проблемы вообще нет.
2) Дай ссылку на твой пример с нормальным описанием. Для чисто функциональных структур данных существуют специальные приемы работы через амортизацию, когда среднее время такое же, а максимальное большое. Такие структуры данных могут пригодиться и в С, потому что они дружественны к многопоточности. Так что у тут мы видим пук в воду.
>>что-то я не видел достаточно больших проектов на чистом функциональном языке (без переменных в лиспе или IORef в хаскеле а значит сама практика доказала нежизнеспособность теории функциональных языков. Они годятся только в учебных целях, в качестве первого языка программирования, например, да и учебники подходящие для этого есть - тот же самый SICP.
3) Ты все время путаешь чисто функциональные и функциональные языки. Чисто функцилнальные - лишь подмножество функциональных и не самое большое. А Хаскель - лишь один из чисто функциональных языков. Функциональные языки давно уже доказали свою полезность, даже МС это признала.
2) Дай ссылку на твой пример с нормальным описанием. Для чисто функциональных структур данных существуют специальные приемы работы через амортизацию, когда среднее время такое же, а максимальное большое. Такие структуры данных могут пригодиться и в С, потому что они дружественны к многопоточности. Так что у тут мы видим пук в воду.
>>что-то я не видел достаточно больших проектов на чистом функциональном языке (без переменных в лиспе или IORef в хаскеле а значит сама практика доказала нежизнеспособность теории функциональных языков. Они годятся только в учебных целях, в качестве первого языка программирования, например, да и учебники подходящие для этого есть - тот же самый SICP.
3) Ты все время путаешь чисто функциональные и функциональные языки. Чисто функцилнальные - лишь подмножество функциональных и не самое большое. А Хаскель - лишь один из чисто функциональных языков. Функциональные языки давно уже доказали свою полезность, даже МС это признала.
1) По моему мнению главная фишка функциональных языков не иммъютабельность данных, а возможность оперировать функциями как обычными данными. Хаскель тут вообще изгой, большинство ФЯ позволяют менять состояние и поэтому твоей проблемы вообще нет.Во-первых, я говорил о функциональных структурах данных, а не о фишках функциональных языков.
Во-вторых, ты плохо знаешь хаскель, он вполне позволяет манипулировать функциями.
В-третьих, в хаскеле есть IORef - ссылочный тип, но программирование с его использованием уже не является функциональным. Получаем ту же самую императивность, только с большим побочным геморроем.
3) Ты все время путаешь чисто функциональные и функциональные языкиНе бывает нечисто функциональных языков. Это уже мультипарадигменные получаются, где царит смешение стилей. Таков, например, питон. В новом стандарте плюсов тоже собираются добавить функциональную парадигму.
2) Дай ссылку на твой пример с нормальным описанием.ты про суффиксные деревья? Гасфилд же.
Я просил ссылку с описанием алгоритма, а не на книгу, которую хрен скачаешь.
вроде эта статья: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
Только вот что делать с простеньким алгоритмом генерации суффиксного дерева? Не получается у меня как-то линейная сложность, не смотря на все красивости. Может они бесполезны?Я вот сейчас подумал, что минимальный автомат вообще по-функциональному не реализовать. В том смысле, что придется завести граф и таблицу ссылок, в конечном итоге все это можно свести в некую комбинированную структуру, но вот так же красиво, как дерево, - "data Tree a = Leaf a | Left (Tree a) Right (Tree a)" - не получится.
что такое минимальный автомат? FSA замечательно через затягивание узла реализовывается.
посмотрел. Думаю можно реализовать функционально, ровно как и собственно суффиксные деревья. Просто это выйдет асимптотически медленнее
Во-первых, я говорил о функциональных структурах данных, а не о фишках функциональных языков.
В следующий раз когда захочешь поговорить о структурах данных, говори "структуры данных", а не "языки", так будет понятнее.
Не бывает нечисто функциональных языков.
У тебя определения тухлые. Функциональный язык - язык с первоклассными функциями. Все. Чистота или ленивость в определение не входят. Чисто функциональные языки - небольшое подмножество, как уже правильно сказали.
Что касается О(n то у меня есть большие сомнения в корректности применения этих оценок в языках со сборкой мусора.
В следующий раз когда захочешь поговорить о структурах данных, говори "структуры данных", а не "языки", так будет понятнее.
отсутствие ссылок и mutable переменных - это основная фича функциональных структур данных,в следующий раз читай пост, на который отвечаешь.
Что касается определений - да у меня отличное от общепринятого. Я полагаю функциональным языком, не тот, где функции представляют собой объекты первого класса, а то, в котором можно удобно программировать в функциональном стиле (то есть представляя результат как композицию функций, без переменных и не работая с состоянием). В этом случае сохраняется чистота и возможность применения математики программированию, в том исключительное отличие функциональных языков. А если добавить в процедурный просто возможность оперировать функциями как первоклассными объектами, мы просто сделаем легкодоступными ещё несколько идиом создания кода и всё. Никаких преимуществ чистых функциональных языков смешанный не наследует.
Почему огрубление сложности алгоритма от "17*n + 30*q +109 умножений и 11*n + 2 сложений, где q - число единичных разрядов в двоичном представлении n" до "O(n)" ты считаешь универсально допустимым, а от "O(n)" до "O(n) с точностью до логарифма" - нет?
жертвовать уже приходится асимптотикой - а это никуда не годится
У Кнута например сложность оценивалась главным образом в стиле первого примера. С распространением более современных книжек типа Кормена все освоили O-нотацию и считают её само собой разумеющейся. А в теории сложности могут пренебрегать различием между n^2 и n^10. А ещё кого-то интересует только, выражается ли сложность в элементарных функциях. А ещё кого-то интересует только факт алгоритмической разрешимости.
С практической точки зрения эффект от систематического непопадания в кэш например может оказаться значительнее логарифмического множителя.
отсутствие ссылок и mutable переменных - это основная фича функциональных структур данных,
Во-первых, чисто функциональных. Во-вторых, у тебя опять каша - ссылки там есть, просто они не mutable.
В этом случае сохраняется чистота и возможность применения математики программированию, в том исключительное отличие функциональных языков.
Какую именно математику ты можешь использовать в чистом ФЯ, но не можешь использовать в том же ML или Лиспе? Как часто ты ее используешь? (хоть раз было?)
А если добавить в процедурный просто возможность оперировать функциями как первоклассными объектами, мы просто сделаем легкодоступными ещё несколько идиом создания кода и всё. Никаких преимуществ чистых функциональных языков смешанный не наследует.
Это уже совсем неправда. Где есть первоклассные функции, там обычно есть функции высшего порядка и карринг, а именно они и дают большую часть ништяков ФП: удобное декларативное задание многих алгоритмов через map, fold, filter и т.п., бесточечный стиль и пр. Собственно, отказываясь от чистоты, я почти ничего не теряю, зато имею возможность реализовать более эффективные алгоритмы.
Извини, но твоя речь напоминает продукт промытых хаскель-пропагандой мозгов при отсутствии опыта использования нечистых ФЯ.
Извини, но твоя речь напоминает продукт промытых хаскель-пропагандой мозгов при отсутствии опыта использования нечистых ФЯ.есть у меня опыт нечистых ФЯ. Питон. Функции высшего порядка - пожалуйста, они даже в плюсовом STL (тот же map) есть. Карринг практически не используется. С каррингом и partial особо не поиграешься, во-первых, нет короткой удобной записи, во-вторых, накладные расходы возрастают без видимой необходимости.
Ну, питон можно назвать ФЯ лишь с большой натяжкой. И если бы функции в нем были только чистыми, выиграл ли бы он от этого, стал ли бы более функциональным? Сомневаюсь.
почему же с натяжкой? Если по моему определению, то никак. А если по вашему, то самое оно. Просто там функциональные средства дополнены всеми прочими - что хочешь, то и используй. Хотя без процедурных не обойтись.
почему же с натяжкой?
Хотя бы из-за ограниченных возможностей создания функций на лету (лямбды фиговые).
Ну и субъективно использование функциональных фишек не шибко удобное (как там с каррингом?). В руби с его блоками и то приятней.
Хотя бы из-за ограниченных возможностей создания функций на лету (лямбды фиговые).с этого момента подробнее. Питон поддерживает весь необходимый инструментарий (с вашей точки зрения для оперирования функциями как первоклассными объектами просто пользоваться им неудобно. Но при этом питон существенно императивен, объявления функций на самом деле являются конструкторами соответствующих объектов и исполняются при загрузке модуля в порядке объявления.
Я могу сделать лямбду с циклом внутри?
Я не спорю, по моему определению питон считается ФЯ, называть его так можно.
Почему с натяжкой - потому что помимо бинарного свойства принадлежности к ФЯ есть еще небинарная упорядоченная характеристика приспособленности языка к использованию первоклассных функций на деле, к функциональному стилю. И вот тут питон сильно проигрывает "настоящим" ФЯ вроде ML, F#, Nemerle, Scala, Haskell и ко.
Я не спорю, по моему определению питон считается ФЯ, называть его так можно.
Почему с натяжкой - потому что помимо бинарного свойства принадлежности к ФЯ есть еще небинарная упорядоченная характеристика приспособленности языка к использованию первоклассных функций на деле, к функциональному стилю. И вот тут питон сильно проигрывает "настоящим" ФЯ вроде ML, F#, Nemerle, Scala, Haskell и ко.
Я могу сделать лямбду с циклом внутри?в хаскеле - нет, там циклов нету. В питоне запросто.
def createFunc:
def f:
res = 0;
for i in Index:
res = res + i
return res
return f
типа если тебе так уж хочется объявить в лямбде слишком сложную функцию, то в явной форме она читаться будет куда лучше
спасибо, капитан
непонятно только, почему вы так долго к этому шли. Для меня ситуация с хаскелем и с его структурами данных стала ясна через 2 месяца после использования
непонятно только, почему вы так долго к этому шли. Для меня ситуация с хаскелем и с его структурами данных стала ясна через 2 месяца после использования
ну я просто полагал, что проблемы с хаскелем имеют в первую очередь причину во мне. То есть необходимо ботать и ботать. Ботал-ботал, а в конце-концов нашёл проблему, которую даже гуру хаскеля решить не смогли.
суффиксное дерево - это например если для слова "привет", то:
а если для слов "привет" и "тест", то:
а если для слов "цветмет", "привет" и "тест", то:
типа того, или здесь есть какие-то подводные камни? минимальной единицей, которая заносится в дерево является слово? типа если в слове есть одинаковые слоги - пофиг, или нужно это учитывать?
т
ет
вет
ивет
ривет
привет
а если для слов "привет" и "тест", то:
т
ет ст
вет ест
ивет тест
ривет
привет
а если для слов "цветмет", "привет" и "тест", то:
т
ет ст
мет вет ест
тмет ивет тест
етмет ривет
ветмет привет
цветмет
типа того, или здесь есть какие-то подводные камни? минимальной единицей, которая заносится в дерево является слово? типа если в слове есть одинаковые слоги - пофиг, или нужно это учитывать?
типа того, или здесь есть какие-то подводные камниесть. Нужно внимательнее читать определение.
в слове тест есть следующие суффиксы:
1 - т
2 - ст
3 - ест
4 - тест
Первый полностью совпадает с префиксом четвёртого и потому либо отображает пустой вершиной, отступающей от узла "т", либо вообще не отображается, если дерево сокращённое
хорошо, я качнул Гасфилда, и там и правда вразумительнее, чем в википедии.
Значит для слова "тест" нельзя построить суффиксное дерево, потому что последний суффикс ("т") - это первый префикс, и поэтому не может закончиться в листе деревА, как того требует определение, и чтобы избежать этого мы используем символ, который нигде в строке не встречается, например $, и тогда для строки "тест$" дерево будет выглядеть:
как-то так?
Значит для слова "тест" нельзя построить суффиксное дерево, потому что последний суффикс ("т") - это первый префикс, и поэтому не может закончиться в листе деревА, как того требует определение, и чтобы избежать этого мы используем символ, который нигде в строке не встречается, например $, и тогда для строки "тест$" дерево будет выглядеть:
с е т
т с $ е
т с
т
как-то так?
неужели O(n*log(n — это настолько хуже O(n) для больших n?
итак, я навелосипедил вот такую очень простую и конечно же неэффективную реализацию несжатого суффиксного дерева.
метод processWord принимает строку и итерирует посимвольно по всем суффиксам, составляющим эту строку: внешний цикл ходит по суффиксам, внутренний - внутри очередного суффикса. Если очередной символ присутствует среди потомков данного узла, смещаемся на этого потомка, и переходим к следующему символу. Если не присутствует - добавляем его в качестве потомка данного узла и также переходим к следующему символу.
После перехода к каждому следующему суффиксу начинаем обход дерева с корневого узла.
Какая здесь у меня сложность алгоритма получилась, кто подскажет?
метод processWord принимает строку и итерирует посимвольно по всем суффиксам, составляющим эту строку: внешний цикл ходит по суффиксам, внутренний - внутри очередного суффикса. Если очередной символ присутствует среди потомков данного узла, смещаемся на этого потомка, и переходим к следующему символу. Если не присутствует - добавляем его в качестве потомка данного узла и также переходим к следующему символу.
После перехода к каждому следующему суффиксу начинаем обход дерева с корневого узла.
public class SuffixTree {
SuffixNode root = new SuffixNode;
public void processWord(String word) {
int len = word.length;
for(int i = 0; i < len; i++) {
SuffixNode sn = root;
for(int j = 0; j < (len-i); j++) {
char c = word.charAt(j+i);
SuffixNode new_sn = sn.getSuffix(c);
if(new_sn == null) {
SuffixNode sn2 = new SuffixNode(c);
sn.addNode(sn2);
sn = sn2;
}
else sn = new_sn;
}
}
}
}
class SuffixNode {
private char suffix;
private Hashtable<Character, SuffixNode> nodes = new Hashtable<Character, SuffixNode>
public SuffixNode // root constructor
{ }
public SuffixNode(char c) {
this.suffix = c;
}
public void addNode(SuffixNode sn) {
nodes.put(sn.getSuffix sn);
}
public SuffixNode getSuffix(char suffix) {
return nodes.get(suffix);
}
public char getSuffix {
return suffix;
}
}
Какая здесь у меня сложность алгоритма получилась, кто подскажет?
Если считать, что findSuffix работает за O(1 то сложность - O(n^2 где n - длина строки.
O(n*log(n — это настолько хуже O(n) для больших n?Конечно, нет. O(n*log(n не на столько, а во столько хуже O(n)
На пхп напиши, джава-то порвана давно.
Оставить комментарий
yroslavasako
Читал недавно на абсурдопедии:Потратив немалое количество времени, своего и гугла, я обнаружил достаточно простое заклятие-отворот, которое снимает любое привораживание функциональными языками и хаскелем в частности.
Вот оно:
суффиксные деревья за линейное время.