Следующая страница > 1 < [2]

Автор Сообщение

Ludmila

Members


Статус

7 сообщений

Где: Belarus
Род занятий:
Возраст:

#3424   2010-11-16 20:51 GMT+3 часа(ов)      
Здравствуйте, очень нужна Ваша помощь!

Образовать функцию amount с одним аргументом-многоуровневым списком. Она должна возвращать в качестве значения количество атомов , содержащихся в аргументе.
Также нельзя использовать метки,циклы и функции типа MAPCAR,MAPLIST,MAPCAN и MAPCON.

Заранее огромное спасибо за помощь!

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3425   2010-11-16 21:14 GMT+3 часа(ов)      
:enterprise-quality-solution
(defun amount (tree)
(typecase tree
(null 0) (atom 1)
(list (+ (amount (car tree))
(amount (cdr tree))))))

Ludmila

Members


Статус

7 сообщений

Где: Belarus
Род занятий:
Возраст:

#3426   2010-11-16 21:24 GMT+3 часа(ов)      
Можнете обьяснить что такое typecase tree???

Ludmila

Members


Статус

7 сообщений

Где: Belarus
Род занятий:
Возраст:

#3427   2010-11-16 21:28 GMT+3 часа(ов)      
Или можно какой-то другой функцией заменить , я ее еще не учила

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3428   2010-11-16 21:29 GMT+3 часа(ов)      
Вот здесь всё написано.
А если не знаете англиского, вот.

megamanx

Members


Статус

307 сообщений

Где: Russia
Род занятий:
Возраст:

#3429   2010-11-16 21:38 GMT+3 часа(ов)      
(defun cntatom (L)
(cond ((null L) 0)
((atom (car L)) (1+ (cntatom (cdr L))))
(T (cntatom (cdr L)))))
(cntatom '(1 (2) 3 (4 (5 6)) 7))
>>> 3
(defun cntatoms(L)
(cond
((null L) 0)
(T
(cond
((listp (car L)) (+ (cntatoms (car L)) (cntatoms (cdr L))))
(T (+ 1 (cntatoms (cdr L))))))))
(cntatoms '(1 (2) 3 (4 (5 6)) 7))
>>> 7
(defun cntatoms1(L n)
(cond
((null L) n)
(T
(cond
((listp (car L)) (+ (cntatoms1 (car L) 0) (cntatoms1 (cdr L) n)))
(T (cntatoms1 (cdr L) (1+ n)))))))
 
делает тоже, тока с тРу хвостовой рекурсией, всвязи с чем
(compile 'amount)
(compile 'cntatoms1)
(compile 'cntatoms)

в результате 100000 повторений (может, есть и другой способ установления скорости работы, но не искал)
(time (do  ((i 0 (1+ i))) ((> i 100000) nil) (amount '(1 2 (3 4) 5 6 ((7))))))
>> 41.812.240
(time (do ((i 0 (1+ i))) ((> i 100000) nil) (cntatoms1 '(1 2 (3 4) 5 6 ((7))) 0)))
>> 35.803.306
(time (do ((i 0 (1+ i))) ((> i 100000) nil) (cntatoms '(1 2 (3 4) 5 6 ((7))))))
>> 39.667.650

см. тут тема была, вы может из одного уч.зав.?

отредактировал(а) megamanx: 2010-11-16 21:55 GMT+3 часа(ов)
I wish I'd made you angry earlier

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#3430   2010-11-16 21:56 GMT+3 часа(ов)      
(defun F (L)
(if L
(+
(if (atom (car L)) 1
(F (car L)))
(F (cdr L)))
0))

Ludmila

Members


Статус

7 сообщений

Где: Belarus
Род занятий:
Возраст:

#3431   2010-11-16 22:08 GMT+3 часа(ов)      
Примного благодарна за помощь!!!

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3432   2010-11-16 22:24 GMT+3 часа(ов)      
> с тРу хвостовой рекурсией
Ну, кстати, здесь надо учитывать, что стандарт CL не требует TCO, так что это только у шибко-умных компиляторов вроде sbcl соптимизируется.
Наверное, такое решение стандартизаторов связано с тем, что незачем TCO языку, где есть нормальные циклы, потому что незачем использовать рекурсию, когда можно цикл.
Кроме лабораторок, конечно

> может, есть и другой способ установления скорости работы
Вот так вроде чуть удобнее:
(time
(dotimes (_ 1000000)
...))

отредактировал(а) ander-skirnir: 2010-11-16 22:33 GMT+3 часа(ов)

megamanx

Members


Статус

307 сообщений

Где: Russia
Род занятий:
Возраст:

#3433   2010-11-16 23:34 GMT+3 часа(ов)      
F всё равно быстрее всех. А кстати, методы определения сложности алгоритмов на лиспе вы не встречали? Ну, кроме общих слов из книжек по теории рекурсии и т.п. Именно для лиспа. Или для хацкеля, на худой конец.
I wish I'd made you angry earlier

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3435   2010-11-17 04:58 GMT+3 часа(ов)      
> F всё равно быстрее всех.
Если бы я писал для себя, без всяких глупых академических требований типа "нельзя использовать метки,циклы и ФВП", сделал бы так:

(defun amount (tree)
(iter (for x :in tree)
(sum (if (atom x) 1
(amount x)))))
 
(time
(dotimes (_ 20000000)
(amount '(1 2 (3 4) 5 6 ((7))))))
Evaluation took:
1.657 seconds of real time
1.650000 seconds of total run time (1.650000 user, 0.000000 system)
99.58% CPU
3,526,576,622 processor cycles
10,144 bytes consed
 
(time
(dotimes (_ 20000000)
(F '(1 2 (3 4) 5 6 ((7))))))
Evaluation took:
2.560 seconds of real time
2.550000 seconds of total run time (2.550000 user, 0.000000 system)
99.61% CPU
5,447,591,093 processor cycles
14,448 bytes consed


> методы определения сложности алгоритмов на лиспе вы не встречали?
Нет, они вроде как везде одинаковые.

joba

Members


Статус

157 сообщений

Где: ---
Род занятий:
Возраст:

#3438   2010-11-17 18:58 GMT+3 часа(ов)      
Где в беларуси учат лисп? В БУИРе чтоли?

joba

Members


Статус

157 сообщений

Где: ---
Род занятий:
Возраст:

#3439   2010-11-17 19:04 GMT+3 часа(ов)      
Цитата
незачем TCO языку, где есть нормальные циклы, потому что незачем использовать рекурсию, когда можно цикл.
Кроме лабораторок, конечно


В лямбда исчислении нету циклов. Не функциональненько с циклами писать. Цикл - это лишняя абстракция, она не нужна. Бритва Окама: «Не следует привлекать новые сущности без самой крайней на то необходимости».

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3487   2010-11-18 06:37 GMT+3 часа(ов)      
> В лямбда исчислении нету циклов.
У нас здесь программирование, а не основания математики.

> Не функциональненько с циклами писать.
А нечего на Лиспе функциональничать. Всерьёз этим заниматься на языке с аппликативным порядком редукции, мягко говоря, туповато.

joba

Members


Статус

157 сообщений

Где: ---
Род занятий:
Возраст:

#3491   2010-11-18 07:00 GMT+3 часа(ов)      
>У нас здесь программирование, а не основания математики.
Что ты имеешь в виду?
>мягко говоря, туповато
аргументируй

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3492   2010-11-18 07:12 GMT+3 часа(ов)      
> Что ты имеешь в виду?
Нам похеру, что там есть в лямбда-калкулусе, а чего нет. Мы решаем задачи как удобнее.

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

> аргументируй
Функциональный код с цепочками сложнее одной аппликации ФВП будет сильно тормозным и многопроходным в случае с аппликативным порядком.
Но, конечно, это далеко не всё. ФП на Лиспе не просто медленно, но еще и неудобно. Ввиду одного только отсутствия неявного карринга - уже непофункциональничаешь нормально.

joba

Members


Статус

157 сообщений

Где: ---
Род занятий:
Возраст:

#3493   2010-11-18 07:31 GMT+3 часа(ов)      
Нам похеру
"Нам" это кому?
>удобнее
субъективно или давай определение.
>Функциональный код с цепочками сложнее одной аппликации ФВП будет сильно тормозным и многопроходным в случае с аппликативным порядком.
Пожалуй соглашусь, такая ситуация возможна, но в, например, схеме есть абстракции, позволяющие производить ленивые вычисления.
>ФП на Лиспе не просто медленно, но еще и неудобно. Ввиду одного только отсутствия неявного карринга - уже непофункциональничаешь нормально.
Неудобство субъективно.

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3494   2010-11-18 07:47 GMT+3 часа(ов)      
> "Нам" это кому?
Лисперам, которых больше беспокоят задачи, а не функциональные красоты.

> в, например, схеме есть абстракции, позволяющие производить ленивые вычисления.
Очень мощные, надо сказать, абстракции:
(defmacro thunk (form)
`(lambda () ,form))
 
(defun force (thunk)
(funcall thunk))


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

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

joba

Members


Статус

157 сообщений

Где: ---
Род занятий:
Возраст:

#3495   2010-11-18 08:00 GMT+3 часа(ов)      
>Лисперам, которых больше беспокоят задачи, а не функциональные красоты.
Каковы тогда основные нерушимые принципы лиспа? S-выражения чтоли? Идентичность представления кода и данных?
>Очень мощные
Да я и раньше подозревал, что это гавно какое-то. Ты меня убедил окончательно.
>писать в функциональном стиле на Лиспе
Да, все таки лиспы со стратегией call by value действительно в этом плане слабы. Надо создавать новый диалект, с соответствующей стратегией.
>хаски
Да, он хорош. Но я с ним знакомился слегка и давно. Кстати, что у него с исчислением конструкции? Сделали уже или нет?

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3496   2010-11-18 08:37 GMT+3 часа(ов)      
> Каковы тогда основные нерушимые принципы лиспа? S-выражения чтоли? Идентичность представления кода и данных?
Сложный вопрос. Эти два точно. А у форта, например, есть только второе.

> гавно какое-то

Ну, чтобы честно, в рэките они "попродвинутее" - там эти санки запихиваются в структуры, обзываются composable-promises и так далее, но суть та же. В том, что вручную санковать и форсить что-то в рамках strict языка - ни к чёрту не годится, сколько вокруг этого инфраструктуры не разводи.

> Надо создавать новый диалект, с соответствующей стратегией.

Где-то читал, что кто-то из изначальной хаскибратии предлагал делать его диалектом Лиспа, но другие отказались.

> Кстати, что у него с исчислением конструкции? Сделали уже или нет?

Не знаю насчёт этого.

Кстати, в AMOP предлагают не называть лисповские "функции" таковыми, чтобы не сбивать с толку математиков и функциональщиков. Тут у нас funcallable instances.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#3498   2010-11-18 15:11 GMT+3 часа(ов)      
Цитата
VH :
(defun F (L)
(if L
(+
(if (atom (car L)) 1
(F (car L)))
(F (cdr L)))
0))


Более оптимизированный вариант:
(defun F (L)
(labels ((FN (N L)
(if L
(FN (if (consp (car L)) (FN N (car L)) (1+ N)) (cdr L))
0)))
(FN 0 L)))

>Ну, кстати, здесь надо учитывать, что стандарт CL не требует TCO, так что это только у шибко-умных компиляторов вроде sbcl соптимизируется.
TCO требует от реализации использования сложного вызова (smart call), что нелучшим образом сказывается на производительности. Поэтому циклы гораздо эффективнее.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#3500   2010-11-18 15:18 GMT+3 часа(ов)      
Цитата
ander-skirnir :
> в, например, схеме есть абстракции, позволяющие производить ленивые вычисления.
Очень мощные, надо сказать, абстракции:
(defmacro thunk (form)
`(lambda () ,form))
 
(defun force (thunk)
(funcall thunk))


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

Это ж зависит от реализации. Ленивые вычисления сродни сильнодействующему лекарству: принимаются ударной дозой коротким курсом.

отредактировал(а) misha: 2010-11-18 15:36 GMT+3 часа(ов)

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3505   2010-11-18 17:47 GMT+3 часа(ов)      
> Это ж зависит от реализации.
Нифига не зависит, если речь о схеме. Полезная ленивость предполагает полную нормальную редукцию всего, а это предполагает полное отсутствие любых побочных эффектов, полную функциональную чистоту.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#3506   2010-11-18 18:26 GMT+3 часа(ов)      
> Нифига не зависит, если речь о схеме.
Что Вы хотите сказать?

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

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

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3507   2010-11-18 21:38 GMT+3 часа(ов)      
> Надо понимать, что эти "ленивые вычисления" никак не меняют порядок редукции с аппликативного на нормальный, а позволяют разве что побаловаться с "ленивыми" точечными парами, эмулируя ленивые бесконечные списки.
> Это ж зависит от реализации.
> Нифига не зависит, если речь о схеме.
> Что Вы хотите сказать?
Что нет схемы с нормальным порядком редукции.

> это не значит, что Вы не можете писать в чистом функциональном стиле.
http://lisp.ru/forums.php?m=posts&p=3487#3487

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#3508   2010-11-18 23:54 GMT+3 часа(ов)      
> Что нет схемы с нормальным порядком редукции.
А доказать сможете? В схеме нет ленивого порядка редукции.

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3511   2010-11-19 05:09 GMT+3 часа(ов)      
Нормальный - это и есть ленивый. А энергичный - это аппликативный. Вообще, навскидку, из языков с нормальным порядком назову только хаски и миранду.

joba

Members


Статус

157 сообщений

Где: ---
Род занятий:
Возраст:

#3513   2010-11-19 06:58 GMT+3 часа(ов)      
>Нормальный - это и есть ленивый.
Не а, нормальный - это не есть ленивый. Нормальный позволяет проводить редукцию внутри абстракций. Ленивый - это вызов по необходимости или вызов по имени.
>Вообще, навскидку, из языков с нормальным порядком назову только хаски и миранду.
Не знаю на счет миранды, а в хаски используется вызов по необходимости, "в котором вместо того, чтобы перевычислять аргумент при каждом использовании, при первом вычислении все вхождения аргумента заменяются значением, и таким образом пропадает необходимость вычислять его заново в следующий раз. При такой стратегии требуется во время выполнения совместно использовать структуры данных между представлениями термов — в сущности, получается отношение редукции на графах абстрактного синтаксиса, а не на синтаксических деревьях".
http://newstar.rinet.ru/~goga/tapl/tapl007.html

ander-skirnir

Members


Статус

227 сообщений
http://lisper.ru
Где: Ukraine
Род занятий: `'`,`',`',
Возраст: 30

#3514   2010-11-19 07:34 GMT+3 часа(ов)      
> нормальный - это не есть ленивый.
Ну, call-by-need и call-by-name - это небольшие его модификации. Отличаются только выбором нормальной формы. Часто, говоря "нормальная редукция", подразумевают одну из этих двух, в зависимости от контекста обсуждения.

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#3515   2010-11-19 14:44 GMT+3 часа(ов)      
> Нормальный - это и есть ленивый.
Пиздешь и провокация) Хотя ленивый и является частным случаем нормального порядка, все-таки "модели" вычисления разные.
1) Приведите последовательности шагов для нормального и ленивого порядка редукции характерные для следующего фрагмента кода
(let* ((x (+ 10 6))
(y (* x 2)))
(+ x y 8))
2) Докажите почему в схеме нормальный порядок редукции.


Онлайн :

0 пользователь(ей), 34 гость(ей) :