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

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

G>>

G>>Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату

M>Для анализа алгоритма еще важны соображения эффективности. Т. е. любой алгоритм должен иметь вычислительную сложность, которую мы должны уметь вычислить.
Для анализа важна ассимптотическая сложность, которая почти всегда одинакова для императивного и для функционального языка. Иногда в функциональном языке требуется дополнительный множитель log(N) для копирования данных, он отсечение вариантов это не тот случай.

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

FR>Такой проблемы нет http://caml.inria.fr/pub/docs/old-311/libref/Pervasives.html#7_Bitwiseoperations

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

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


M>Мне тоже так казалось, что не может быть проблемы только в битовых операциях. А в чем тогда проблема?

В том что очень узкое подмножество писателей шахматных алгоритмов не пересеклось с не очень широким подмножеством
функциональных программистов

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

_>Ну это для вас проще.

Для меня тоже. Причем то что он написал — это и есть чистое описание алогоритма. Особенно если говорить о Прологовском варианте (кстати, не пойму почему язык так не заслужено забыт!).

Вот тебе вариант на языке с сиоразным синтаксисом (но тоже с поддержкой сопоставления с образцом):

def qSort(lst)
{
  | []            => [];
  | head :: tail  => qSort(tail.Filter(_ < head)) + [head] + qSort(tail.Filter(_ >= head));
}

WriteLine(qSort([3,1,6,9,2,5,4,0]));

Пара пояснений, чтобы человек не знающий что такое сопоставление с образцом и частичное применение понял суть.
Конструкции "| []" и "| head :: tail" — это образцы. Если список переданный в качестве параметра пуст, то сопоставляется образец "| []" и соответственно возвращается пустой список (описываемый литералом "[]". Если список содержит хотя бы один элемент, то он сопоставляется с образцом "| head :: tail". Этот образец производит декомпозицию списка на голову (первый элемент списка) и хвост (список состоящий из всех элементов исходного списка за исключением головы). При этом головной элемент связывается переменной head, а хвост списка связывается с переменной tail.
Остальное все ясно само собой. Единственный мутный момент — это выражения "_ < head" и "_ >= head". Это так называемое частичное применение. В случае операторов с помощью частичного применения можно получить из оператора функцию. В данном случае функции lessThen и greatThen (соответственно). Подчеркиваение описывает свободный параметр (который становится параметром новой фунции). С применением лямбд это будет выглядеть так:

def qSort(lst)
{
  | []            => [];
  | head :: tail  => qSort(tail.Filter(x => x < head)) + [head] + qSort(tail.Filter(x => x >= head));
}

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

_> То что вы написали на хаскеле и прологе для меня филькина грамота,

Очень смешно. И ты еще ведешь речь о каком-то "экспрешон эспиранто"?
А как же ты тогда поймешь ту самую математическую запись?
quickSort([]) = []


_>и желания вникнуть особого нет в этот читабельный по вашему мнению синтаксис.

А у кого есть желание учить синтаксис и семантику твоего псевдокода?

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

Но на С как раз невозможно описать суть алгоритма. Точнее можно конечно, но алгоритм будет разбавлен тоннами не относящихся к делу подробностей (управление памятью, работа с ячейками памяти...).
В прочем, алгоритм написанный на Паскале может быть без труда переведен почти на любой язык (кроме, пожалуй, Пролога). Так в чем тогда проблема? Пиши все на Паскале. Все поймут.

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

У С легкость восприятия ниже плинтуса. А те кто не знаком с С, вообще ничего не поймут.

Потому тебе и говорят, что твоя идея — утопия.

_>Я искал дерево выражений а не читабельный синтаксис. XML подобные языки в этом плане и удобны что дерево выражений явно описывается.


А, ну, то есть задачи читать написанного нет?

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

Например, класс матриц описывается с использованием грамотного программирования примерно так: math.pdf.

G>Слив засчитан.

Какой слив, не понял? Ты меня пытаешься оскорбить?

G>Хотя если вы с женой общаетесь на C\C++ я хочу на это посмотреть

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

Вот я и говорю: если вам на Хаскеле понятнее, чем на человеческом языке, общайтесь на Хаскеле.

В следующий раз, если сообщение будет написано не на Хаскеле, читать и отвечать не буду.

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

FR>Вот это на хаскеле

FR>

FR>qsort []     = []
FR>qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
FR>

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

А что насчет пирамидальной сортировки???

Здравствуйте, Тролль зеленый и толстый, Вы писали:

ТЗИ>Да уж, такой дебильный ход мыслей может быть только в голове у программиста. Наверно, я все-таки имел в виду нормальный человеческий язык. Мы ведь здесь спорили о том, что, дескать, на Хаскеле понятнее, чем на английском.

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

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

_>Ок, я действительно не изучал до сих пор ни одного ФЯ, немного правда читал про F#.

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

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

_> Но, может я здесь ошибаюсь, тот же C# сейчас позволяет писать код в функциональном стиле: есть анонимные делегаты, лямбды.

Ага. Только нет сопоставления с образцом и много чего не поддерживается или поддерживается не очень качественно. Но и на C# 3.0 можно писать намного проще чем на яве, скажем. И это же крайне усложняет преобразование C#-кода в ява-код.

_> Я сейчас, возможно наивно, полагаю что ФЯ дает просто краткий синтаксис использования всего этого.

Ну, да. ФЯ просто предоставляет синтаксис и семантику для манипулирования с кодом на уровне выражений. C# 3.0 стал на половину ФЯ. Если же этих фич нет, то реализация алгоритмов становится запутаннее, сложнее и как следствие больше по объему.

_>Никаких принципиально новых выражений в ФЯ нет.

Ну, да. А любой код на любом языке высокого уровня (С, С++, Ява и т.п.) тоже не имеет ничего приципиально нового по сравнению с ассемблерами (тем же IL-ом к примеру). Но это только если не считать, что тот же if — это фича которая позволяет выражать мысль так как хочется, а не так как получается на том же ассемблере.

_>Ведь F# — функциональный язык, а так как он для .net то любой код написаный на нем легко дизассемблировать на C#.

Ну, так описывай свои алгоритмы на IL или x86-ом ассемблере. За чем дело встало?

Принципиально они одинаково мощны. Ведь все они полны по Тюрингу.

_>Что мне даст изучение какого либо ФЯ?

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

G>>Есть другая сторона медали: в чистом ФЯ алгоритм может быть сильно не похож на аналог на императивном языке, и чтобы придумать один общий синтаксис нужно уметь из него оба варианта получать, иначе программа на самом языке окажется понятнее.

_>Не могу с вами спорить на тему ФЯ, мало компетентен, но сомнения вы у меня посеяли )), надо думать.

Надо пробовать. А когда попробуешь будешь думать. За одно и вопрос твой сам сбой решится.

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

FR>Sum(list) не содержит в отличии от кода на Хаскеле выше алгоритма.

Да, ну. Алгоритм тот же. Просто фолд — это универсальная функция из которой можно получить в том числе и конкретную функцию сум.

FR>Этот "краткий синтаксис использования" дает новое качество.

+1

FR>А писать на C# функционально очень похоже на писание на Си объектно-ориентированно.

Ну, это ты загнул. C# 3.0 позволяет весьма сносно писать в функциональном стиле. Но это только лишь потому, что он на половину стал ФЯ (получил одну из главных фишек функциональных языков — ФВП).

Конечно есть множество ФЯ которые поддерживают ФП намного лучше шарпа (да почти все ), но все же Шарп тоже позволяет писать очень даже неплохо. Особенно если применять ЛИНК.

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

+1

Кстати, о Немерле . Если человек знаком с C#, то изучить Немерле можно недели за две не напрягаясь.

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

M>>Для такого простого случая это не суть важно. Вряд ли бы кто описывал алгоритм, где надо просто найти сумму. В более сложном случае и счетчик цикла может перепрыгивать, и выход из цикла может произойти досрочно, и сам массив/список может быть надо будет изменить на лету...

FR>В более сложных случаях тоже проще и декларативнее получается.

Мне показалось, что он об этом и говорил.

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

N>Ну вот давай попробуем написать тот же самый алгоритм русскими словами:

N>

