Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 209
Вы из тех, кто считает, что подсчет факториала рекурсией во многих книжках есть хороший пример на использование рекурсии?
В общем, да.
А что? :)
А что? :)
… ну… начнем с того, что вы представляете как работает рекурсия?)
и как множится память под выделенные функции?)
Зачастую рекурсия это красивое эллегантное но жрущее ресурсы зло)
и как множится память под выделенные функции?)
Зачастую рекурсия это красивое эллегантное но жрущее ресурсы зло)
> и как множится память под выделенные функции?)
Здесь поподробнее, пожалуйста, что за выделение функций…
Встречный вопрос: про tail call optimiation слышали?
Здесь поподробнее, пожалуйста, что за выделение функций…
Встречный вопрос: про tail call optimiation слышали?
Слышали, но я не только про то что мы стек будем кушать))
Так расскажите, кто, где и как ещё будет потреблять ресурсы, избыточные по сравнению с итерацией.
Блин обрезал хабр:
Как МЫ напишем так и будет, и собсно,
когда компилятор видит что это хвост — то автоматом оптимизирует до циклов, еще вопросы?
Как МЫ напишем так и будет, и собсно,
когда компилятор видит что это хвост — то автоматом оптимизирует до циклов, еще вопросы?
Да. Доказательства того, что «рекурсия это красивое, элегантное, но жрущее ресурсы зло», мы не услышали. «Как мы напишем, так и будет» применимо абсолютно к любой технике программирования.
А с чем собственно вы спорите?
С тем что красиво?
или с тем что ресурсы кушает?
… Рекурсии довольно обширная тема, а как ее читают в универах?)
Вот смотрите — вот так мона высчитывать факториал, или р Фибоначи.…
Из — за этого и получается что: ,, жрущее ресурсы зло,,.
И да, я противник ее использования повсеместно. если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.
С тем что красиво?
или с тем что ресурсы кушает?
… Рекурсии довольно обширная тема, а как ее читают в универах?)
Вот смотрите — вот так мона высчитывать факториал, или р Фибоначи.…
Из — за этого и получается что: ,, жрущее ресурсы зло,,.
И да, я противник ее использования повсеместно. если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.
Почитайте таки про оптимизацию хвостовой рекурсии (или трамплины).
Обработка многих структур данных также неотъемлемо рекурсивна.
В общем, от рекурсии не убежишь, не спрячешься. %)
Обработка многих структур данных также неотъемлемо рекурсивна.
В общем, от рекурсии не убежишь, не спрячешься. %)
Вы читаете меня через строчку, а я вас)).
Ладно попробую еще раз.
Никто не собирается убегать.
Но говорить что от циклов нужно избавится… это слишком…
>>И да, я противник ее использования повсеместно. если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.
Ключевое слово повсеместно
Ладно попробую еще раз.
Никто не собирается убегать.
Но говорить что от циклов нужно избавится… это слишком…
>>И да, я противник ее использования повсеместно. если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.
Ключевое слово повсеместно
Я спорю с утверждением, что рекурсия априори потребляет больше ресурсов, чем эквивалентная итерация.
Если вы намекаете на то, что рядовой, не обремененный теоретическими (и вообще любыми) знаниями разработчик способен наколбасить рекурсивный код препоганого качества, я соглашусь. Проблема в том, что если человек, к примеру, не в состоянии оценить вычислительную сложность наивной реализации Фибоначчи, от него в принципе ничего хорошего ожидать не стоит.
Разумеется, если в коде на C++ или Java или любом другом императивном языке разработчик заменяет простой цикл хвостовой рекурсией, надлежит надавать ему по руками и код переписать.
Но проблема в том что после слов подобных вашим, рекурсию начинать избегать как огня, не понимая сути. Классический, на мой взгляд, пример: замена рекурсии рукотворным стеком аргументов в быстрой сортировке и подобных алгоритмах. Асимптотика по памяти и времени одинаковая, но нет, в голову уже вбили рекурсия — тормозное зло.
Автор зря сделал упор в заголовке на рекурсии, только вскользь упомянув ФВП, ссылочную прозрачность и прочие радости. В итоге набросились на узкую тему… впрочем, так и так бы набросились.
Если вы намекаете на то, что рядовой, не обремененный теоретическими (и вообще любыми) знаниями разработчик способен наколбасить рекурсивный код препоганого качества, я соглашусь. Проблема в том, что если человек, к примеру, не в состоянии оценить вычислительную сложность наивной реализации Фибоначчи, от него в принципе ничего хорошего ожидать не стоит.
если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.
Разумеется, если в коде на C++ или Java или любом другом императивном языке разработчик заменяет простой цикл хвостовой рекурсией, надлежит надавать ему по руками и код переписать.
Но проблема в том что после слов подобных вашим, рекурсию начинать избегать как огня, не понимая сути. Классический, на мой взгляд, пример: замена рекурсии рукотворным стеком аргументов в быстрой сортировке и подобных алгоритмах. Асимптотика по памяти и времени одинаковая, но нет, в голову уже вбили рекурсия — тормозное зло.
Автор зря сделал упор в заголовке на рекурсии, только вскользь упомянув ФВП, ссылочную прозрачность и прочие радости. В итоге набросились на узкую тему… впрочем, так и так бы набросились.
> Автор зря сделал упор в заголовке на рекурсии, только вскользь упомянув ФВП, ссылочную прозрачность и прочие радости.
Про ссылочную прозрачность и чистоту писал уже, на другом ресурсе. С этими понятиями оказалось еще хуже.
Про ссылочную прозрачность и чистоту писал уже, на другом ресурсе. С этими понятиями оказалось еще хуже.
название провокационное, вот и набросились =) а так вы правы.
На мой взгляд, На C++, Pascal отличным примером рекурсии может стать обход дерева, реализованного в виде рекурсивного типа данных (записью с двумя ссылками на следующую и информационной частью). Вот здесь и экономия кода колоссальна, да и проблем с переполнением/скоростью не возникает.
+1
Здорово получается, делаем рекурсию для того, чтобы избавиться от циклов, а компилятор избавляется от рекурсии в пользу циклов.
На ананизм смкхивает.
На ананизм смкхивает.
Неверно сформулирована цель создания рекурсивного алгоритма.
Делаем рекурсию, чтобы избавиться от рутины и множества кода.
Компилятор же берет на себя работу, которую нам было делать лень.
Следуя вашему утверждению — пишем на С++, чтобы избавиться от низкоуровневого кода, а компилятор все равно нашу программу в него переведет. %)
Делаем рекурсию, чтобы избавиться от рутины и множества кода.
Компилятор же берет на себя работу, которую нам было делать лень.
Следуя вашему утверждению — пишем на С++, чтобы избавиться от низкоуровневого кода, а компилятор все равно нашу программу в него переведет. %)
Программы пишем для людей а не для компьютеров
«Компью́терная програ́мма — последовательность инструкций, предназначенная для исполнения устройством управления вычислительной машины.» (с) педивикия
это то да, но поддержка программ осуществляется не компом, а человеком
поэтому человек глядя на код должен чётко понимать что будет делать машина.
кроме этого он должен четко понимать что надо поменять (причем с минимальными усилиями) чтобы программа работала по другому
и тут рекурсия не рулит.
допустим, было у нас вычисление n! и надо его переделать в «произведение всех чётных чисел от 1 до n»
если у нас был цыкл, то мы просто увеличиваем вдвое шаг цикла.
а если рекурсия, то нам придётся добавить ветвление — для чётных чисел одна формула, для нечётных — другая.
допустим, было у нас вычисление n! и надо его переделать в «произведение всех чётных чисел от 1 до n»
если у нас был цыкл, то мы просто увеличиваем вдвое шаг цикла.
а если рекурсия, то нам придётся добавить ветвление — для чётных чисел одна формула, для нечётных — другая.
в рекурсии в данном случае надо будет просто поставить один иф
Вы наверно не поняли к чему я говорю. Я не за и не против рекурсии. Я за умеренное использование рекурсии… в тех местах где это надо
Вы наверно не поняли к чему я говорю. Я не за и не против рекурсии. Я за умеренное использование рекурсии… в тех местах где это надо
Вы просто не умеете их готовить — одна функция для для произвольного шага (хвостовая рекурсия). Пользуясь случаем рекламирую язык nemerle
def F(x, step = 1, acc = 1)
{
| (y,_,_) when (y<=0) => acc
| (_,_,_) => F(x-step, step, acc*x)
}
Assert.AreEqual(6,F(3));
без понятия, что тут происходит, но подозреваю, что тут вычисляется двойной факториал, а я говорил о «произведении всех чётных чисел от 1 до n».
def F2(x) { if (x%2==0) F(x,2) else F(x-1,2) }
угу, о чём я и говорил. появилось ветвление и дополнительная функция.
а если нужно перемножить числа фибоначчи не превышающие n?
а если нужно перемножить числа фибоначчи не превышающие n?
А если использовать циклы и нужно считать и двойной факториал, и произведение только четных, и тройной факториал, то у вас будет:
- дублирование кода
зато код будет простой и понятный. усложнить его я всегда успею.
есть две, противоречащие друг-другу концепции: минимизация дублирования кода и минимизация связности между участками программы.
первая — уменьшает размер программы и повышает реюзинг, но порождает сложные и запутанные зависимости. вторая — порождает простой, быстроусваиваемый и легко модифицируемый код, но плата за это — дублирование реализации простейших манипуляций.
есть две, противоречащие друг-другу концепции: минимизация дублирования кода и минимизация связности между участками программы.
первая — уменьшает размер программы и повышает реюзинг, но порождает сложные и запутанные зависимости. вторая — порождает простой, быстроусваиваемый и легко модифицируемый код, но плата за это — дублирование реализации простейших манипуляций.
, что само по себе плохо, а так же будут использоваться функции как workaround для циклов, что бы обеспечить декомпозицию. В случае рекурсии сама функция рекурсии является так же и приемом для декомпозиции.
Если интересна реализация в виде одной функции:
def F(x) {
def F2(x, step = 1, acc = 1)
{
| (y,_,_) when (y<=0) => acc
| (_,_,_) => F2(x-step, step, acc*x)
}
if (x%2==0) F2(x,2) else F2(x-1,2)
}
def F(x) {
def F2(x, step = 1, acc = 1)
{
| (y,_,_) when (y<=0) => acc
| (_,_,_) => F2(x-step, step, acc*x)
}
if (x%2==0) F2(x,2) else F2(x-1,2)
}
> а если нужно перемножить числа фибоначчи не превышающие n?
Функция fib взята отсюда: www.haskell.org/haskellwiki/The_Fibonacci_sequence#Constant-time_implementations
Функция fib взята отсюда: www.haskell.org/haskellwiki/The_Fibonacci_sequence#Constant-time_implementations
fib = fst . fib2 where
-- | Return (fib n, fib (n + 1))
fib2 0 = (1, 1)
fib2 1 = (1, 2)
fib2 n
| even n = (a*a + b*b, c*c - a*a)
| otherwise = (c*c - a*a, b*b + c*c)
where (a,b) = fib2 (n `div` 2 - 1)
c = a + b
funny n = product $ map fib [1..n]
main = putStrLn $ show $ funny 5
не «первых n чисел», а «всех чисел, не превышающих n».
впрочем, по ссылке очень хорошо видно ту колоссальную пропость между гламурным «native definition», который никто в здравом уме писать не будет, и «fairly fast version», представляющую из себя груду запутанного кода
впрочем, по ссылке очень хорошо видно ту колоссальную пропость между гламурным «native definition», который никто в здравом уме писать не будет, и «fairly fast version», представляющую из себя груду запутанного кода
> не «первых n чисел», а «всех чисел, не превышающих n».
Ошибся чуток.
> впрочем, по ссылке очень хорошо видно ту колоссальную пропость между гламурным «native definition», который никто в здравом уме писать не будет, и «fairly fast version», представляющую из себя груду запутанного кода
Это не повод не пользоваться абстракциями.
Ошибся чуток.
> впрочем, по ссылке очень хорошо видно ту колоссальную пропость между гламурным «native definition», который никто в здравом уме писать не будет, и «fairly fast version», представляющую из себя груду запутанного кода
Это не повод не пользоваться абстракциями.
это повод пользоваться правильными абстракциями. то есть теми, которые с одной стороны будут понятны и естественны для человека, а с другой — чётко объясняют машине, что от неё хотят.
Именно этого не делает цикл. Человек хочет получить произведение элементов списка (а не пройтись по каждому и умножить на него), а сделаются они подряд, или попарно, это неважно.
Другое дело, что оптимизация оставляет желать лучшего.
Другое дело, что оптимизация оставляет желать лучшего.
поэтому я всеми ногами за использование итераторов.
Т.е. вы начали утверждать, что циклы лучше, а в итоге оказались лучше итераторы, которые суть эмуляция ленивых списков.
не все итераторы являются «ленивыми списками». например, если у нас уже есть готовый список, то его итератор ну никак не назвать ленивым.
итераторы — сладкая форма циклов.
итераторы — сладкая форма циклов.
>если у нас уже есть готовый список, то его итератор ну никак не назвать ленивым.
Можно. Список не ленив, но итератор — ленив. Пара итераторов является ленивым списком, вне зависимости от того, где реально находится этот список, и находится ли вообще, так как реально значение будет прочитано в момент обращения к элементу итератора, что и есть ленивость.
Итераторы — не очень сладкая форма ленивого списка, источник которого в случае энергичного языка указывается явно (реальный список, элементы файла, ввод пользователя), а в Хаскеле выглядит именно как список, который тоже может как реально существовать, так и не существовать.
Можно. Список не ленив, но итератор — ленив. Пара итераторов является ленивым списком, вне зависимости от того, где реально находится этот список, и находится ли вообще, так как реально значение будет прочитано в момент обращения к элементу итератора, что и есть ленивость.
Итераторы — не очень сладкая форма ленивого списка, источник которого в случае энергичного языка указывается явно (реальный список, элементы файла, ввод пользователя), а в Хаскеле выглядит именно как список, который тоже может как реально существовать, так и не существовать.
итератор для конечного списка может быть развёрнут в таблицу. ни о какой «ленивости» тут речи быть не может.
Не понял, что вы имели в виду, но подозреваю, что случай, когда итератор пробегает по массиву. Если так, то ленивости тут хоть отбавляй, покажите, где тут энергичность, когда исходная таблица может быть изменена по ходу пробега и итератор прочтёт, как ни странно, — последнее значение, то есть выполнит чтение лениво.
Если это не так, покажите лучше кодом, или попытайтесь сформулировать чётче.
Если это не так, покажите лучше кодом, или попытайтесь сформулировать чётче.
а если нужно перемножить числа фибоначчи не превышающие n?
product [x | x <- fibs, x <= n]
Тут наврал. К сожалению, сказать, что fibs всё время возрастает, нельзя.
Придётся ручками:
Придётся ручками:
product (takeWhile (<= n) fibs)
а чем они отличаются?
по любому от рекурсии не осталось и следа — берётся итератор, из которого в цикле достаются значения, которые аккумулируются посредством функции умножения.
по любому от рекурсии не осталось и следа — берётся итератор, из которого в цикле достаются значения, которые аккумулируются посредством функции умножения.
В первом случае должен быть просмотрен весь (бесконечный) список, так как компилятор не знает, что все остальные числа не пройдут условие. Какой-нибудь Coq, может быть, и смог бы с этим справиться, но Хаскель не может. Разумеется, если произведение не печатать, то никаких вычислений не будет вообще.
Декларативно переписываю ваши слова в код:
Этот код ещё и читать проще.
— tenshiFunc для n это:
— перемножить. те, что чётные. от 1 до n
tenshiFunc n = (product. filter even) [1… n]
Этот код ещё и читать проще.
ага, только:
* тут нет рекурсии
* тут создаётся список, который фильтруется. эффективней в этом случае использовать итератор, который на каждом шаге выдаёт следующее чётное число. ну либо надеяться на аццкий оптимизатор, который сможет развернуть наш код в правильный цикл…
* тут нет рекурсии
* тут создаётся список, который фильтруется. эффективней в этом случае использовать итератор, который на каждом шаге выдаёт следующее чётное число. ну либо надеяться на аццкий оптимизатор, который сможет развернуть наш код в правильный цикл…
Вообще-то о том и речь, что рекурсивные filter и product можно комбинировать, а два цикла — нет, и тут не создаётся промежуточный список.
ещё раз: в данном коде рекурсии нет. реализация функции filter может быть какой угодно, хоть таблица значений.
что мешает комбинировать два цикла?
может и не создаётся… а ты уверен, что сей код будет развёртнут в цикл с шагом 2, а не в цикл с шагом 1 и вызовом функции even на каждом?
что мешает комбинировать два цикла?
может и не создаётся… а ты уверен, что сей код будет развёртнут в цикл с шагом 2, а не в цикл с шагом 1 и вызовом функции even на каждом?
что мешает комбинировать два цикла?
Скомбинируйте. Не переписав один из них, а не меняя двух исходных.
а ты уверен, что сей код будет развёртнут в цикл с шагом 2, а не в цикл с шагом 1 и вызовом функции even на каждом?
Никто не говорит, что надо писать на Хаскеле критичные к скорости программы, а я что-то сомневаюсь, что тут будет battle-neck.
Основной тезис — так писать удобнее, и при этом в отличие от энергичных языков не сильно медленнее (ибо в энергичном действительно будет создание нового списка)
Скомбинируйте. Не переписав один из них, а не меняя двух исходных.
а ты уверен, что сей код будет развёртнут в цикл с шагом 2, а не в цикл с шагом 1 и вызовом функции even на каждом?
Никто не говорит, что надо писать на Хаскеле критичные к скорости программы, а я что-то сомневаюсь, что тут будет battle-neck.
Основной тезис — так писать удобнее, и при этом в отличие от энергичных языков не сильно медленнее (ибо в энергичном действительно будет создание нового списка)
почему я не должен хотеть изменить один из них?
свёртки и делегаты не являются прерогативой функциональных языков.
свёртки и делегаты не являются прерогативой функциональных языков.
Потому что иначе это копипаст с изменением, а не комбинирование.
Я хотел бы увидеть комбинацию двух независимо написанных циклов. Так как вы спросили, что мешает их комбинированию, я предположил, что вы утверждаете, что ничто.
Я хотел бы увидеть комбинацию двух независимо написанных циклов. Так как вы спросили, что мешает их комбинированию, я предположил, что вы утверждаете, что ничто.
циклы вынесенные в отдельную функцию — это итераторы. их можно комбинировать в произвольном порядке. но не любые циклы имеет смысл куда-то выносить…
Не надо мне рассказывать, покажите лучше код, такой же лаконичный, и при этом чтобы итерация была через 2 элемента. Ну или хотя бы просто такой же лаконичный. Боюсь, что я увижу там эмуляцию ленивости при помощи итераторов, а не циклы
reduce( mult, xrange( 1, n, 2 ) )
Не смешно
О чём я и говорил. Ушли от циклов, да ещё и even убралось, ручками оптимизировали частное условие.
product [2, 4 .. n]
О чём я и говорил. Ушли от циклов, да ещё и even убралось, ручками оптимизировали частное условие.
что будет в случае n=1?
even не убралось, а не водилось. за ненадобностью. зачем перебирать все значения и проверять их чётность, если можно перебирать сразу только чётные значения?
even не убралось, а не водилось. за ненадобностью. зачем перебирать все значения и проверять их чётность, если можно перебирать сразу только чётные значения?
Будет пустой список. Его product вычислить нельзя, но это не недостаток функции, а недостаток формулировки задачи (не сказано о том, что делать, если n <= 1).
even убралось. Прочтите исходные условия. Перемножить чётные. То, что они следуют через 1, это оптимизация, причём ручная, которая выглядит и в Хаскеле не хуже. Я вам ответил, что он не проведёт такую оптимизацию сам, но сделать список чётных можно.
even взят ради примера, давайте ещё попросим простоту чисел? И ваш шаг магически исчезнет (так как этот случай уже так не прооптимизировать), а в случае явного условия добавится isSieve.
Пойнт в том, что ручной for эффективнее, но зачастую не на порядок (а малые константы неинтересны, да и большие, если это не узкое место), а его понятность оставляет желать лучшего.
even убралось. Прочтите исходные условия. Перемножить чётные. То, что они следуют через 1, это оптимизация, причём ручная, которая выглядит и в Хаскеле не хуже. Я вам ответил, что он не проведёт такую оптимизацию сам, но сделать список чётных можно.
even взят ради примера, давайте ещё попросим простоту чисел? И ваш шаг магически исчезнет (так как этот случай уже так не прооптимизировать), а в случае явного условия добавится isSieve.
Пойнт в том, что ручной for эффективнее, но зачастую не на порядок (а малые константы неинтересны, да и большие, если это не узкое место), а его понятность оставляет желать лучшего.
Это определение про скомпилированную программу. А тут идет речь о программе которая суть исходный код. Так что, по-моему ваш комментарий не в тему.
Вы забыли, что ЯПы сделали, чтобы избавиться от ручного вбивания машинного кода, а компиляторы, чтобы из этого языка делать всё обратно. Это на что смахивает?
ЯПы сделали для того код был более человекопонятен. рекурсия человекопонятна только в самых примитивных случаях.
максимальной человекопонятности можно достичь позволив человеку применять термины предметной области. то есть не «всё есть функции» или «всё есть объекты» и крутись как хочешь, а «есть человек, его зовут вася, он может сделать стул, если его попросить».
максимальной человекопонятности можно достичь позволив человеку применять термины предметной области. то есть не «всё есть функции» или «всё есть объекты» и крутись как хочешь, а «есть человек, его зовут вася, он может сделать стул, если его попросить».
> максимальной человекопонятности можно достичь позволив человеку применять термины предметной области.
Да, правильно. Только вот конкретно Хаскель справляется с этим гораздо лучше, чем конкретно Жаба.
> то есть не «всё есть функции» или «всё есть объекты» и крутись как хочешь, а «есть человек, его зовут вася, он может сделать стул, если его попросить».
Коротенький пример из веба:
(h |/ «forum» |/ «code» *> output «this is forum/code») <|> output «couldn't match url»
Напишите что-нибудь более простое и понятное на PHP, скажем.
Да, правильно. Только вот конкретно Хаскель справляется с этим гораздо лучше, чем конкретно Жаба.
> то есть не «всё есть функции» или «всё есть объекты» и крутись как хочешь, а «есть человек, его зовут вася, он может сделать стул, если его попросить».
Коротенький пример из веба:
(h |/ «forum» |/ «code» *> output «this is forum/code») <|> output «couldn't match url»
Напишите что-нибудь более простое и понятное на PHP, скажем.
Ну в данном случае я бы не сказал, что рекурсия ближе восприятию, нежели итерация. Плюс итерация посчитает в общем случае быстрее (хотя, конечно, плохо говорить о скорости в принципе, не переходя к конкретному языку).
хорошо бы, если следующим шёл пример с обходом шахматной доски конем.
в хаскеле то это выглядит красиво. а как то же самое будет выглядеть на не функциональном языке?
погоди, погоди. Ты рассказал что циклы это goto, а разьве рекурсия не goto? Фактически рекурсия и циклы взаимозаминяемы, тут задача проектирования скорее.
Если говорить о человеке, то цикл это плохая абстракция, а рекурсия и ФВП — хорошие.
Если говорить о машине, то, собственно, хвостовая рекурсия превращается в goto, но программы ведь пишут люди и для других людей. :)
Если говорить о машине, то, собственно, хвостовая рекурсия превращается в goto, но программы ведь пишут люди и для других людей. :)
Точно не могу сказать. Наверное, из SICP или из работ Бэкуса (опосредованно).
Реквестирую доказательство.
Читайте и просветляйтесь: lambda-the-ultimate.org/node/997
к сожалению английский язык не является интуитивно понятным. так что давай говорить по-русски. не то я ща начну давать ссылки на японские статьи ;-)
Кстати, это, оказывается, холивар: lambda-the-ultimate.org/node/1014 (вот уж не подумал бы...)
> obj result = 0;
> foreach(obj item in list)
> result += item;
Этот пример все-таки хуже третьего, потому что нарушается прозрачность по ссылкам, а интуитивным его считают только из-за того, что этому обучают на первых курсах. :) К тому же, цикл нельзя использовать также, как и ФВП (макросы первого класса я еще не видел, может, ошибаюсь).
Второй и третий пример лучше, потому что они явственно показывают структурную индукцию и прозрачны по ссылкам (referentially transparent).
Другое дело, что, написав в функцию в стиле TCO, мы немного теряем в ясности намерений. %) Явной рекурсии можно избежать с помощью ФВП.
> obj result = 0;
> foreach(obj item in list)
> result += item;
Этот пример все-таки хуже третьего, потому что нарушается прозрачность по ссылкам, а интуитивным его считают только из-за того, что этому обучают на первых курсах. :) К тому же, цикл нельзя использовать также, как и ФВП (макросы первого класса я еще не видел, может, ошибаюсь).
Второй и третий пример лучше, потому что они явственно показывают структурную индукцию и прозрачны по ссылкам (referentially transparent).
Другое дело, что, написав в функцию в стиле TCO, мы немного теряем в ясности намерений. %) Явной рекурсии можно избежать с помощью ФВП.
«Прозрачность по ссылкам» это referential transparency (видел где-то такой перевод).
Выражение называют прозрачным по ссылкам, если его можно заменить на результат его вычисления без изменения смысла программы. Например, арифметические выражения из математики обладают таким свойством.
ФВП это функция высшего порядка, то есть функция, которая либо принимает одну или более функций в качестве аргументов, либо возвращает функцию в качестве результата. Например, в JS методы массива reduce, map являются ФВП.
Выражение называют прозрачным по ссылкам, если его можно заменить на результат его вычисления без изменения смысла программы. Например, арифметические выражения из математики обладают таким свойством.
ФВП это функция высшего порядка, то есть функция, которая либо принимает одну или более функций в качестве аргументов, либо возвращает функцию в качестве результата. Например, в JS методы массива reduce, map являются ФВП.
> А чем понятие «прозрачность выражения по ссылке» отличается от «выражение, состоящее из чистых функций»?
Это немного разные вещи, хотя они безусловно связаны. Хаскельные функции в IO монаде чистые (они ничего не меняют), но непрозрачные (все-таки имеют побочные эффекты, из-за чего их нельзя подставить). (Где-то видел пример, кажется, от Киселева — блин, не могу найти. Вот здесь есть чуть-чуть: thread.gmane.org/gmane.comp.lang.haskell.cafe/47569)
> И, кстати, просьба не использовать сокращений. Не все из них знает каждый программист.
Простите мне мою лень ;)
Это немного разные вещи, хотя они безусловно связаны. Хаскельные функции в IO монаде чистые (они ничего не меняют), но непрозрачные (все-таки имеют побочные эффекты, из-за чего их нельзя подставить). (Где-то видел пример, кажется, от Киселева — блин, не могу найти. Вот здесь есть чуть-чуть: thread.gmane.org/gmane.comp.lang.haskell.cafe/47569)
> И, кстати, просьба не использовать сокращений. Не все из них знает каждый программист.
Простите мне мою лень ;)
второе — функции высшего порядка. в данном случае имеются ввиду делегаты — динамически создаваемые функции замкнутрые на текущий контекст передаваемые другой функции в качестве параметра.
афайк, свёртка списка, которая тут имеется ввиду, никакого отношения к рекурсии не имеет.
функция свёртки на функциональных языках реализуется через рекурсию, на императивных — через цыклы.
афайк, свёртка списка, которая тут имеется ввиду, никакого отношения к рекурсии не имеет.
функция свёртки на функциональных языках реализуется через рекурсию, на императивных — через цыклы.
> в данном случае имеются ввиду делегаты — динамически создаваемые функции замкнутрые на текущий контекст передаваемые другой функции в качестве параметра.
Матчасть. Ну почему вы ее так не любите?
Я уже говорил, что такое ФВП. А делегаты это костыль. (Кстати, Вы описываете замыкания aka closure.)
> афайк, свёртка списка, которая тут имеется ввиду, никакого отношения к рекурсии не имеет.
Список это рекурсивная структура. Настойчиво учите матчасть.
Матчасть. Ну почему вы ее так не любите?
Я уже говорил, что такое ФВП. А делегаты это костыль. (Кстати, Вы описываете замыкания aka closure.)
> афайк, свёртка списка, которая тут имеется ввиду, никакого отношения к рекурсии не имеет.
Список это рекурсивная структура. Настойчиво учите матчасть.
ну так на JS можно вынести массив в метод sum, чтобы избежать копирования кода. И ввести метод filter, который будет фильтровать по каким-то параметрам и возвращать новый лист:
sumEven(filter(a));
Все различие в том, что в хаскеле это все уже определено.
sumEven(filter(a));
Все различие в том, что в хаскеле это все уже определено.
> sumEven(filter(a));
Получаем двойное копирование массива: один массив создается в функции filter, потом передается в функцию sumEven, которая еще создает другой массив.
В JS так делать неэффективно, а в Хаскеле, из-за ленивости вычислений, это в порядке вещей.
> Все различие в том, что в хаскеле это все уже определено.
Статья-то не об этом. Читайте внимательнее.
ЗЫ: надо было брать Си для примера. ай, нехорошо получилось!
Получаем двойное копирование массива: один массив создается в функции filter, потом передается в функцию sumEven, которая еще создает другой массив.
В JS так делать неэффективно, а в Хаскеле, из-за ленивости вычислений, это в порядке вещей.
> Все различие в том, что в хаскеле это все уже определено.
Статья-то не об этом. Читайте внимательнее.
ЗЫ: надо было брать Си для примера. ай, нехорошо получилось!
Статья не об этом. Это я писал к тому, что вы ругаетесь на дублирование кода и непонятность. что касается производительности — я не знаю, как в хаскеле работает фильтрация(там не создается еще один массив, а просто проверяется каждое значение на соотвествие фильтру? ну думаю, что это повысит производительность =) ), так что не могу сказать ничего по этому поводу.
На счет массива вы не правы в js в функцию передается ссылка на массив копируются только простые типы как строки или числа
Ну так перед тем, как передать эту ссылку, массив нужно вычислить. ^_^
Ну ладно, в JS тоже можно вычислять по ходу, передавая фильтрующее замыкание в sumEven, но я не думаю, что это будет быстрее. ведь в хаскеле оно не волшебным образом вычисляется, наверно… В общем js действительно не удачный язык для примера…
ну вобщем то можно так
var val = 2;
var sumar = ar.map(function(el){
return el%2?el:el+val;
});
var val = 2;
var sumar = ar.map(function(el){
return el%2?el:el+val;
});
Циклы понятней и лучше разбираемы(понимаемы человеком), чем рекурсия.
При грамотно составленной рекурсии и при мнемоничном именовании в точности до наоборот.
Подумайте сами: в случае с циклом нужно прочитать и осмыслить введение переменных, их изменение, и еще то, что находится в теле цикла. В случае рекурсии нужно просто думать в терминах индукции.
Явной рекурсии можно избежать с помощью ФВП, тогда ее легче понять.
Явной рекурсии можно избежать с помощью ФВП, тогда ее легче понять.
ИМХО, вы не правы… хотя бы потому что для достижения наилучшей производительности всегда стоит разворачиать рекурсии в циклы (оно как бе быстрее получается). Да и более менее серьезную логику лучше писать на циклах, так как в рекурсии она превратится в слабо-поддерживаемое зло.
Действительно — иногда приходиться здорово поломать голову чтобы понять как работает та или иная рекурсивная функция. Но видимо это не про джедаев хаскеля :), потому что въехать в него — это уже имхо подвиг :)
хаскель не так и сложен… скажем так, он не сильно сложнее пролога
В общем-то да, основная сложность — это пересилить себя в самом начале.
Потом начинаются непонятки с монадой IO, etc. :)
Потом начинаются непонятки с монадой IO, etc. :)
Ой, не знаю… Я очень восхищался OCaml, когда только познакомился, и сейчас он мне нравится, как практически единственный строгий ФП со статической типизацией, который можно реально использовать. Но по сравнению с тем же Haskell код на OCaml часто выглядит загроможденным. Это и стандартная библиотека совсем другого уровня (то что сейчас Лерой и Ко переписывают в batteries выглядит приличнее, и явно inspired by Haskell), и отсутствие полиморфных операторов, и многое другое. Ленивость я уже не упоминаю, это материя тонкая.
Жаль, что все перспективные ML-оиды сегодня на дотнете, а OCaml никто радикально менять не собирается.
Jon Harrop недавно обмолвился, что пишет на досуге бэкэнд на LLVM для OCaml, хочется надеятся, что что-нибудь в этом направлении выйдет.
Жаль, что все перспективные ML-оиды сегодня на дотнете, а OCaml никто радикально менять не собирается.
Jon Harrop недавно обмолвился, что пишет на досуге бэкэнд на LLVM для OCaml, хочется надеятся, что что-нибудь в этом направлении выйдет.
хоть и боян, но…
чтобы понять рекурсию надо понять рекурсию
а вообще рекурсивный вызов функции требует больше системного времени чем аналогичный цикл (запись в стек адресов возврата и т.д.)
чтобы понять рекурсию надо понять рекурсию
а вообще рекурсивный вызов функции требует больше системного времени чем аналогичный цикл (запись в стек адресов возврата и т.д.)
> хотя бы потому что для достижения наилучшей производительности всегда стоит разворачиать рекурсии в циклы (оно как бе быстрее получается)
В конце статьи есть упоминание об оптимизации хвостовой рекурсии. Внимательнее надо быть. :)
> Да и более менее серьезную логику лучше писать на циклах, так как в рекурсии она превратится в слабо-поддерживаемое зло.
Ну миф же. :) Покажите мне более-менее серьезную логику, а я покажу, что Вы неправы.
В конце статьи есть упоминание об оптимизации хвостовой рекурсии. Внимательнее надо быть. :)
> Да и более менее серьезную логику лучше писать на циклах, так как в рекурсии она превратится в слабо-поддерживаемое зло.
Ну миф же. :) Покажите мне более-менее серьезную логику, а я покажу, что Вы неправы.
вот так на-гора выдать пример я не смогу, но я думаю вы не будете отрицать что легко достижим случай 4-5 функций, рекурсивно вызывающих друг-друга причем в непостоянной последовательности
при небольшом изменении тз такую конструкцию может понадобится переписывать наполовину, а циклы при любом исправлении тз надо править только соизмеримо с размерами исправлений тз.
Я ни в коей мере не умаляю значение и крутость рекурсии. Я просто считаю, что все надо использовать там где оно нужно и не забивать микроскопом гвозди.
при небольшом изменении тз такую конструкцию может понадобится переписывать наполовину, а циклы при любом исправлении тз надо править только соизмеримо с размерами исправлений тз.
Я ни в коей мере не умаляю значение и крутость рекурсии. Я просто считаю, что все надо использовать там где оно нужно и не забивать микроскопом гвозди.
> вот так на-гора выдать пример я не смогу, но я думаю вы не будете отрицать что легко достижим случай 4-5 функций, рекурсивно вызывающих друг-друга причем в непостоянной последовательности
Эти проблемы исчезают, когда используется ФВП и другие фишки. Тут еще можно упомянуть, что функциональная чистота (а еще лучше полная ссылочная прозрачность) решает.
А вообще, да, при бездумном использовании ССЗБ. :)
> Я просто считаю, что все надо использовать там где оно нужно и не забивать микроскопом гвозди.
Зависит от языка. В большинстве популярных ЯП так и будет. :( Но мы-то о Хаскеле! =)
Эти проблемы исчезают, когда используется ФВП и другие фишки. Тут еще можно упомянуть, что функциональная чистота (а еще лучше полная ссылочная прозрачность) решает.
А вообще, да, при бездумном использовании ССЗБ. :)
> Я просто считаю, что все надо использовать там где оно нужно и не забивать микроскопом гвозди.
Зависит от языка. В большинстве популярных ЯП так и будет. :( Но мы-то о Хаскеле! =)
честно говоря смотря на вступление к статье я подумал что мы о всех языках в принципе…
а хаскель (как и пролог, ерланг и иже с ними) это слишком нишевой язык…
внесите пожалуйста в топик про бездумное использование, ибо я то понимаю что вы хотели сказать, а вот некоторые могут не понять и не дай бог придется такой код поддерживать
а хаскель (как и пролог, ерланг и иже с ними) это слишком нишевой язык…
внесите пожалуйста в топик про бездумное использование, ибо я то понимаю что вы хотели сказать, а вот некоторые могут не понять и не дай бог придется такой код поддерживать
Очень интересная тема, мне нравится. Хотя она и слегка для «начинающих».
Но в качестве примера стоило бы императивный язык, а не js. В js можно сделать все ваши примеры, на что вам справедливо и указывают.
Но в качестве примера стоило бы императивный язык, а не js. В js можно сделать все ваши примеры, на что вам справедливо и указывают.
> это «оператор» (а точнее, инструкция, statement), которая позволяет изменить поток управления программы
любой вызов функции — это оператор, изменяющий поток выполнения программы
> это синтаксическая абстракция
вызов функции — тоже синтаксическая абстракция
> это замаскированный goto, которые суть зло (Дейкстра доказал уже в своем труде «Goto considered harmful», ЕМНИП)
любое изменение потока потока выполнения программы — это замаскированный гото
> это еще один способ «повторить себя»
как и способ: записать имя функции дважды где-либо в программе
> передавать в функции в качестве аргументов и возвращать из других функций
свёртки, итераторы, делегаты — всё это хоть и было придумано для функциональных языков, но не требует ни рекурсии, ни функционального программирования. и не надо приводить примеры на устаревших языках.
любой вызов функции — это оператор, изменяющий поток выполнения программы
> это синтаксическая абстракция
вызов функции — тоже синтаксическая абстракция
> это замаскированный goto, которые суть зло (Дейкстра доказал уже в своем труде «Goto considered harmful», ЕМНИП)
любое изменение потока потока выполнения программы — это замаскированный гото
> это еще один способ «повторить себя»
как и способ: записать имя функции дважды где-либо в программе
> передавать в функции в качестве аргументов и возвращать из других функций
свёртки, итераторы, делегаты — всё это хоть и было придумано для функциональных языков, но не требует ни рекурсии, ни функционального программирования. и не надо приводить примеры на устаревших языках.
Наверное стоит трактовать термин «рекурсия» шире. Рекурсия[1], как методический подход и рекурсия[2], как техническая реализация, тогда бы было меньше споров. Если вы делаете обход дерева на циклах, то это все равно рекурсивная[1] методика, когда курсор откатывается назад. И наоборот хвостовая рекурсия[2] — никакая суть не рекурсия[1], поскольку отката курсора не производится.
Я так понимаю, что автор предлагает рассматривать объекты одного порядка (n-мерные матрицы, для которых естественная операция — итерация), как частный случай объектов более сложного порядка (деревья). Стремление в общем случае похвальное. Но честно говоря сомневаюсь, что такая абстракция сослужит добрую службу. К сожалению задачи ставятся еще слишком конкретно, чтобы эксплуатировать абстратктные методы их реализации. Действительно сопровождать такие решения будет на много сложнее. И XSLT, как проба пера в этом направлении, это подтверждает.
Я так понимаю, что автор предлагает рассматривать объекты одного порядка (n-мерные матрицы, для которых естественная операция — итерация), как частный случай объектов более сложного порядка (деревья). Стремление в общем случае похвальное. Но честно говоря сомневаюсь, что такая абстракция сослужит добрую службу. К сожалению задачи ставятся еще слишком конкретно, чтобы эксплуатировать абстратктные методы их реализации. Действительно сопровождать такие решения будет на много сложнее. И XSLT, как проба пера в этом направлении, это подтверждает.
Целью статьи является пропаганда и привлечение внимания к Хаскелю. Поэтому и заголовок такой. :)
Что-то меня не привлекает такой заголовок. Наличие множества статей с жёлтыми заголовками каким-то странным образом действуют на моё подсознание и говорят мне, что раз они используются, значит хороших аргументов в пользу написанного в статье нет. Имхо, такой пиар хорошо действует на менеджеров, но пытаться привлечь им разработчиков — как минимум неуважение к ним.
«В процессе мы будем пейсать на православном языке Хаскель, который очень непонятен.»
Ладно, на такой стиль изложения автор может претендовать, но причем здесь «православный язык»? Такой оборот, по-моему, вообще здесь неуместен!
Ладно, на такой стиль изложения автор может претендовать, но причем здесь «православный язык»? Такой оборот, по-моему, вообще здесь неуместен!
перенеси в тематический блог
Че-то вы все в одну кучу смешали.
Показали пример на С с циклом, привели контрпример на Хаскеле с рекурсией. Но, забыли одно — то, что С-шный пример читается гораздо проще хоть и намного объемнее.
Вы про алгоритмы или языки говорите? Если про языки, то на Питоне все это решается несравнимо проще и, важно, легче для восприятия последующих поколений.
Нужна сумма массива?
Сложить четные элементы?
Не правда ли, все гораздо проще?
А вот если вы хотите сравнить алгоритмы, то давайте примеры на одном ЯП.
Показали пример на С с циклом, привели контрпример на Хаскеле с рекурсией. Но, забыли одно — то, что С-шный пример читается гораздо проще хоть и намного объемнее.
Вы про алгоритмы или языки говорите? Если про языки, то на Питоне все это решается несравнимо проще и, важно, легче для восприятия последующих поколений.
Нужна сумма массива?
>>> a=[1,2,3,4,5] >>> sum(a) 15Зачем еще какие-то функции вводить?
Сложить четные элементы?
>>> sum([x for x in a if x%2==0]) 6
Не правда ли, все гораздо проще?
А вот если вы хотите сравнить алгоритмы, то давайте примеры на одном ЯП.
Не правда ли, все гораздо проще?
Проще, чем где? Если чем в Хаскеле, то неправда.
Проще, чем где? Если чем в Хаскеле, то неправда.
sum [1..5]
sum [x | x <- a, even x]
> Зачем еще какие-то функции вводить?
Для повторного использования, вестимо. Для будущих поколений. :)
> Сложить четные элементы?
> >>> sum([x for x in a if x%2==0])
Эта фишка пришла в Петон из ФЯП. О чем спорите?
Для повторного использования, вестимо. Для будущих поколений. :)
> Сложить четные элементы?
> >>> sum([x for x in a if x%2==0])
Эта фишка пришла в Петон из ФЯП. О чем спорите?
О том, что не надо смешивать алгоритмы и фишки :)
Это, заумно говоря, разные слои абстракции.
Это, заумно говоря, разные слои абстракции.
Списочные включения — это не фишка (ничего, кроме синтаксиса, оно в себе не несет).
Это синтаксический сахар над map и filter.
Это синтаксический сахар над map и filter.
Совершенно верно.
Но вам не кажется нелогичным сравнивать чистый синтаксис с синтаксическим сахаром?
Повторю свою мысль: если вы говорите про рекурсию как алгоритмический прием, то сравните два алгоритма на одном и том же языке.
Например, на С, либо на Хаскеле. Без использования сторонних функций. Используя только ветвления, циклы, арифметические действия и рекурсию. Если вам нужны map и filter — напишите их самостоятельно и тогда вызывайте.
Но вам не кажется нелогичным сравнивать чистый синтаксис с синтаксическим сахаром?
Повторю свою мысль: если вы говорите про рекурсию как алгоритмический прием, то сравните два алгоритма на одном и том же языке.
Например, на С, либо на Хаскеле. Без использования сторонних функций. Используя только ветвления, циклы, арифметические действия и рекурсию. Если вам нужны map и filter — напишите их самостоятельно и тогда вызывайте.
> Но вам не кажется нелогичным сравнивать чистый синтаксис с синтаксическим сахаром?
А кто тут сравнивает «чистый синтаксис с синтаксическим сахаром»? Сравнивается как раз два подхода к решению задачи: один императивный, другой декларативный.
> Повторю свою мысль: если вы говорите про рекурсию как алгоритмический прием, то сравните два алгоритма на одном и том же языке.
Пойнт в том, чтобы пропеарить Хаскель. Си-то в этом не нуждается. :)
> Без использования сторонних функций.
Это тех, которые определены в стандартной библиотеке? Ну так я бы использовал то, что находится в std*.h, если бы оно там было.
> Используя только ветвления, циклы, арифметические действия и рекурсию.
В статье приводится реализация foldr, even. Что еще нужно? Список вот так определяется:
data List a = Nil | Cons a (List a)
Если заменить Nil на [], а Cons x y на (x:y), то получим стандартный список. Я не стал так вдаваться в детали, потому что тогда, ради справедливости, пришлось бы реализовывать индексирование массива с помощью указателей, что не относится к теме статьи.
> Если вам нужны map и filter — напишите их самостоятельно и тогда вызывайте.
В статье нет ни слова о map/filter. Претензия непонятна.
А кто тут сравнивает «чистый синтаксис с синтаксическим сахаром»? Сравнивается как раз два подхода к решению задачи: один императивный, другой декларативный.
> Повторю свою мысль: если вы говорите про рекурсию как алгоритмический прием, то сравните два алгоритма на одном и том же языке.
Пойнт в том, чтобы пропеарить Хаскель. Си-то в этом не нуждается. :)
> Без использования сторонних функций.
Это тех, которые определены в стандартной библиотеке? Ну так я бы использовал то, что находится в std*.h, если бы оно там было.
> Используя только ветвления, циклы, арифметические действия и рекурсию.
В статье приводится реализация foldr, even. Что еще нужно? Список вот так определяется:
data List a = Nil | Cons a (List a)
Если заменить Nil на [], а Cons x y на (x:y), то получим стандартный список. Я не стал так вдаваться в детали, потому что тогда, ради справедливости, пришлось бы реализовывать индексирование массива с помощью указателей, что не относится к теме статьи.
> Если вам нужны map и filter — напишите их самостоятельно и тогда вызывайте.
В статье нет ни слова о map/filter. Претензия непонятна.
Рекурсия никакого отношения к различиям между императивностью и функциональностью не имеет. Существуют функциональные языки без рекурсии, и рекурсию можно применять в большинстве императивных языков программирования. Так что, вы всё-таки где-то как-то подменяете понятия.
Если же вы хотите PR'ить именно Haskell, то надо бы начать с приемущество ФП, типа простоты параллельного программирования и использования higher-order функций. Собственно, на этом приемущества и заканчиваются… Но они хоть реальные.
А вообще, это пустой PR. Достаточно посмотреть на любую программу на Haskell из реального мира. Даже darcs, который написан фанатом математической физики и функционального программирования в итоге банально скатывается в какую-то головокружительную вязь из монад и arrow да в интенсивное использование native-функций на Си.
Поэтому, надо не противопоставлять ФП с Haskell императивным языкам, а рассказывать о том, чем ФП обогощает инструментарий программиста. Так оно вернее будет. IMHO, естественно.
Если же вы хотите PR'ить именно Haskell, то надо бы начать с приемущество ФП, типа простоты параллельного программирования и использования higher-order функций. Собственно, на этом приемущества и заканчиваются… Но они хоть реальные.
А вообще, это пустой PR. Достаточно посмотреть на любую программу на Haskell из реального мира. Даже darcs, который написан фанатом математической физики и функционального программирования в итоге банально скатывается в какую-то головокружительную вязь из монад и arrow да в интенсивное использование native-функций на Си.
Поэтому, надо не противопоставлять ФП с Haskell императивным языкам, а рассказывать о том, чем ФП обогощает инструментарий программиста. Так оно вернее будет. IMHO, естественно.
> Рекурсия никакого отношения к различиям между императивностью и функциональностью не имеет.
Покажите тогда способ произвести итерацию, не встроенный в язык, и не использующий побочные эффекты.
> Если же вы хотите PR'ить именно Haskell, то надо бы начать с приемущество ФП, типа простоты параллельного программирования и использования higher-order функций.
Не поймут же. Я пробовал.
> Поэтому, надо не противопоставлять ФП с Haskell императивным языкам, а рассказывать о том, чем ФП обогощает инструментарий программиста.
Нет, пусть сами догадываются. Я даю пищу для размышлений (причем, только для тех, кто будет склонен подумать еще после прочтения такой статьи).
Покажите тогда способ произвести итерацию, не встроенный в язык, и не использующий побочные эффекты.
> Если же вы хотите PR'ить именно Haskell, то надо бы начать с приемущество ФП, типа простоты параллельного программирования и использования higher-order функций.
Не поймут же. Я пробовал.
> Поэтому, надо не противопоставлять ФП с Haskell императивным языкам, а рассказывать о том, чем ФП обогощает инструментарий программиста.
Нет, пусть сами догадываются. Я даю пищу для размышлений (причем, только для тех, кто будет склонен подумать еще после прочтения такой статьи).
> Ибо когда у вас одна рекурсия — все хорошо. А когда у вас их штук 5 и они вызываются друг в друге, то при ошибке становится довольно трудно выловить баг.
Приведите пример кода, пожалуйста. Посмотрим, можно ли его исправить.
Приведите пример кода, пожалуйста. Посмотрим, можно ли его исправить.
шаманы
А щастье наступит тогда, когда всю эту парадигму обернут в c-подобрый синтаксис.
Человек, знающий С может понять код на С++.
Человек, знающий С++ понимает код на Жабе.
Человек, знающий всё вышеперечисленное без полулитры не поймёт, что значит
Человек, знающий С может понять код на С++.
Человек, знающий С++ понимает код на Жабе.
Человек, знающий всё вышеперечисленное без полулитры не поймёт, что значит
foldr f z (x:xs) = f x (foldr f z xs)
«for — это замаскированный goto...»
Смешно как-то… такое ощущение, будто тот, кто это писал, совершенно не думал о программировании вобщем, а ограничился какими-то принципами, правилами, кстати, не понятно толком, а надо ли вообще? Дело в том, что for — эт замаскированный jmp, который уж никак не обойдешь, хоть на хаскеле программируй, хоть на брейнфаке! Если уж ваша философия избегает goto, то не здесь нужно искать врага, не здесь!
Мне статья кажется просто банальным получением некоего впечателения от прочтения пары забавных статей. И от того, что ты что-то понял, и тебе хочется быть частью чего-то гениального, революционного, конечно же сразу бует море радости от того, что ты данную глупость освоил. И надо о ней прокричать, пусть даже аргументами будут высказывания о goto в стиле «слыхал звон, да не знаю, где он».
Смешно как-то… такое ощущение, будто тот, кто это писал, совершенно не думал о программировании вобщем, а ограничился какими-то принципами, правилами, кстати, не понятно толком, а надо ли вообще? Дело в том, что for — эт замаскированный jmp, который уж никак не обойдешь, хоть на хаскеле программируй, хоть на брейнфаке! Если уж ваша философия избегает goto, то не здесь нужно искать врага, не здесь!
Мне статья кажется просто банальным получением некоего впечателения от прочтения пары забавных статей. И от того, что ты что-то понял, и тебе хочется быть частью чего-то гениального, революционного, конечно же сразу бует море радости от того, что ты данную глупость освоил. И надо о ней прокричать, пусть даже аргументами будут высказывания о goto в стиле «слыхал звон, да не знаю, где он».
> Дело в том, что for — эт замаскированный jmp, который уж никак не обойдешь, хоть на хаскеле программируй, хоть на брейнфаке!
Об абстракции слыхивали когда-нибудь? О пользе, о вреде? Зачем, почему?
> Если уж ваша философия избегает goto, то не здесь нужно искать врага, не здесь!
Я могу написать статейку о тлетворном влиянии Фон-Неймановской архитектуры на умы.
ЗЫ очень сильно сумневаюсь в вашенской компетентности, товарищ. Либо подберите аргументацию, либо перестаньте писать откровенно глупые, невежественные посты (такие, как этот).
Об абстракции слыхивали когда-нибудь? О пользе, о вреде? Зачем, почему?
> Если уж ваша философия избегает goto, то не здесь нужно искать врага, не здесь!
Я могу написать статейку о тлетворном влиянии Фон-Неймановской архитектуры на умы.
ЗЫ очень сильно сумневаюсь в вашенской компетентности, товарищ. Либо подберите аргументацию, либо перестаньте писать откровенно глупые, невежественные посты (такие, как этот).
Напишите, пожалуйста.
А то вот я тоже не понял, в чём преимущество использования рекурсии в данном случае?
Да, и call, afair, это всё тот же push + jmp.
А то вот я тоже не понял, в чём преимущество использования рекурсии в данном случае?
int sum(int *a, size_t length) {
if (length == 0)
return 0;
return a[0] + sum(a+1, length-1);
}
Да, и call, afair, это всё тот же push + jmp.
> А то вот я тоже не понял, в чём преимущество использования рекурсии в данном случае?
В данном случае преимущества нету, кроме пожалуй того, что функция sum чистая получилась, из-за чего она подчиняется некоторым алгебраическим законам, из-за чего о ней можно рассуждать математицки. И она банально проще, чем если бы была написана с использованием цикла и побочных эффектов.
С другой стороны, эту функцию придется переписать в хвостово-рекурсивную форму.
С одной стороны, на Си никто так не пишет и не будет писать. С другой стороны, пост и не призывает это делать, пост пеарит Хаскель.
В данном случае преимущества нету, кроме пожалуй того, что функция sum чистая получилась, из-за чего она подчиняется некоторым алгебраическим законам, из-за чего о ней можно рассуждать математицки. И она банально проще, чем если бы была написана с использованием цикла и побочных эффектов.
С другой стороны, эту функцию придется переписать в хвостово-рекурсивную форму.
С одной стороны, на Си никто так не пишет и не будет писать. С другой стороны, пост и не призывает это делать, пост пеарит Хаскель.
Всё равно не понял.
У вас настолько возвышенное описание, что нам, земноводным, ни хрена не понятно.
что значит, что функция получилась чистая? Каким законам она подчиняется?
Какие у цикла побочные эффекты?
Чем она проще?
Какое отношение фильтрация списка имеет к рекурсии (там выше граждане про питона писали)
У вас настолько возвышенное описание, что нам, земноводным, ни хрена не понятно.
что значит, что функция получилась чистая? Каким законам она подчиняется?
Какие у цикла побочные эффекты?
Чем она проще?
Какое отношение фильтрация списка имеет к рекурсии (там выше граждане про питона писали)
А вы поизучайте теорию. Начните хотя бы с SICP.
> У вас настолько возвышенное описание, что нам, земноводным, ни хрена не понятно.
Учитесь думать абстрактно. Это сложно, я знаю.
> что значит, что функция получилась чистая?
Это значит, что у функции нету побочных эффектов, из-за чего я вполне определенно могу сказать, что sum(a, len) == sum(a, len) при всех возможных значениях a и len (это называется ссылочной прозрачностью, aka referential transparency).
Что еще это значит? Это значит, что к такой функции можно применять всяческие алгебраические преобразования (оптимизации).
> Какое отношение фильтрация списка имеет к рекурсии (там выше граждане про питона писали)
Самое наипрямейшее, потому что список определяется индуктивно. Что такое список?
— это что-то пустое (пустой список)
— это пара значение + другой список
Учитесь думать абстрактно. Это сложно, я знаю.
> что значит, что функция получилась чистая?
Это значит, что у функции нету побочных эффектов, из-за чего я вполне определенно могу сказать, что sum(a, len) == sum(a, len) при всех возможных значениях a и len (это называется ссылочной прозрачностью, aka referential transparency).
Что еще это значит? Это значит, что к такой функции можно применять всяческие алгебраические преобразования (оптимизации).
> Какое отношение фильтрация списка имеет к рекурсии (там выше граждане про питона писали)
Самое наипрямейшее, потому что список определяется индуктивно. Что такое список?
— это что-то пустое (пустой список)
— это пара значение + другой список
Вы опять же смешиваете. Функция sum(x, a[]) = (int sum = 0; for (int i = 0; i < x; i += 1) (sum += a[i]); return sum) Так же является чистой. И любой компилятор вменяемый вам об этом сообщит и этим воспользуется на всю катушку. Использование циклов никак не наделяет функцию побочными эффектами. Конечно, в каком-нибудь Haskell все функции будут чистыми, но опять же… Код выше тривиально параллелится на автомате. Аналогичная реализация на Haskell через рекурсию — не очень тривиально, потому что компилятор должен многое осознать о характере доступа к элементами массива/списка.
Так что, это просто переливание сложностей из одного сосуда в другой.
Так что, это просто переливание сложностей из одного сосуда в другой.
> Использование циклов никак не наделяет функцию побочными эффектами.
Абсолютно верно, но, следуя плану «максимум», требуются написать чистую функцию, состоящую из чистых же выражений.
Абсолютно верно, но, следуя плану «максимум», требуются написать чистую функцию, состоящую из чистых же выражений.
Так это на самом деле вопрос того, как синтаксис цикла интерпретировать. Есть такой язык SISAL, так там такие циклы рассматриваются как последовательности вычислений, в котором каждая интерация выполняется в своей scope. То есть i на первой итерации и i на второй — это разные переменные. Вот такая занятка.
Такая вот занятка и никаких side-effects.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Почему циклы должны умереть