Pull to refresh

Comments 209

Вы из тех, кто считает, что подсчет факториала рекурсией во многих книжках есть хороший пример на использование рекурсии?
… ну… начнем с того, что вы представляете как работает рекурсия?)
и как множится память под выделенные функции?)
Зачастую рекурсия это красивое эллегантное но жрущее ресурсы зло)
Вы никогда не слышали о хвостовой рекурсии?
> и как множится память под выделенные функции?)
Здесь поподробнее, пожалуйста, что за выделение функций…

Встречный вопрос: про tail call optimiation слышали?
Слышали, но я не только про то что мы стек будем кушать))
Так расскажите, кто, где и как ещё будет потреблять ресурсы, избыточные по сравнению с итерацией.
Даже простой вызов функции тратит весьма много вычислительных ресурсов.
Ведь сохраняется контекст программы, параметры пихаются в стек и т.д.
Блин обрезал хабр:
Как МЫ напишем так и будет, и собсно,
когда компилятор видит что это хвост — то автоматом оптимизирует до циклов, еще вопросы?
Да. Доказательства того, что «рекурсия это красивое, элегантное, но жрущее ресурсы зло», мы не услышали. «Как мы напишем, так и будет» применимо абсолютно к любой технике программирования.
А с чем собственно вы спорите?
С тем что красиво?
или с тем что ресурсы кушает?
… Рекурсии довольно обширная тема, а как ее читают в универах?)
Вот смотрите — вот так мона высчитывать факториал, или р Фибоначи.…
Из — за этого и получается что: ,, жрущее ресурсы зло,,.
И да, я противник ее использования повсеместно. если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.
Почитайте таки про оптимизацию хвостовой рекурсии (или трамплины).

Обработка многих структур данных также неотъемлемо рекурсивна.

В общем, от рекурсии не убежишь, не спрячешься. %)
Вы читаете меня через строчку, а я вас)).
Ладно попробую еще раз.
Никто не собирается убегать.
Но говорить что от циклов нужно избавится… это слишком…
>>И да, я противник ее использования повсеместно. если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.
Ключевое слово повсеместно
Я спорю с утверждением, что рекурсия априори потребляет больше ресурсов, чем эквивалентная итерация.
Если вы намекаете на то, что рядовой, не обремененный теоретическими (и вообще любыми) знаниями разработчик способен наколбасить рекурсивный код препоганого качества, я соглашусь. Проблема в том, что если человек, к примеру, не в состоянии оценить вычислительную сложность наивной реализации Фибоначчи, от него в принципе ничего хорошего ожидать не стоит.
если можно достаточно просто заменить рекурсию — циклом, я считаю что всегда это нужно делать.

Разумеется, если в коде на C++ или Java или любом другом императивном языке разработчик заменяет простой цикл хвостовой рекурсией, надлежит надавать ему по руками и код переписать.
Но проблема в том что после слов подобных вашим, рекурсию начинать избегать как огня, не понимая сути. Классический, на мой взгляд, пример: замена рекурсии рукотворным стеком аргументов в быстрой сортировке и подобных алгоритмах. Асимптотика по памяти и времени одинаковая, но нет, в голову уже вбили рекурсия — тормозное зло.
Автор зря сделал упор в заголовке на рекурсии, только вскользь упомянув ФВП, ссылочную прозрачность и прочие радости. В итоге набросились на узкую тему… впрочем, так и так бы набросились.
> Автор зря сделал упор в заголовке на рекурсии, только вскользь упомянув ФВП, ссылочную прозрачность и прочие радости.

Про ссылочную прозрачность и чистоту писал уже, на другом ресурсе. С этими понятиями оказалось еще хуже.
название провокационное, вот и набросились =) а так вы правы.
На мой взгляд, На C++, Pascal отличным примером рекурсии может стать обход дерева, реализованного в виде рекурсивного типа данных (записью с двумя ссылками на следующую и информационной частью). Вот здесь и экономия кода колоссальна, да и проблем с переполнением/скоростью не возникает.
Здорово получается, делаем рекурсию для того, чтобы избавиться от циклов, а компилятор избавляется от рекурсии в пользу циклов.
На ананизм смкхивает.
Неверно сформулирована цель создания рекурсивного алгоритма.
Делаем рекурсию, чтобы избавиться от рутины и множества кода.
Компилятор же берет на себя работу, которую нам было делать лень.

