Товарищи, так как занимаюсь функциональным программирование всего неделю, страшным словом для меня является "рекурсия":) Простые функции еще поддаются пониманию(факториалы, длина списка и т.п.), но вот возникли две задачи, которые я реализовал итеративно и не придумал пока как сделать рекурсивные аналоги предложенных алгоритмов. Уже начинает съезжать крыша...Растолкуйте, пожалуйста, как ЭТО делать:
1.    Дан список, состоящий из подсписков. Построить список, элементами которого являются наибольшие и наименьшие элементы подсписков данного списка, собранные в подсписки.
Реализовал вот так:


2.    Даны два списка, состоящие из атомов. Построить список, в котором сначала расположены четные элементы первого списка, а затем нечетные элементы второго:
Реализовал так:




 

Это сообщение отредактировал(а) Skevalt - 30.11.2006, 19:03

Во-первых, даже в императивных программах нежелательно постоянно использовать глобальные переменные; имена локальных переменных можно, например, перечислить в скобках после PROG. Во-вторых, LENGTH и NTH вычисляются за время, пропорциональное длине списка и, соответственно, номеру элемента. В результате вся программа работает намного медленнее, чем нужно. Вот несколько вариантов реализации функции, вычисляющей список (max min), на ANSI Common Lisp:

1. Если предположить, что элементами подсписков (исходного списка) не являются списки (а только атомы), то и в рекурсии нет необходимости (ежели только внутри функций MAX и MIN):

2.  Также рекурсия только внутри "внутренней" функции ODDLIST:


(Хювёнен-Сеппянен "Мир Лиспа" т.1 под именем КАЖДЫЙ-ВТОРОЙ)

В современном стандарте Common Lisp считается, что список, начинающийся с LAMBDA, не является функцией. Соответственно, нужно писать либо (mapcar #'(lambda ...)...), либо (mapcar (lambda ...) ...).

APPLY может работать очень медленно или вообще не работать с длинным списком аргументов. Лучше использовать (reduce #'max _sublist) (заодно, можно указать значение для пустого списка).

IMHO, список, начанающийся с символа LAMBDA, никогда и не являлся функцией (вызовом функции), ибо это есть лямбда-выражение, то есть форма, содержащая изображение вычислений.
Соответственно, при вычислении (mapcar (lambda ...) ...) придется вычислить и выражение (lambda ...) (так как блокирующий вычисление вызов функции QUOTE отсутствует), а это же не вызов функции... и в результате... "Error: Undefined function LAMBDA" ?
Применение лексического замыкания (function (lambda ...)) при отсутствии в замыкаемой функции свободных переменных (не наш ли это случай?) ничем не отличается от применения (quote).
А ежели APPLY (или какая другая функция) может "...вообще не работать...", то IMHO это проблема разработчиков конкретной неработающей среды, а не языка, в котором декларируется, что "...APPLY ... является функцией двух аргументов, из которых первый аргумент представляет собой функцию, которая применяется к элементам списка, составляющим второй аргумент..." и ничего не сказано про длину этого (или какого другого) списка, а что тут скажешь - список он и есть список, а то что же: 10 (100, 1000) - список, а 1001 (10001, 100001) - не список (а что тогда?).
Канечна, после недели изучения такого замечательного LISPа пора уже двигать в сторону Ассемблера (там, говорят, все очень быстро).

Рекомендую почитать 3-ю главу замечательной книги Пола Грэхэма «On Lisp»
У меня вторая задача вот так получилась:

Но по-любому проще mapcan заюзать 

как вариант: