Автор | Сообщение |
kaizer131
3 сообщений |
#2848 2010-09-14 16:08 GMT+3 часа(ов) |
Помогите пожалуйста с задачей
Определить рекурсивную функцию, возвращающую количество элементов в списке без какого-либо указываемого элемента. В лиспе пока не силён поэтому обращаюсь к знающим людям. |
|
misha![]()
1275 сообщений |
#2851 2010-09-14 18:13 GMT+3 часа(ов) |
Без счетчика и учета циклических ссылок (CONS-циклов)
(defun len (l e) отредактировал(а) misha: 2010-09-14 18:21 GMT+3 часа(ов) |
|
ander-skirnir![]()
227 сообщений |
#2852 2010-09-14 21:41 GMT+3 часа(ов) |
misha, в common-lisp, в отличии от схем,
макрос defun всегда объявляет топлевельную функцию, поэтому в этом варианте мы получаем аж две объявленных функции. В cl для локальных функций используются формы flet и labels (первая оптимизированее, но не поддерживает рекурсию). Ну и по производительности можно было чуть улучшить - счётчик в len0 не обязателен. (defun len (l e) отредактировал(а) ander-skirnir: 2010-09-14 22:23 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#2854 2010-09-14 22:00 GMT+3 часа(ов) |
>misha, в common-lisp, в отличии от схем,
А кто сказал что речь шла именно о CL? Поэтому я реализовал как можно совместимее) мой код совместим даже с Lisp 1.5) >Ну и по производительности можно было чуть улучшить - счётчик в len0 не обязателен. А там нет никакого счетчика) там используется локальная переменная, причем ее значение не изменяется в процессе вычисления. Конечно её можно заменить константой) Если бы Вы добавили счетчик, то общая производительность бы несколько возрасла засчет уменьшения нагрузки на стек. отредактировал(а) misha: 2010-09-14 22:09 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#2855 2010-09-14 22:06 GMT+3 часа(ов) |
(define (len l e) |
|
ander-skirnir![]()
227 сообщений |
#2857 2010-09-14 22:17 GMT+3 часа(ов) |
Да ладно, это распространённая путаница схемеров, пишущих на cl, и наоборот.
Я, например, в ужасе от костылей, которыми нужно обкладываться в ракете для топлевельных замыканий, связанных с локальным define ![]() > там используется локальная переменная, причем ее значение не изменяется в процессе вычисления. Конечно её можно заменить константой) Я, кстати, так и не понял, зачем она там вообще. А правосторонняя свёртка здесь жутко медленная же: (defun count-without (l e) |
|
misha![]()
1275 сообщений |
#2858 2010-09-14 22:21 GMT+3 часа(ов) |
>Я, например, в ужасе от костылей, которыми нужно обкладываться в ракете для топлевельных замыканий, связанных с локальным define
Приведите пример) >А правосторонняя свёртка здесь жутко медленная же: Вполне вероятно она реализована плохо. |
|
misha![]()
1275 сообщений |
#2859 2010-09-14 22:31 GMT+3 часа(ов) |
А хотя нет) Общая проблема сверток состоит в том, что приходится создавать промежуточный навый список.
|
|
ander-skirnir![]()
227 сообщений |
#2860 2010-09-14 22:33 GMT+3 часа(ов) |
> Вполне вероятно она реализована плохо.
Ну мужики иногда в шоке, что reduce в sbcl вытворяет - он там очень скоростной ![]() А можете глянуть, как такой фолдр на ракетке отработает? Мне кажется, проблема здесь в самом принципе правосторонней свёртки. > Приведите пример) Пожалуйста (: common-lisp: (let ((a 1) (b 2) (c 3)) racket: (define-values (foo-a foo-b foo-c) Но это еще такое дело. Главная причина, по которой я предпочитаю cl racket'у - это макро-замыкания с сайд-эффектами. В ракете макросы очень статичные и не позволяют такого: (let ((i 0)) |
|
misha![]()
1275 сообщений |
#2862 2010-09-14 23:19 GMT+3 часа(ов) |
На мой взгляд такое поведение CL ущербно) Объяснить почему?)
>В ракете макросы очень статичные и не позволяют такого: Это не совсем так) Можно и без make-parameter (define xx #f) |
|
misha![]()
1275 сообщений |
#2863 2010-09-14 23:22 GMT+3 часа(ов) |
Как оказалось почти тоже самое, что ранее реализовал я:
(define (fold-right fun start lst . lsts) Т.е. в нашем случае имеет место простая рекурсия. |
|
ander-skirnir![]()
227 сообщений |
#2864 2010-09-14 23:40 GMT+3 часа(ов) |
> На мой взгляд такое поведение CL ущербно) Объяснить почему?)
Валяйте, но это удобно, гибко, и этому посвящена целая книга. Цитата Ну сделали Вы макрос, который раскрывается в замкнутую на переменную лямбду. Но причём тут это? Речь шла о замкнутом на переменную макросе. Что Вы сделали: (define (foo-a) (xx)) Что имелось ввиду: (let ((i 0)) |
|
misha![]()
1275 сообщений |
#2865 2010-09-15 00:15 GMT+3 часа(ов) |
>Речь шла о замкнутом на переменную макросе.
Макрос не замкнут на переменную, он просто подставляет константу полученную в результате вычисления (incf i) >Что имелось ввиду: Типа это) (define-values (a b c) |
|
misha![]()
1275 сообщений |
#2866 2010-09-15 00:20 GMT+3 часа(ов) |
>Валяйте, но это удобно, гибко, и этому посвящена целая книга.
Просто мне нравится Racket, а Вам CL - вот собственно и все) И холивар разводить не стоит) |
|
ander-skirnir![]()
227 сообщений |
#2877 2010-09-15 06:09 GMT+3 часа(ов) |
> Просто мне нравится Racket, а Вам CL - вот собственно и все) И холивар разводить не стоит)
На самом деле я бы с радостью перешёл на рэкит, если бы не эти ограничения. Потому меня это всё так и расстраивает ![]() Цитата Не в обиду, но мне это напомнило "метапрограммирование шаблоны c++" ![]() Вообще, ограничение макросов пределами одной фазы кажется преступлением против лиспа. Вы на фазе компиляции прибиндили 3 константы к 3 переменным, и что? Это опять не макрос с сайд эффектом. Не могли бы Вы, пожалуйста, привести аналог вышеописанного макроса moo? А желательно сразу что-то такое (чтобы макросы и функции замыкались по одним и тем же переменным): (let ((i 0)) > Макрос не замкнут на переменную, он просто подставляет константу полученную в результате вычисления (incf i) Ну так это оно и есть. Используя в cl в макросе мутабельную форму, мы по сути неявно задаём самомодифицируемый макро-трансформер. |
|
kaizer131
3 сообщений |
#2878 2010-09-15 12:02 GMT+3 часа(ов) |
Познавательная дискуссия , а можно комментарии к коду
(defun len (l e) В часности не могу сообразить последовательность аргументов при вызове функции len |
|
Raino
18 сообщений |
#2881 2010-09-15 17:55 GMT+3 часа(ов) |
Если голова списка равна искомому элементу, то пропускает его и вызывает себя же, передавая хвост списка. Если голова не равна, то добавляет к обработанному хвосту еще единицу. Зачем там n не знаю, судя по всему оно хранит "количество элементов в пустом списке, которые не равны заданому элементу", т.е. 0.
|
|
kaizer131
3 сообщений |
#2882 2010-09-15 18:00 GMT+3 часа(ов) |
хорошо , а как передать функции список в котором необходимо произвести поиск и элемент количество вхождений которого необходимо подсчитать ?
PS: Оказывается не так просто после С++ и паскаля "мыслить" на лиспе. |
|
misha![]()
1275 сообщений |
#2883 2010-09-15 18:26 GMT+3 часа(ов) |
>Не могли бы Вы, пожалуйста, привести аналог вышеописанного макроса moo?
Программа на Racket состоит из модулей, поэтому сначала код трансформируется и переобразуется макросами, а затем уже компилируется и выполняется. Т.е. после трансформации код уже не содержит макросов. Поэтому Ваша просьба не выполнима. >Используя в cl в макросе мутабельную форму, мы по сути неявно задаём самомодифицируемый макро-трансформер. Для написания полиморфных макросов необходимо взаимодействовать с макро-трансформерами, например, (define-for-syntax i 0)для более сложных задач необходимо создавать собственные трансформеры (этому посвящена целая глава). CL-макросы посути представляют собой замыкания, со всеми вытекающими) например, если Вы при написании макроса допустили ошибку, то о ней Вы узнаете только во время выполнения программы. |
|
misha![]()
1275 сообщений |
#2884 2010-09-15 18:30 GMT+3 часа(ов) |
Цитата (len '(a s d f s) 's) |
|
LinkFly
152 сообщений |
#2885 2010-09-15 22:16 GMT+3 часа(ов) |
На CL:
(count 's '(a b s c d s m n)) Тяжело привыкнуть к простоте? ;) |
|
misha![]()
1275 сообщений |
#2897 2010-09-16 15:27 GMT+3 часа(ов) |
Я проанализировал поведение макросов со слайд-эффектом в Clisp и SBCL, и сделал неутишительный для поклонников CL вывод: только в простых случаях можно ожидать желаемый результат.
[1]> (defun t ()SBCL с этим не справился, как впрочем и с (let ((i 0)) ВЫВОД: ПРИМЕНЕНИЕ МАКРОСОВ СО СЛАЙД-ЭФФЕКТОМ МОЖЕТ ПРИВЕСТИ К НЕПРЕДСКАЗУЕМЫМ ПОСЛЕДСТВИЯМ. |
|
ander-skirnir![]()
227 сообщений |
#2901 2010-09-16 19:36 GMT+3 часа(ов) |
А оно и не должно работать. Дело в том, что сlisp - самый кривой и бажный компилятор common-lisp'а из известных. И эффект "работы" этого кода странный - вызов с всегда должен возвращать одно и то же значение.
Вот как это делается: (defmacro defun! (name &rest definition) (f1) ;> 1 (f1) ;> 1 (f2) ;> 2 (f1) ;> 1 ... |
|
misha![]()
1275 сообщений |
#2902 2010-09-16 19:51 GMT+3 часа(ов) |
>А оно и не должно работать.
И на SBCL должно работать, только правильно. Но не работает ведь) >И эффект "работы" этого кода странный Непредсказуемый результат ведь) >Вот как это делается: Не признаете опасности слайд-эффекта? Вы можете оправдывать недостатки Cl сколько Вам угодно, но я уже убедился в том, что макросы со слайд-эффектом не есть тру) |
|
ander-skirnir![]()
227 сообщений |
#2903 2010-09-16 20:31 GMT+3 часа(ов) |
> И на SBCL должно работать, только правильно. Но не работает ведь)
Нет, не должно. Это некорректный код, и его работоспособность является ошибкой компилятора. > Непредсказуемый результат ведь) А какой еще эффект ожидать от некорректного кода? > Не признаете опасности слайд-эффекта? Сайд(side, побочный)-эффекты по определению опасны. Нужна хорошая самодисциплина и понимание того, что делаешь. > я уже убедился в том, что макросы со слайд-эффектом не есть тру) Ну, наверное, так даже лучше, ведь в ином случае Вам было бы очень обидно ![]() |
|
misha![]()
1275 сообщений |
#2905 2010-09-16 20:45 GMT+3 часа(ов) |
>Это некорректный код, и его работоспособность является ошибкой компилятора.
Это Вы так считаете) >Ну, наверное, так даже лучше, ведь в ином случае Вам было бы очень обидно Так все-таки признаете, что подобное использование макросов ошибочный подход, являющийся признаком неопытности программиста. А коль так, то и нестоит нахваливать CL-макросы, ведь они не обладают предсказуемостью в отличае от макросов Racket. |
|
ander-skirnir![]()
227 сообщений |
#2906 2010-09-16 21:03 GMT+3 часа(ов) |
> Это Вы так считаете)
Стандарт так считает: http://www.lispworks.com/documentation/HyperSpec/Issues/iss104_w.htm > Так все-таки признаете... Конечно же нет. Я имел ввиду, что если бы Вы не включили подсознательно механизм вытеснения пользы таких макросов, Вам стало бы очень обидно, что в ракете ничего такого и в помине нет. |
|
misha![]()
1275 сообщений |
#2907 2010-09-16 21:17 GMT+3 часа(ов) |
>что в ракете ничего такого и в помине нет.
Если мне это потребуется, то я это реализую в качестве дополнительной библиотеки. И если Вы думаете, что компилятору поступает точно такой же код, что Вы написали, то Вы глубоко ошибаетесь. >механизм вытеснения пользы таких макросов Если мне потребуется получить какую либо информацию в процессе работы макроса, то Racket позволяет это сделать. А Вы знали об этой возможности? И это не сайд-эффект) А другой пользы от него я не вижу. |
|
misha![]()
1275 сообщений |
#2909 2010-09-17 01:56 GMT+3 часа(ов) |
Эмуляция сайд-эффекта)
> (module side-effect racketСчитайте это аналогом (defmacro defun! (name &rest definition) |
|
LinkFly
152 сообщений |
#2926 2010-09-19 14:01 GMT+3 часа(ов) |
Код на CL вообще не грамотный.
Так может писать человек не представляющий что значат в CL стадии обработки кода. ander-skirnir прав - у вас явно какое-то предубеждение. |
|