Здравствуйте, gandjustas, Вы писали:
G>Кстати, ты будешь удивлен, но в хаскеле есть паттерн n+k и можно писать функции так
G>Так что там насчет далекости хаскеля от математики?
ты будешь смеяться, но хаскель 2010 от математики таки отдалился
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, gandjustas, Вы писали:
G>>Кстати, ты будешь удивлен, но в хаскеле есть паттерн n+k и можно писать функции так
G>>Так что там насчет далекости хаскеля от математики?
BZ>ты будешь смеяться, но хаскель 2010 от математики таки отдалился
Ну да, там убрали паттерн (n+k) мотивируя это тем, что оператор (+) может быть переопределен и паттерн не может это учитывать.
Здравствуйте, Mystic, Вы писали:
M>Здравствуйте, VladD2, Вы писали:
VD>>1. Не является описанием алгоритма Хоара. M>Это одна и есть вариация метода быстрой сортировки, которая была предложена Хоаром. Вот его статья в том виде, в котором она появилась в 1962.
Ага, только ты процетировал даже не хоровский алгоритм. Посмотри внимательно, там идет речь об сортировке вставками (видимо как оптимизация).
M>Там алгоритм описан словами
Ага. Но не кнутовскими.
VD>>2. Не является математическим описанием, а является описанием на каком-то суржике с преобладанием русского языка. M>А типа математическое описание только там, где нет слов?
Если 90% описания — это слова, то математики в нем чуть больше чем полностью нет.
M> Много лет алгоритмы описывались словами, а в случае необходимости формального описания приводился исходный текст программы. Чем это не математика? У тебя какое-то совсем узвое понимание
Дык я и говорил, что математика плохо пригодна для описания алгоритмов. Потому их словами и описывают. Причем если вообще обойтись без мат.символов, то станет только понятнее, а вот обратное не верно.
VD>>Так вот, описать алгоритм Хора средствами одной лишь математики практически невозможно. А если постораться это сделать, то у тебя получится запись очень близкая к записи получаемой на функциональных языках: VD>> VD>>
M>Нигде такой изврат не встречал.
Это говорит исключительно о тебе.
M> Алгоритмы очень часто встречаются в математических книгах. Для их описания часто используется словесная форма, используются (использовались) блок-схемы-алгоритмы, используется псевдокод.
Ага. Только вот псевдокод — это миф. Фактически используется выдуманный язык. Иногда даже (как в книгах Кнута) используется выдуманный ассемблер выдуманной машины.
M> Это можно найти довольно часто. А такого я не видел, может подкинешь ссылоку?
Можешь зайти тайти самоучитель по любому ФЯ. Там почти наверняка будет подобное описание.
M> Более того, это не алгоритм Хоара, по той причине, что алгоритм Хоара вполняет сортировку по месту.
Это алгоритм Хора. Алгоритм вообще не знает что такое место. Алгоритм — это абстракция.
M>Я бы не стал осквернять имя Хоара такой реализацией.
Ты бы лучше о своем имени думал. Несешь чушь с уверенностью достойной лучше применения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ага, только ты процетировал даже не хоровский алгоритм. Посмотри внимательно, там идет речь об сортировке вставками (видимо как оптимизация).
Да, оптимизация на последнем этапе. Хоар тоже об этом упоминал в своей работе.
VD>>>2. Не является математическим описанием, а является описанием на каком-то суржике с преобладанием русского языка. M>>А типа математическое описание только там, где нет слов? VD>Если 90% описания — это слова, то математики в нем чуть больше чем полностью нет. VD>Дык я и говорил, что математика плохо пригодна для описания алгоритмов. Потому их словами и описывают. Причем если вообще обойтись без мат.символов, то станет только понятнее, а вот обратное не верно.
Описать алгоритмы можно, как можно описать машину Тьюринга. Можно ввести свои обозначения, описать любой язык программирования. Вопрос другой: а смысл? Часто словесного описания алгоритма более чем достаточно. Общепринятой формальной системы нет, и смысла в ней тоже нет. Ничто не мешает ее построить в соответствии с аксиоматикой, как те же конечные автоматы. Только это будет напрасный перевод бумаги: описание такой системы будет объемно и тривиально по содержанию Там гду нужна такая формализация появились языки программирования. Тем не менее, иногда они это чрезмерная детализация, которая не нужна.
M>> Алгоритмы очень часто встречаются в математических книгах. Для их описания часто используется словесная форма, используются (использовались) блок-схемы-алгоритмы, используется псевдокод. VD>Ага. Только вот псевдокод — это миф. Фактически используется выдуманный язык. Иногда даже (как в книгах Кнута) используется выдуманный ассемблер выдуманной машины.
А в математике все выдумано, если на то пошло. Математика это плох воображения: если выдуманная система аксиом, в которой мы и работаем. В этой системе аксиом можно описать реальный ассемблер, а можно выдуманный. Можно описать Nemerle, C# и т. п.
M>> Это можно найти довольно часто. А такого я не видел, может подкинешь ссылоку? VD>Можешь зайти найти самоучитель по любому ФЯ. Там почти наверняка будет подобное описание.
Там обычно идет исходник на этом ФЯ, не более того. Ибо возникает естественный вопрос: зачем математической символикой дублировать этот ФЯ? Любой язык программирования по сути может рассматриваться как математическая символика.
M>> Более того, это не алгоритм Хоара, по той причине, что алгоритм Хоара вполняет сортировку по месту. VD>Это алгоритм Хора. Алгоритм вообще не знает что такое место. Алгоритм — это абстракция.
Еще как знает. Вся дисциплина "анализ алгоритмов" о том, как получать характеристики алгоритма, такие как затраты памяти, скорость выполнения, количество тех или иных операций и т. п. Если брать за оригинал статью самого Хоара, то все его формулы из нее ну никак не относятся к тому варианту, что ты привел. Например, там оценивается количество перестановок, которые выполняет алгоритм. Где они у тебя? Нет перестановок, значит это не Хоар, а другой алгоритм
Здравствуйте, VladD2, Вы писали:
N>>Потому что сейчас есть Curry.
VD>А ты сам то это чудо используешь?
На работе на нашем проекте используется только C# и VB.NET, так что нет.
Но у меня есть одна задачка, которой я собираюсь заняться в свободное время, и я как раз думал приспособить туда Curry.
Здравствуйте, FR, Вы писали:
FR>Как язык пролог один из самых декларативных и читабельных, и вообще ближе к человеческому мышлению чем FR>императивные и функциональные языки. Но при этом страшно неэффективен кроме очень узкой ниши.
Может эти прелести надо не Прологу приписывать, а списку правил т.е. списку импликаций?
Списки импликаций действительно вещь очень читабельная, хотя и недостаточная для создания всех промышленных систем.
Только вот стоит ли из этого пытаться делать самодостаточный язык. Если и возможно целиком на Прологе реализовать ERP или CAD систему, ве на Прологе от графики до логики, то читабельность будет просто ужасная.
А списки правил вида: если будет дождь -> взять зонт; если есть тучи ->будет дожь, оно конечно читабельнее чем код на C++ какой нибудь системы 3D моделирования.
Нам в курсе математики структурную индукцию не давали. Я так понял, что структурная индукция — есть обобщение математической индукции на рекурсивные структуры данных, такие как деревья и списки.
В самой же математической индукции я ничего рекурсивного не вижу.
ТЗИ>>Я не припоминаю, чтоб нас этому учили в рекуррентной форме. G>Определения обычно не в рекурентной форме. А вычисления в рекурентной.
Я такого не припоминаю. Там были обычные циклы. Я не спорю, что это можно выразить рекуррентно, но в средней школе рекурсия вроде не упоминалась.
G>Да ну? G>Вспоминаем как доказывать по индукции: G>1)Определяем базовый (или несколько базовых случаев) при фиксированном N G>2)Предполагаем что утверждение выполняется для N (формальность) G>3)Доказываем для N+k, где k — константа и обычно равна 1
Ну вспоминаем. Че-то вы не то написали.
Для индукции нужно доказать истинность двух утверждений:
N>Можно написать и с деструктивным in-place обновлением (здесь, здесь), но будет уже не так коротко и понятно.
От. От это оно. Чего-ж спорить-то до усрачки, если сами все прекрасно понимаете?
Вот это он и есть самый квиксорт, о котором писал Хоар.
И не странно, что в этом алгоритме проступают знакомые императивные черты. А если еще фигурных скобочек добавить?
И, главное, какой "понятный" синтаксис! Какая легкость восприятия! Мммм... Переменные обозначены одной буквой, конечно ж, это от высокого функционального стиля. А функция processArray как-то слишком вульгарно-понятно называется — это фи, императивщина, надо было j или sigma.
import Control.Monad (when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray
qsort :: (IArray a e, Ix i, Enum i, Ord e) => a i e -> a i e
qsort arr = processArray quickSort arr
processArray :: (IArray a e, IArray b e, Ix i)
=> (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e
processArray f (arr :: a i e) = runST $ do
arr' <- thaw arr :: ST s (STArray s i e)
f arr'
unsafeFreeze arr'
quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m ()
quickSort arr = qsort' =<< getBounds arr
where
qsort' (lo, hi) | lo >= hi = return ()
| otherwise = do
p <- readArray arr hi
l <- mainLoop p lo hi
swap l hi
qsort' (lo, pred l)
qsort' (succ l, hi)
mainLoop p l h | l >= h = return l
| otherwise = do
l' <- doTil (\l' b -> l' < h && b <= p) succ l
h' <- doTil (\h' b -> h' > l' && b >= p) pred h
when (l' < h') $ do
swap l' h'
mainLoop p l' h'
doTil p op ix = do
b <- readArray arr ix
if p ix b then doTil p op (op ix) else return ix
swap xi yi = do
x <- readArray arr xi
readArray arr yi >>= writeArray arr xi
writeArray arr yi x
Здравствуйте, Тролль зеленый и толстый, Вы писали:
DM>>См., например, обобщение математической индукции — структурную индукцию: DM>>http://en.wikipedia.org/wiki/Structural_induction
ТЗИ>Нам в курсе математики структурную индукцию не давали. Я так понял, что структурная индукция — есть обобщение математической индукции на рекурсивные структуры данных, такие как деревья и списки. ТЗИ>В самой же математической индукции я ничего рекурсивного не вижу.
Осталось только понять, почему это обобщение: потому что натуральные числа — это частный случай рекурсивной структуры:
Nat = Zero | Succ Nat
(см. http://en.wikipedia.org/wiki/Peano_axioms )
В матиндукции из школьной программы мы доказываем истинность некого предиката Р(n) для всех натуральных n.
Зная, что n — это либо 0, либо k+1 некоторого натурального k, P превращается в рекурсивную функцию c двумя ветками: P(0) и P(n), выраженную через P(n-1). И наоборот — рекурсивную функцию над натуральными числами в приведенной форме можно рассматривать как индуктивное доказательство некоторого утверждения, справедливого для всех натуральных чисел.
Надеюсь, про прямую связь между функциями и доказательствами, а также типами и утверждениями вы знаете (изоморфизм Карри-Говарда). http://thedeemon.livejournal.com/15889.html
Здравствуйте, Тролль зеленый и толстый, Вы писали:
ТЗИ>>>Я не припоминаю, чтоб нас этому учили в рекуррентной форме. G>>Определения обычно не в рекурентной форме. А вычисления в рекурентной.
ТЗИ>Я такого не припоминаю. Там были обычные циклы. Я не спорю, что это можно выразить рекуррентно, но в средней школе рекурсия вроде не упоминалась.
В средней школе и циклов, и рекурсии даже близко не было.
G>>Да ну? G>>Вспоминаем как доказывать по индукции: G>>1)Определяем базовый (или несколько базовых случаев) при фиксированном N G>>2)Предполагаем что утверждение выполняется для N (формальность) G>>3)Доказываем для N+k, где k — константа и обычно равна 1
ТЗИ>Ну вспоминаем. Че-то вы не то написали.
ТЗИ>Для индукции нужно доказать истинность двух утверждений:
ТЗИ>1) Истинность F(n)
Неверно, истинность F(n) предполагаем, доказывать надо для F(N0),F(N1)... — базовые случаи ТЗИ>2) Истинность импликации F(n) => F(n + k),
Именно, и как это доказывается? Выражением F(n + k) через F(n) — вот тебе и рекурсия.
VD>Func<List<int>, int> sum = lst => lst.Aggregate(0, (x, acc) => x + acc);
VD>
VD>так что некоторых фич нет.
О чём и речь.
VD>Так нет частичного применения, и вывод типов по хуже. Но базовые строительные блоки таки есть. И это позволяет писать на шарпе в функциональном стиле. Причем писать довольно не плохо.
Ну ты сравни строку на F# и C# Потом в C# операция определена только над списком целых, и я не знаю насчёт F#, а в Haskell тип схожего выражения будет
Здравствуйте, VladD2, Вы писали:
VD>Цитировать надо добросовестно.
G>Даже в таком простом коде на F# используется несколько концепций, которых нету в C#. VD> так что некоторых фич нет. L>>О чём и речь.
Здравствуйте, lomeo, Вы писали:
VD>>Цитировать надо добросовестно.
G>>Даже в таком простом коде на F# используется несколько концепций, которых нету в C#. VD>> так что некоторых фич нет. L>>>О чём и речь.
L>Так пойдёт?
Нет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, FR, Вы писали:
FR>Большинству людей как раз будет ближе функциональщина, так как они не программисты, а функциональщина ближе к математической нотации чем FR>сиобразные.
Ты это всерьез считаешь, что большинству людей близка математическая нотация? Подавляющее большинство инженеров последний раз с математической нотацией сталкивается в ВУЗе, после чего с успехом ее забывает, т.к. практические задачи где она применима встречаются крайне редко.
Здравствуйте, Undying, Вы писали:
U>Ты это всерьез считаешь, что большинству людей близка математическая нотация? Подавляющее большинство инженеров последний раз с математической нотацией сталкивается в ВУЗе, после чего с успехом ее забывает, т.к. практические задачи где она применима встречаются крайне редко.
А с нотацией или псевдокодом основанными на императивных языках программирвания они сталкиваются еще реже, и "изученный" бейсик или паскаль вылетает из головы гораздо быстрее чем математика.