Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Scheme] Операции со списком

Автор: REZiaMIX 7.11.2008, 02:24

Scheme:
Есть такая задачка

Код


a) Write the function lessthan which takes a list lis as its first argument and an
atom k as its second argument. The function returns a new list which contains
the elements from lis which are less than k.

Не пойму как проводить операции со списком.

Т.е по идее алгоритм такой:

Код


1)Текущая позиция в данном списке меньше k ?
2)Если да , добавляем в новый список значение текущей позиции
3)goto 1

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

Автор: MystDeim 7.11.2008, 22:58

Сам недавно начал изучать ским, обращаться по индексу вроде нельзя. А пробегать список можно так:

Код


(define items (list 0 1 1 1 0))
(car items) ; вернёт 0
(cdr items) ; вернёт 1 1 1 0

То есть car отрезает первый элемент, cdr остальные.

Вот функция для доступа к n- элементу списка ( из книжки Харольд Абельсон "Структура интерпретация компьютерных программ")

Код


(define (list-ref items n)
    (if (= n 0) 
        (car items) 
        (list-ref (cdr items) (- n 1)))) 
(define squares (list 1 4 9 16 25)) 
(list-ref squares 3); вернёт 16

Надеюсь помог smile

Автор: VH_ 8.11.2008, 10:29

Изложение задачи на русском языке:
«Записать функцию с именем lessthen, первым аргументом которой является список lis, а вторым аргументом - атом k. Функция возвращает новый список, который содержит те элементы из списка lis, которые (в некотором смысле - VH.) меньше чем (значение - VH.) k.»
Таким образом, про индексы элементов списка речи не идет. Уточнение о том, что список «новый» важно, так как есть структуроразрушающие функции, которые в состоянии покорежить и вернуть исходный (физически) список. Если атом k не является числом, либо в списке lis есть нечисловые элементы (например, списки), то каким образом в таких случаях определить отношение "меньше"?
Вариант для списка чисел lis и числа k (обычный LISP):

Код


(defun LESSTHEN (Lis K)
 (cond
  ((null Lis) nil)
  ((< (car Lis) K) (cons (car Lis) (LESSTHEN (cdr Lis) K)))
  (T (LESSTHEN (cdr Lis) K))))

Код


(defun LESSTHEN (Lis K)
 (if Lis
  ((lambda (elem result)
    (if (< elem K) (cons elem result)
      result))
   (car Lis)
   (LESSTHEN (cdr Lis) k))))

Автор: MystDeim 8.11.2008, 11:01

Вы привели пример на коммон лисп, автор темы просил на скиме...

Автор: REZiaMIX 8.11.2008, 18:54

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

Автор: VH_ 8.11.2008, 19:41

>MystDeim
Автор темы в идее алгоритма говорит «...текущая позиция...» (то есть положение в списке) и «...значение текущей позиции...» (то есть сам элемент списка). В задании же предлагается сравнивать с данным атомом сами элементы списка, а не их позиции.
Теперь по делу:
«...как проводить операции со списком...»
Единственная «операция», которая есть в LISPе - это вызов функции (и никаких других нет). Следовательно, чтобы что-то сделать со списком, необходимо вызвать подходящую функцию, аргументом которой является список. Например,
«...как обращаться к отдельным элементам списка по индексу...»
В LISPе есть функция (nth индекс список), аргументами которой являются порядковый номер (начальный номер равен 0!) и список, и которая возвращает элемент данного списка, находящийся в позиции с данным порядковым номером (либо NIL, если данный список слишком короткий).
«...как возвратить произвольный список...»
Так как в LISPе есть только вызов функции, то каждый вызов функции возвращает значение. Поэтому при вызове функции на месте аргумента можно (и нужно, так как других средств нет) сделать вызов той функции, которая вернет необходимое значение (суперпозиция функций). Значение, возвращенное самым внешним вызовом функции, предоставляется пользователю.
«...знаю что возвращается переменная , с которой обращались посл. раз...»
В корне неверное утверждение. Во-первых, в LISPе понятие переменной (то есть ячейки памяти, содержащей значение) является излишним - без "переменных" вполне можно обойтись. Во-вторых, при вызове функции значения аргументов передаются по значению, то есть с формальным параметром связывается значение аргумента, и любые действия внутри функции (кроме экзотических структуроразрушающих) не могут изменить сам аргумент.
PS. А чего такого нет в Scheme, что есть в обычном LISPе? Разве в Scheme не переводится буквально «по шаблону»?
>MystDeim
А как Вы определили, что это CommonLISP (а не Xlisp, не AutoLISP, не InterLISP)?

Автор: MystDeim 9.11.2008, 16:06

VH_,

Цитата

А как Вы определили, что это CommonLISP (а не Xlisp, не AutoLISP, не InterLISP)

Код


(defun LESSTHEN (Lis K)

Вот по этому, хотя не спорю, возможно это и не коммон лисп. Сам имел дело только со скимом... поглядывал еще на Arc Lisp smile

В скиме чуть по другому скобки расставлены и объявление пишеться: defun -> define, скорее всего есть еще отличия.

Похоже с Вами лучше не спорить, столько всего умного написали, я всё-таки не спец по лиспу, изучить его решил только из спортивного интереса.

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

Автор: REZiaMIX 10.11.2008, 01:01

Код


a) Write the function lessthan which takes a list lis as its first argument and an
atom k as its second argument. The function returns a new list which contains
the elements from lis which are less than k.

Не подскажете как эту задачу решить на Scheme?, никак на могу придумать((

Автор: adejneka 10.11.2008, 06:16

Цитата(MystDeim @ 9.11.2008, 16:06)

Посоветуйте книжек лучше по лиспу, кроме этой Харольд Абельсон "Структура интерпретация компьютерных программ"

http://www.cliki.net/Online%20Tutorial
http://www.cliki.net/Lisp%20books

Автор: VH_ 10.11.2008, 09:47

Код


(define LESSTHEN
 (lambda (Lis K)
  (cond
   ((null? Lis) nil)
   ((< (car Lis) K) (cons (car Lis) (LESSTHEN (cdr Lis) K)))
   (else (LESSTHEN (cdr Lis) K)))))