Следуя вашему утверждению — пишем на С++, чтобы избавиться от низкоуровневого кода, а компилятор все равно нашу программу в него переведет. %)
Программы пишем для людей а не для компьютеров
«Компью́терная програ́мма — последовательность инструкций, предназначенная для исполнения устройством управления вычислительной машины.» (с) педивикия
это то да, но поддержка программ осуществляется не компом, а человеком
поэтому человек глядя на код должен чётко понимать что будет делать машина.
кроме этого он должен четко понимать что надо поменять (причем с минимальными усилиями) чтобы программа работала по другому
и тут рекурсия не рулит.

допустим, было у нас вычисление 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».

угу, о чём я и говорил. появилось ветвление и дополнительная функция.

а если нужно перемножить числа фибоначчи не превышающие 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)
}
> а если нужно перемножить числа фибоначчи не превышающие n?

Функция 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», представляющую из себя груду запутанного кода
> не «первых n чисел», а «всех чисел, не превышающих n».

Ошибся чуток.

> впрочем, по ссылке очень хорошо видно ту колоссальную пропость между гламурным «native definition», который никто в здравом уме писать не будет, и «fairly fast version», представляющую из себя груду запутанного кода

Это не повод не пользоваться абстракциями.
это повод пользоваться правильными абстракциями. то есть теми, которые с одной стороны будут понятны и естественны для человека, а с другой — чётко объясняют машине, что от неё хотят.
Именно этого не делает цикл. Человек хочет получить произведение элементов списка (а не пройтись по каждому и умножить на него), а сделаются они подряд, или попарно, это неважно.
Другое дело, что оптимизация оставляет желать лучшего.
поэтому я всеми ногами за использование итераторов.
Т.е. вы начали утверждать, что циклы лучше, а в итоге оказались лучше итераторы, которые суть эмуляция ленивых списков.
не все итераторы являются «ленивыми списками». например, если у нас уже есть готовый список, то его итератор ну никак не назвать ленивым.

итераторы — сладкая форма циклов.
>если у нас уже есть готовый список, то его итератор ну никак не назвать ленивым.
Можно. Список не ленив, но итератор — ленив. Пара итераторов является ленивым списком, вне зависимости от того, где реально находится этот список, и находится ли вообще, так как реально значение будет прочитано в момент обращения к элементу итератора, что и есть ленивость.
Итераторы — не очень сладкая форма ленивого списка, источник которого в случае энергичного языка указывается явно (реальный список, элементы файла, ввод пользователя), а в Хаскеле выглядит именно как список, который тоже может как реально существовать, так и не существовать.
итератор для конечного списка может быть развёрнут в таблицу. ни о какой «ленивости» тут речи быть не может.
Не понял, что вы имели в виду, но подозреваю, что случай, когда итератор пробегает по массиву. Если так, то ленивости тут хоть отбавляй, покажите, где тут энергичность, когда исходная таблица может быть изменена по ходу пробега и итератор прочтёт, как ни странно, — последнее значение, то есть выполнит чтение лениво.
Если это не так, покажите лучше кодом, или попытайтесь сформулировать чётче.
ошибся, «пробегается по таблице», а не по массиву
имеется ввиду, что:

[1,2,3].iterate( xxx );

разворачивается в:

xxx(1);
xxx(2);
xxx(3);

Это к итераторам, насколько я вижу, имеет весьма опосредованное отношение (разве что реализовано через них). Пара итераторов — ленивый список. Действие, произведённое через итераторы, само по себе может быть нелениво, как мы и видим в данном примере. Тут нет самого итератора.
а если нужно перемножить числа фибоначчи не превышающие 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 на каждом?

Никто не говорит, что надо писать на Хаскеле критичные к скорости программы, а я что-то сомневаюсь, что тут будет battle-neck.
Основной тезис — так писать удобнее, и при этом в отличие от энергичных языков не сильно медленнее (ибо в энергичном действительно будет создание нового списка)
почему я не должен хотеть изменить один из них?

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

Я хотел бы увидеть комбинацию двух независимо написанных циклов. Так как вы спросили, что мешает их комбинированию, я предположил, что вы утверждаете, что ничто.
циклы вынесенные в отдельную функцию — это итераторы. их можно комбинировать в произвольном порядке. но не любые циклы имеет смысл куда-то выносить…
Не надо мне рассказывать, покажите лучше код, такой же лаконичный, и при этом чтобы итерация была через 2 элемента. Ну или хотя бы просто такой же лаконичный. Боюсь, что я увижу там эмуляцию ленивости при помощи итераторов, а не циклы
Не смешно
product [2, 4 .. n]

О чём я и говорил. Ушли от циклов, да ещё и even убралось, ручками оптимизировали частное условие.
что будет в случае n=1?

even не убралось, а не водилось. за ненадобностью. зачем перебирать все значения и проверять их чётность, если можно перебирать сразу только чётные значения?
Будет пустой список. Его product вычислить нельзя, но это не недостаток функции, а недостаток формулировки задачи (не сказано о том, что делать, если n <= 1).

even убралось. Прочтите исходные условия. Перемножить чётные. То, что они следуют через 1, это оптимизация, причём ручная, которая выглядит и в Хаскеле не хуже. Я вам ответил, что он не проведёт такую оптимизацию сам, но сделать список чётных можно.
even взят ради примера, давайте ещё попросим простоту чисел? И ваш шаг магически исчезнет (так как этот случай уже так не прооптимизировать), а в случае явного условия добавится isSieve.

Пойнт в том, что ручной for эффективнее, но зачастую не на порядок (а малые константы неинтересны, да и большие, если это не узкое место), а его понятность оставляет желать лучшего.
Пишем, как говорим:
someFunc n
&nbsp&nbsp| n <= 1 = 1
&nbsp&nbsp| otherwise = product [2, 4 .. n]

Конечно, а что вас смущает?
Вообще можно переписать даже так, без ветвлений:
product (1: [2, 4… n])
Тогда для пустого списка будет автоматически 1, но это излишнее упрощение, код лучше писать для человека.
блядь. сука хабра… шоб они сдохли, гнойные пидары.

короче, нет ничего плохого в бесплатной оптимизации. в частности простые числа можно искать только среди нечётных.
Это определение про скомпилированную программу. А тут идет речь о программе которая суть исходный код. Так что, по-моему ваш комментарий не в тему.
Вы забыли, что ЯПы сделали, чтобы избавиться от ручного вбивания машинного кода, а компиляторы, чтобы из этого языка делать всё обратно. Это на что смахивает?
ЯПы сделали для того код был более человекопонятен. рекурсия человекопонятна только в самых примитивных случаях.

максимальной человекопонятности можно достичь позволив человеку применять термины предметной области. то есть не «всё есть функции» или «всё есть объекты» и крутись как хочешь, а «есть человек, его зовут вася, он может сделать стул, если его попросить».
> максимальной человекопонятности можно достичь позволив человеку применять термины предметной области.

Да, правильно. Только вот конкретно Хаскель справляется с этим гораздо лучше, чем конкретно Жаба.

> то есть не «всё есть функции» или «всё есть объекты» и крутись как хочешь, а «есть человек, его зовут вася, он может сделать стул, если его попросить».

Коротенький пример из веба:

(h |/ «forum» |/ «code» *> output «this is forum/code») <|> output «couldn't match url»

Напишите что-нибудь более простое и понятное на PHP, скажем.
да-да, как же.

если бы твой код был простым и понятным, то у меня бы не возникло вопроса «что тут нафиг происходит?»
Ну в данном случае я бы не сказал, что рекурсия ближе восприятию, нежели итерация. Плюс итерация посчитает в общем случае быстрее (хотя, конечно, плохо говорить о скорости в принципе, не переходя к конкретному языку).
хорошо бы, если следующим шёл пример с обходом шахматной доски конем.
в хаскеле то это выглядит красиво. а как то же самое будет выглядеть на не функциональном языке?
Если в языке есть функции первого класса и замыкания, то это не значит, что он функциональный до мозга костей.

Эту технику AFAIK можно использовать в JS, Perl, Ruby, PHP, Python, D (правда, больше букв будет, из-за того, что там плохо с каррированием). В общем, много где.
я имел ввиду без применения функциональных фишечек
Без применения функциональных фишечек получится как с функторами в Си++ (вроде и работают, но всерьез их как-то не воспринимают).