N>быстрая сортировка пустого списка = пустой список
N>быстрая сортировка списка, первый элемент которого x, а хвост списка xs = 
N>  конкатенация 3 списков:
N>    быстрой сортировки xs, из которого отфильтрованы элементы, меньшие x
N>    списка из одного элемента x
N>    быстрой сортировки xs, из которого отфильтрованы элементы, большие или равные x
N>

Это все хорошо, только на C/C++ записывается совершенно другой алгоритм. Там делается акцент на том, как выполнить быструю сортировку не создавая дополнительные структуры. Так что это разные алгоритмы в моем понимании. Соответственно интересует, как на ФЯ описать алгоритм, который бы четко давал понять, как расходовать O(1) памяти сверх занятой списком. Также неудовлетворителен тот факт, что в качестве x мы берем первый элемент списка.

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

G>

G>let sum = fold (+) 0
G>

G>Даже в таком простом коде на F# используется несколько концепций, которых нету в C#.

Э...

Func<List<int>, int> sum = lst => lst.Aggregate(0, (x, acc) => x + acc);

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

_>>Ведь F# — функциональный язык, а так как он для .net то любой код написаный на нем легко дизассемблировать на C#.
G>Только понять потом что написано — нереально.

Да и дезасемблировать не реально. Рефлектор будет падать постоянно.

_>>Что мне даст изучение какого либо ФЯ?
G>Оно сделает тебя более профессиональным программистом.

+1

Здравствуйте, Тролль зеленый и толстый, Вы писали:

ТЗИ>Как ты думаешь, много ли программистов, как ты, изучают в свободное время функциональные языки? Почему ты пытаешься стыдить человека тем, что он не знает функциональных языков?

Не стыдить же людей тем, что они больше знают? А тем что они знают мало уж точно гордиться не чего.

ТЗИ>С таким же успехом можно упрекать людей в том, что они не знают brainfuck.

Толь есть троль . Причем тут эзотеричский язык? Его изобрели чтобы посмеяться. Знание же ФП действительно делает программиста лучше.
В прочем, ты это похоже и сам знаешь, но по-тролить охота. Да?

ТЗИ>Кстати, код быстрой сортировки на Хаскеле по "понятности" приближается к brainfuck'у.

Гы-гы.

G>>

G>>fold (+) list
G>>

ТЗИ>Здесь написано: свернуть (+) список.

На ОКамле здесь написано передать функции fold функцию (+) и список. Так как у функции есть еще один параметр, то в результате получается новая функция логика которой суммирование значений списка.

ТЗИ>Не знаю, мне не очень понятно.
ТЗИ>Понятно было бы так, например:

ТЗИ>

ТЗИ>x = sum of all items in list
ТЗИ>

А мне не очень понятно. Понятнее было бы так:

Посчитай все сама, плиз.

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

VD>если говорить о Прологовском варианте (кстати, не пойму почему язык так не заслужено забыт!).

Потому что сейчас есть Curry.

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

FR>Еще 10 лет назад было полно народу которые бравировали тем что не знают ООП и он им совершенно не нужен, сейчас это почему-то редкие птицы, странно да?

Кстати, многие фанатичные функциональщики снова начали этим бравировать.

Здравствуйте, Тролль зеленый и толстый, Вы писали:

ТЗИ>Если человек изучал математику и не изучал программирование, ему оба варианта будут непонятны.

Ты изучал математику?

Приведи, плиз, математическое описание алгоритма быстрой сортировки Хора.

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

M>Это все хорошо, только на C/C++ записывается совершенно другой алгоритм. Там делается акцент на том, как выполнить быструю сортировку не создавая дополнительные структуры. Так что это разные алгоритмы в моем понимании. Соответственно интересует, как на ФЯ описать алгоритм, который бы четко давал понять, как расходовать O(1) памяти сверх занятой списком.

Можно написать и с деструктивным in-place обновлением (здесь, здесь), но будет уже не так коротко и понятно.

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

VD>Приведи, плиз, математическое описание алгоритма быстрой сортировки Хора.

Д. Кнут, третий том?

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

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

N>Потому что сейчас есть Curry.

Который известен и используется много менее Пролога.