Хвостовая рекурсия

[ankalagonblack]

Уже давно урывками, в основном на работе, пытаюсь приобщаться к функциональному программированию.
Узнаю кучу всякого нового и интересного, есть желание писать что-нибудь по этому поводу.
Фиг знает, кому оно будет интересно, так что основная цель - структуризация информации для себя. Если кому-то пригодится - буду рад. И еще, я начинающий ФП'шник, так

Comments

[loreley_aq]

Ой не напоминай о функциональном и логическом программировании =( Семестр Пролога вспоминается с ужасом.

[ankalagonblack]

Зря ты:) Это же интересно. Во всяком случае, элегантно. Во всяком случае, элегантнее императивного программирования. Наверное :D

[loreley_aq]

Я не спорю, что элегантно. Базы знаний и данных там красивы =) Да и механизм рекурсии тоже понравился. Но лабы, что нам давали вызывали расстройство =( Мне до сих пор эти чертовы списки сняться.
Вот пример задания
"8. Во введённом списке символов S1, S2, ..., Sn каждую указанную последовательность символов заменить другой указанной последовательностью."
"
28. Написать программу шифрации последовательности А нулей и единиц в последовательность В (также нулей и единиц), реализующую следующий алгоритм шифрации:
b ( 1 ) = a ( 1 );
b ( j ) = 1, если a ( j ) = a ( j-1 ) и b ( j ) = 0 в противном случае.
Написать также программу дешифрации В в А."

Я все конечно понимаю, но логическое программирование для такого не предназначено. Я скорее пойду на яве это напишу.

[airfairy]

Здорово!

А я учусь на курсах университета стэнфорда по искусственному интеллекту и машинному обучению. И тоже заглядываю в функциональную чащу знаний иногда. С понедельника собираюсь ходить на лекции знакомого как раз в этой области =)

[ankalagonblack]

Круто! Как в следующий раз вы к нам придете(ну или мы к вам:)), будет о чем поговорить)

[antilamer]

Hi, http://fprog.ru/ editor here. Забежал на огонек.

Замечу, что factTail эквивалентна factSimple только благодаря тому, что произведение коммутативно (они вычисляют его в разном порядке); для произвольной функции этот трюк не прокатит.

> Но важен сам факт - сделать так можно.
Да, можно; в пределе такая реализация просто-напросто выродится в хвосто-рекурсивный, т.е. де-факто циклический, пошаговый интерпретатор исходного языка. Это интересно с теоретической точки зрения, но это нельзя назвать преобразованием программы в хвосто-рекурсивную форму :)

Еще несколько замечаний:
* "Хвостовая рекурсия" - это лишь частный случай хвостового вызова; притом самый неинтересный частный случай. Если бы это было единственное применение хвостовых вызовов, я бы не колеблясь убрал поддержку хвостовых вызовов из всех функциональных языков и добавил бы старые добрые циклы. Интересное начинается, когда в хвостовой позиции находится косвенный вызов - например, вызов функции по указателю, или вызов

[antilamer]

И еще ряд приемов преобразования программ в хвосто-рекурсивную форму вот тут ближе к концу: https://docs.google.com/document/d/1pPuVJytW8bqJuzq72Rnz4t2tb9YQhgEWmCMZ8KssL5M/edit?hl=ru

[ankalagonblack]

Спасибо за интересную ссылку. Насколько я понимаю, это ваш курс лекций, и он во многом основан на SICP'е? Если да, то интересно узнать, что будет там из того, что в SICP'е не было освещено/освещено недостаточно широко? Для того, чтобы знать, что почитать не повторяя уже изученного :)

[antilamer]

1) Можно попросить разскринить предыдущий комментарий? :)

2) Да, это мой курс http://compsciclub.ru/courses/fprog ; из того, чего в SICP не было, там вот что: а) темы - свертки, моноиды и системы типов б) во всех лекциях гораздо больше параллелей с повседневным программированием на императивных языках, и все темы расширены различными знаниями, которых еще не было во времена публикации SICP, но которые я счел достойными внимания :)