Костыльно, в общем, будет.
погоди, погоди. Ты рассказал что циклы это goto, а разьве рекурсия не goto? Фактически рекурсия и циклы взаимозаминяемы, тут задача проектирования скорее.
Если говорить о человеке, то цикл это плохая абстракция, а рекурсия и ФВП — хорошие.

Если говорить о машине, то, собственно, хвостовая рекурсия превращается в goto, но программы ведь пишут люди и для других людей. :)
> Если говорить о человеке, то цикл это плохая абстракция, а рекурсия и ФВП — хорошие.
Откуда взята эта мысль?
Точно не могу сказать. Наверное, из SICP или из работ Бэкуса (опосредованно).
В общем она звучит как будто высосана из пальца на самом деле.
Доказательство чего? Это же ваше утверждение. Я как раз в нём сомневаюсь.
Ха-ха. Вы считаете правильным утверждать, что тигр плохое животное, а леопард — хорошее, а потом просить кого-то оспорить этот тезис? Нет уж, увольте-с.
Прежде чем спорить, подыщите аргументацию. В статье, как мне кажется, достаточно примеров. Математика тоже на моей стороне (а ей больше тыщщи лет, по сравнению с программированием).

Слив засчитан ^_^
Он не спорил, он «реквестировал доказательство» вашего утверждения, что «цикл это плохая абстракция, а рекурсия и ФВП — хорошие.». Причем он сделал это раньше, чем вы «реквестировали» его.
к сожалению английский язык не является интуитивно понятным. так что давай говорить по-русски. не то я ща начну давать ссылки на японские статьи ;-)
Всё прочитать трудно, т.к. я не в совершенстве владею английским, однако #pragma optimize read diagonal немного исправляет дело.

Давайте рассмотрим простой пример с суммой списка:
obj result = 0;

foreach(obj item in list)
result += item;

return result;
— let rec sum = function
| [] -> 0
| x :: xs -> x + sum xs
— let rec sum_taily result tail =
match tail with
| [] -> result
| x :: xs -> sum_taily (result + x) xs

let sum list = sum_taily 0 tail
— Что означают эти варианты для человека?
Первый вариант означает, что он берёт пакет (result) и затем каждое яблоко кладёт в него.
Второй (если читать прямо) означает, что он берёт первое яблоко, затем остальные кладёт в пакет, потом кладёт и это яблоко. Неоптимальный вариант, никто так явно не думает.
Третий вариант означает, что человек сначала учится перекладывать яблоки в произвольный пакет, затем берёт пустой и перекладывает яблоки в него.

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

Там в обсуждении по ссылке утверждается, что программисты (те, кто самостоятельно учился программированию, но не особо математике) мыслят примерно как я. То есть представляют себе третий вариант как последовательность итеративных вызовов sum_taily с разными result и list. А математики (те, кто занимаются математикой и немного увлеклись программированием) представляют себе sum_taily как-то иначе.

«Математики», если такие тут есть (имеются ввиду те, кто мыслит иначе), опишите как Вы это делаете.

П.С. Меня сильно смущает та статья, посколько мне сложно отказаться от мысли, что я мыслю не как математики. Всё-таки призёр областной олимпиады по ней.
Кстати, это, оказывается, холивар: lambda-the-ultimate.org/node/1014 (вот уж не подумал бы...)

> obj result = 0;
> foreach(obj item in list)
> result += item;

Этот пример все-таки хуже третьего, потому что нарушается прозрачность по ссылкам, а интуитивным его считают только из-за того, что этому обучают на первых курсах. :) К тому же, цикл нельзя использовать также, как и ФВП (макросы первого класса я еще не видел, может, ошибаюсь).

Второй и третий пример лучше, потому что они явственно показывают структурную индукцию и прозрачны по ссылкам (referentially transparent).

Другое дело, что, написав в функцию в стиле TCO, мы немного теряем в ясности намерений. %) Явной рекурсии можно избежать с помощью ФВП.
что такое «прозрачность по ссылкам»?
что такое «ФВП»?
«Прозрачность по ссылкам» это referential transparency (видел где-то такой перевод).

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

ФВП это функция высшего порядка, то есть функция, которая либо принимает одну или более функций в качестве аргументов, либо возвращает функцию в качестве результата. Например, в JS методы массива reduce, map являются ФВП.
А чем понятие «прозрачность выражения по ссылке» отличается от «выражение, состоящее из чистых функций»?
И, если ничем не отличается, чем такое выражение хуже выражения состоящего не только из чистых функций?

И, кстати, просьба не использовать сокращений. Не все из них знает каждый программист.
> А чем понятие «прозрачность выражения по ссылке» отличается от «выражение, состоящее из чистых функций»?

Это немного разные вещи, хотя они безусловно связаны. Хаскельные функции в IO монаде чистые (они ничего не меняют), но непрозрачные (все-таки имеют побочные эффекты, из-за чего их нельзя подставить). (Где-то видел пример, кажется, от Киселева — блин, не могу найти. Вот здесь есть чуть-чуть: thread.gmane.org/gmane.comp.lang.haskell.cafe/47569)

> И, кстати, просьба не использовать сокращений. Не все из них знает каждый программист.

Простите мне мою лень ;)
> Хаскельные функции в IO монаде чистые (они ничего не меняют), но непрозрачные (все-таки имеют побочные эффекты, из-за чего их нельзя подставить).
В определении Википедии чистой функцией называется детерминированная функция без побочных эффектов. Возможно я не знаком с IO монадой, но разве функции из неё детерминированы и не имеют побочных эффектов (да Вы сами написали, что имеют)?
> Typically the function subexpression is simply a function identifier. Pure expressions are often referred to as being referentially transparent.
Нашёл на wiki. Вопрос снят. Я не считаю, что любое чисто функциональное выражение понятнее и ближе человеку, чем не чисто функциональное, а значит аргументом за «лучшесть» прозрачность по ссылке для меня не является.
второе — функции высшего порядка. в данном случае имеются ввиду делегаты — динамически создаваемые функции замкнутрые на текущий контекст передаваемые другой функции в качестве параметра.
афайк, свёртка списка, которая тут имеется ввиду, никакого отношения к рекурсии не имеет.
функция свёртки на функциональных языках реализуется через рекурсию, на императивных — через цыклы.
> афайк, свёртка списка, которая тут имеется ввиду, никакого отношения к рекурсии не имеет.
Раз может быть реализована через рекурсию, значит имеет.
> функция свёртки на функциональных языках реализуется через рекурсию, на императивных — через цыклы
Почти во всех императивных языках она реализуется как через рекурсию, так и через циклы.
В чисто функциональных языках — да, только через рекурсию.
Не очень понимаю сути вопроса.
Что мешает в императивном языке реализовать свертку через рекурсию?
Поясните? Язык императивный => надо рекурсию разворачивать в циклы?
наоборот. язык императивный — цыклы нет необходимости заворачивать в рекурсию.
А кто говорит о необходимости? Хочешь — так делай, хочешь — эдак.
> в данном случае имеются ввиду делегаты — динамически создаваемые функции замкнутрые на текущий контекст передаваемые другой функции в качестве параметра.

Матчасть. Ну почему вы ее так не любите?

Я уже говорил, что такое ФВП. А делегаты это костыль. (Кстати, Вы описываете замыкания aka closure.)

> афайк, свёртка списка, которая тут имеется ввиду, никакого отношения к рекурсии не имеет.

Список это рекурсивная структура. Настойчиво учите матчасть.
не стоит учиться программированию только лишь по википедии и мануалу по хаскелю.
да, и форсировать недомемы я бы тебе тоже не реккомендовал.
ну так на JS можно вынести массив в метод sum, чтобы избежать копирования кода. И ввести метод filter, который будет фильтровать по каким-то параметрам и возвращать новый лист:

sumEven(filter(a));

Все различие в том, что в хаскеле это все уже определено.
> sumEven(filter(a));

Получаем двойное копирование массива: один массив создается в функции filter, потом передается в функцию sumEven, которая еще создает другой массив.

В JS так делать неэффективно, а в Хаскеле, из-за ленивости вычислений, это в порядке вещей.

> Все различие в том, что в хаскеле это все уже определено.

Статья-то не об этом. Читайте внимательнее.

