Задача по LISP. , работа со списками

[Mokar]

Помогите пожалйста решить задачу. Нужно проверить является ли один список фрагментом другого списка. если можно какой-нибудь кусочек примера подсказать, спасибо.

[Vesper]

напиши проверку равенства первых элементов двух списков. Или найди, благо решается в одну строчку. Иначе эта тема - кандидат в "Помощь студентам"

[korvin]

собственно а шо там делать?

(defun sublistp (xs ys &key (test 'eql))
  (let ((list xs))
    (block foo
      (dolist (y ys)
        (cond ((null list)
               (return-from foo t))
              ((funcall test (first list) y)
               (setq list (cdr list)))
              (t (setq list xs))))))
 
;;; Testing:
CL-USER> (sublistp '(1 2 3) '(4 5))
NIL                                                                                                                    
CL-USER> (sublistp '(1 2 3) '(1 2 4 5 6 7))
NIL                                                                                                                    
CL-USER> (sublistp '(1 2 3) '(1 2 3 4 5 6 7))
T                                                                                                                      
CL-USER> (sublistp '(1 2 3) '(0 1 2 3 4 5 6 7))
T                                                                                                                      
CL-USER> (sublistp '(1 2 3) '(0 1 2 4 1 2 3 5 6 7))
T

[Mokar]

korvin спасибо большое за помощь
только не совсем понятно вот эта операция block foo , для чего она нужна?

Добавлено 09.03.10, 20:13
и пробовал щас запустить через MIT-GNU Scheme пишет ошибки(

[Alexey Dejneka]

Не фурычит:

CL-USER> (sublistp '(1 2 3 1 2 4) '(1 2 3 1 2 3 1 2 4 5))
NIL

Тупое решение:

(defun startp (list1 list2)
  (do ((rest1 list1 (cdr rest1))
       (rest2 list2 (cdr rest2)))
      ((null rest1)
       t)
    (cond ((null rest2)
           (return nil))
          ((not (eql (car rest1) (car rest2)))
           (return nil)))))
 
(defun sublistp (list1 list2)
  (do ((rest2 list2 (cdr rest2)))
      ((startp list1 rest2)
       t)
    (cond ((null rest2)
           (return nil)))))

Сообщение отредактировано: Alexey Dejneka - 10.03.10, 04:10

[Alexey Dejneka]

На Scheme:

(define (startp list1 list2)
  (let loop ((rest1 list1) (rest2 list2))
    (cond ((null? rest1)
           #t)
          ((null? rest2)
           #f)
          ((not (eqv? (car rest1) (car rest2)))
           #f)
          (else
           (loop (cdr rest1) (cdr rest2))))))
 
(define (sublistp list1 list2)
  (let loop ((rest2 list2))
    (cond ((startp list1 rest2)
           #t)
          ((null? rest2)
           #f)
          (else
           (loop (cdr rest2))))))

[Mokar]

я не понимаю что значат операции #f , #t ?

[Vesper]

это возврат, #f ложь (она же NIL) а #t истина (Т)

[korvin]

Цитата Alexey Dejneka @ 10.03.10, 04:02

Не фурычит:

CL-USER> (sublistp '(1 2 3 1 2 4) '(1 2 3 1 2 3 1 2 4 5))
NIL

Тупое решение:

(defun startp (list1 list2)
  (do ((rest1 list1 (cdr rest1))
       (rest2 list2 (cdr rest2)))
      ((null rest1)
       t)
    (cond ((null rest2)
           (return nil))
          ((not (eql (car rest1) (car rest2)))
           (return nil)))))
 
(defun sublistp (list1 list2)
  (do ((rest2 list2 (cdr rest2)))
      ((startp list1 rest2)
       t)
    (cond ((null rest2)
           (return nil)))))

да, это я не учел =)

Добавлено 10.03.10, 16:15

Цитата Mokar @ 09.03.10, 20:01

korvin спасибо большое за помощь
только не совсем понятно вот эта операция block foo , для чего она нужна?

Добавлено 09.03.10, 20:13
и пробовал щас запустить через MIT-GNU Scheme пишет ошибки(

в следующий раз уточняйте диалект =)

http://www.lispworks.com/documentation/HyperSpec/Body/s_block.htm#block

[Mokar]

спасибо всем за помощь, но я честно говроя половина функций не знаю что делают и вот набросал свой вариант задачи, вроде работает. проверьте правильно ли все :

(define (sps2 p1 p2)
(if (= (length p1) 0) 1
(if (> (length p1) (length p2)) 0
(if (= (car p1) (car p2))
(sps2 (cdr p1) (cdr p2)) 0))))
 
(define (sps p1 p2)
(if (> (length p1) (length p2)) 0
(if (= (sps2 p1 p2) 1) 1
(sps p1 (cdr p2)))))

[Alexey Dejneka]

Цитата Vesper @ 10.03.10, 07:23

это возврат, #f ложь (она же NIL) а #t истина (Т)

В языке Scheme, начиная по крайней мере с R⁵RS, #f (ложь), символ NIL и пустой список - это три разных объекта, в частности, NIL и () обозначают "истину". #t ("каноническая истина") и символ T также различаются.

[korvin]

Цитата Alexey Dejneka @ 10.03.10, 17:36

Цитата Vesper @ 10.03.10, 07:23

это возврат, #f ложь (она же NIL) а #t истина (Т)

В языке Scheme, начиная по крайней мере с R⁵RS, #f (ложь), символ NIL и пустой список - это три разных объекта, в частности, NIL и () обозначают "истину". #t ("каноническая истина") и символ T также различаются.

вообще-то Vesper в скобках приводил аналоги из Common Lisp'а