ЗЫ: надо было брать Си для примера. ай, нехорошо получилось!
Статья не об этом. Это я писал к тому, что вы ругаетесь на дублирование кода и непонятность. что касается производительности — я не знаю, как в хаскеле работает фильтрация(там не создается еще один массив, а просто проверяется каждое значение на соотвествие фильтру? ну думаю, что это повысит производительность =) ), так что не могу сказать ничего по этому поводу.
На счет массива вы не правы в js в функцию передается ссылка на массив копируются только простые типы как строки или числа
Ну так перед тем, как передать эту ссылку, массив нужно вычислить. ^_^
Ну ладно, в JS тоже можно вычислять по ходу, передавая фильтрующее замыкание в sumEven, но я не думаю, что это будет быстрее. ведь в хаскеле оно не волшебным образом вычисляется, наверно… В общем js действительно не удачный язык для примера…
ну вобщем то можно так
var val = 2;
var sumar = ar.map(function(el){
return el%2?el:el+val;
});
UFO landed and left these words here
Ну да, ну да… «Неисповедимы пути Господни» — порой это очень подходит к рекурсивным функциям =)
UFO landed and left these words here
Циклы понятней и лучше разбираемы(понимаемы человеком), чем рекурсия.
При грамотно составленной рекурсии и при мнемоничном именовании в точности до наоборот.
Подумайте сами: в случае с циклом нужно прочитать и осмыслить введение переменных, их изменение, и еще то, что находится в теле цикла. В случае рекурсии нужно просто думать в терминах индукции.

Явной рекурсии можно избежать с помощью ФВП, тогда ее легче понять.
ИМХО, вы не правы… хотя бы потому что для достижения наилучшей производительности всегда стоит разворачиать рекурсии в циклы (оно как бе быстрее получается). Да и более менее серьезную логику лучше писать на циклах, так как в рекурсии она превратится в слабо-поддерживаемое зло.
Действительно — иногда приходиться здорово поломать голову чтобы понять как работает та или иная рекурсивная функция. Но видимо это не про джедаев хаскеля :), потому что въехать в него — это уже имхо подвиг :)
хаскель не так и сложен… скажем так, он не сильно сложнее пролога
В общем-то да, основная сложность — это пересилить себя в самом начале.

Потом начинаются непонятки с монадой IO, etc. :)
ИМХО, хаскель хуже читается, чем некоторые другие ФЯПы. Например, хуже, чем OCaml.
Ой, не знаю… Я очень восхищался OCaml, когда только познакомился, и сейчас он мне нравится, как практически единственный строгий ФП со статической типизацией, который можно реально использовать. Но по сравнению с тем же Haskell код на OCaml часто выглядит загроможденным. Это и стандартная библиотека совсем другого уровня (то что сейчас Лерой и Ко переписывают в batteries выглядит приличнее, и явно inspired by Haskell), и отсутствие полиморфных операторов, и многое другое. Ленивость я уже не упоминаю, это материя тонкая.

Жаль, что все перспективные ML-оиды сегодня на дотнете, а OCaml никто радикально менять не собирается.
Jon Harrop недавно обмолвился, что пишет на досуге бэкэнд на LLVM для OCaml, хочется надеятся, что что-нибудь в этом направлении выйдет.
Лично мне в Хаскеле не хватает системы модулей из ML'ов. :(

А так все нормально. Хаскель можно применять на практике, так же, как и OCaml.
> Хаскель можно применять на практике, так же, как и OCaml.
Конечно. Я говорил только про строгие ФЯП, Хаскель он ленивый всё-таки :-)
хоть и боян, но…
чтобы понять рекурсию надо понять рекурсию
а вообще рекурсивный вызов функции требует больше системного времени чем аналогичный цикл (запись в стек адресов возврата и т.д.)
Убейте меня тапком.

Вы же хотели рекурсию, а не цикл или итерацию.

Значит рекурсии все-таки не так хороши? :)
> хотя бы потому что для достижения наилучшей производительности всегда стоит разворачиать рекурсии в циклы (оно как бе быстрее получается)

В конце статьи есть упоминание об оптимизации хвостовой рекурсии. Внимательнее надо быть. :)

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

Ну миф же. :) Покажите мне более-менее серьезную логику, а я покажу, что Вы неправы.
вот так на-гора выдать пример я не смогу, но я думаю вы не будете отрицать что легко достижим случай 4-5 функций, рекурсивно вызывающих друг-друга причем в непостоянной последовательности

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

Я ни в коей мере не умаляю значение и крутость рекурсии. Я просто считаю, что все надо использовать там где оно нужно и не забивать микроскопом гвозди.
> вот так на-гора выдать пример я не смогу, но я думаю вы не будете отрицать что легко достижим случай 4-5 функций, рекурсивно вызывающих друг-друга причем в непостоянной последовательности

Эти проблемы исчезают, когда используется ФВП и другие фишки. Тут еще можно упомянуть, что функциональная чистота (а еще лучше полная ссылочная прозрачность) решает.

А вообще, да, при бездумном использовании ССЗБ. :)

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

Зависит от языка. В большинстве популярных ЯП так и будет. :( Но мы-то о Хаскеле! =)
честно говоря смотря на вступление к статье я подумал что мы о всех языках в принципе…
а хаскель (как и пролог, ерланг и иже с ними) это слишком нишевой язык…

внесите пожалуйста в топик про бездумное использование, ибо я то понимаю что вы хотели сказать, а вот некоторые могут не понять и не дай бог придется такой код поддерживать
Очень интересная тема, мне нравится. Хотя она и слегка для «начинающих».
Но в качестве примера стоило бы императивный язык, а не js. В js можно сделать все ваши примеры, на что вам справедливо и указывают.
Да, я теперь понимаю, что ошибся. (Думал, раз уж Хабр, то тут вероятнее знание JS/PHP, нежели C/C++/Delphi)
> это «оператор» (а точнее, инструкция, statement), которая позволяет изменить поток управления программы

любой вызов функции — это оператор, изменяющий поток выполнения программы

> это синтаксическая абстракция

вызов функции — тоже синтаксическая абстракция

> это замаскированный goto, которые суть зло (Дейкстра доказал уже в своем труде «Goto considered harmful», ЕМНИП)

любое изменение потока потока выполнения программы — это замаскированный гото

> это еще один способ «повторить себя»

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

> передавать в функции в качестве аргументов и возвращать из других функций

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

И не стыдно при такой толщине на людях-то появляться? %)
Наверное стоит трактовать термин «рекурсия» шире. Рекурсия[1], как методический подход и рекурсия[2], как техническая реализация, тогда бы было меньше споров. Если вы делаете обход дерева на циклах, то это все равно рекурсивная[1] методика, когда курсор откатывается назад. И наоборот хвостовая рекурсия[2] — никакая суть не рекурсия[1], поскольку отката курсора не производится.

Я так понимаю, что автор предлагает рассматривать объекты одного порядка (n-мерные матрицы, для которых естественная операция — итерация), как частный случай объектов более сложного порядка (деревья). Стремление в общем случае похвальное. Но честно говоря сомневаюсь, что такая абстракция сослужит добрую службу. К сожалению задачи ставятся еще слишком конкретно, чтобы эксплуатировать абстратктные методы их реализации. Действительно сопровождать такие решения будет на много сложнее. И XSLT, как проба пера в этом направлении, это подтверждает.
UFO landed and left these words here
Целью статьи является пропаганда и привлечение внимания к Хаскелю. Поэтому и заголовок такой. :)
Что-то меня не привлекает такой заголовок. Наличие множества статей с жёлтыми заголовками каким-то странным образом действуют на моё подсознание и говорят мне, что раз они используются, значит хороших аргументов в пользу написанного в статье нет. Имхо, такой пиар хорошо действует на менеджеров, но пытаться привлечь им разработчиков — как минимум неуважение к ним.
UFO landed and left these words here
«Наличие множества статей с жёлтыми заголовками» говорит о соответствующих изменениях основной массы читателей на хабре, имхо)
«В процессе мы будем пейсать на православном языке Хаскель, который очень непонятен.»
Ладно, на такой стиль изложения автор может претендовать, но причем здесь «православный язык»? Такой оборот, по-моему, вообще здесь неуместен!
Разработка | Создай haskell если будешь писать дальше
Че-то вы все в одну кучу смешали.
Показали пример на С с циклом, привели контрпример на Хаскеле с рекурсией. Но, забыли одно — то, что С-шный пример читается гораздо проще хоть и намного объемнее.
Вы про алгоритмы или языки говорите? Если про языки, то на Питоне все это решается несравнимо проще и, важно, легче для восприятия последующих поколений.

Нужна сумма массива?

>>> 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])

Эта фишка пришла в Петон из ФЯП. О чем спорите?
О том, что не надо смешивать алгоритмы и фишки :)
Это, заумно говоря, разные слои абстракции.
Списочные включения — это не фишка (ничего, кроме синтаксиса, оно в себе не несет).

Это синтаксический сахар над 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 функций.

Не поймут же. Я пробовал.

> Поэтому, надо не противопоставлять ФП с Haskell императивным языкам, а рассказывать о том, чем ФП обогощает инструментарий программиста.

Нет, пусть сами догадываются. Я даю пищу для размышлений (причем, только для тех, кто будет склонен подумать еще после прочтения такой статьи).
UFO landed and left these words here
> Ибо когда у вас одна рекурсия — все хорошо. А когда у вас их штук 5 и они вызываются друг в друге, то при ошибке становится довольно трудно выловить баг.

Приведите пример кода, пожалуйста. Посмотрим, можно ли его исправить.
UFO landed and left these words here
> я не говорю что не в состоянии выловить баг.

Так об этом речи нет. Речь идет о примере, вовлекающем несколько хаотично вызывающих друг друга взаимно-рекурсивных функциях. Где он?
UFO landed and left these words here
У меня есть друг, который разберется без дебагера. Да я и сам еще ни разу не пользовался дебагером в Хаскеле.
UFO landed and left these words here
80% того, что я реализую в С — в хаскеле невозможно.
UFO landed and left these words here
Да, по сути автор хотел сказать «рекурсия в хаскеле рулит!», но зачем-то обосрал другие языки и даже goto.
Ни от рекурсии, ни от циклов программирование не откажется.
Человек сам по себе исполнитель. Ему, в принципе, всё равно, действует он по императивной программе или функциональной — результат один и тот же.

Программу действий пишет рассудок, а исполняет тело. На самом деле может эта программа написана на языке, где рекурсия и циклы записываются одинаково. Поэтому дальнейшие споры, что ближе — рекурсия или циклы, считаю бесполезными.
А щастье наступит тогда, когда всю эту парадигму обернут в c-подобрый синтаксис.
Человек, знающий С может понять код на С++.
Человек, знающий С++ понимает код на Жабе.
Человек, знающий всё вышеперечисленное без полулитры не поймёт, что значит
foldr f z (x:xs) = f x (foldr f z xs)

Вы пробовали читать текст, написанный транслитом справа налево?
А, казалось бы, всего лишь синтаксис…
Дело привычки, не более.

В ЯП есть гораздо более важные вещи, чем синтаксис.
Фор хум хау.
Если в НИИ изучать — таки и да.
А если активно проталкивать в массы, то почему-то массы не желают переходить на передовые смоллтоки с лиспами, а пишут на языках с фигурными скобочками.
А в массы можно продвинуть только одним способом — насильственным.
UFO landed and left these words here
«for — это замаскированный goto...»
Смешно как-то… такое ощущение, будто тот, кто это писал, совершенно не думал о программировании вобщем, а ограничился какими-то принципами, правилами, кстати, не понятно толком, а надо ли вообще? Дело в том, что for — эт замаскированный jmp, который уж никак не обойдешь, хоть на хаскеле программируй, хоть на брейнфаке! Если уж ваша философия избегает goto, то не здесь нужно искать врага, не здесь!
Мне статья кажется просто банальным получением некоего впечателения от прочтения пары забавных статей. И от того, что ты что-то понял, и тебе хочется быть частью чего-то гениального, революционного, конечно же сразу бует море радости от того, что ты данную глупость освоил. И надо о ней прокричать, пусть даже аргументами будут высказывания о goto в стиле «слыхал звон, да не знаю, где он».
> Дело в том, что for — эт замаскированный jmp, который уж никак не обойдешь, хоть на хаскеле программируй, хоть на брейнфаке!

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

> Если уж ваша философия избегает goto, то не здесь нужно искать врага, не здесь!

Я могу написать статейку о тлетворном влиянии Фон-Неймановской архитектуры на умы.

ЗЫ очень сильно сумневаюсь в вашенской компетентности, товарищ. Либо подберите аргументацию, либо перестаньте писать откровенно глупые, невежественные посты (такие, как этот).
Напишите, пожалуйста.
А то вот я тоже не понял, в чём преимущество использования рекурсии в данном случае?

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(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 на второй — это разные переменные. Вот такая занятка.
Я попросил примера, где бы реализовывались циклы без побочных эффектов и обязательно средствами языка. Прошу еще раз.

SISAL — интересный ЯП, спасибо за наводку.
Only those users with full accounts are able to leave comments. Log in, please.