Схема: Как проверить, все ли элементы списка идентичны

Я хотел бы создать функцию Scheme, которая возвращает true, если ей передается список, полностью состоящий из идентичных элементов. Такой список будет '(1 1 1 1). Это даст false с чем-то вроде '(1 2 1 1).

Это то, что у меня есть до сих пор:

    (define (list-equal? lst)
      (define tmp (car lst))
      (for-each (lambda (x) 
                   (equal? x tmp))
                 lst)
      )

Очевидно, это неправильно, и я новичок в этом. Думаю, я не могу выразить шаг, на котором я должен вернуть #t или #f.

Заранее спасибо!

РЕДАКТИРОВАТЬ: я немного повозился и нашел решение, которое работает очень хорошо и с минимальным количеством кода:

(define (list-equal? lst)
 (andmap (lambda (x) 
        (equal? x (car lst)))
      lst))

Еще раз спасибо за помощь всем.


list lambda equality scheme
person Joseph    schedule 06.09.2011    source источник

Ответы (10)


arrow_upward
3
arrow_downward

Минимальное количество кода, если вам все равно, что он работает только для чисел:

(define (list-equel? lst)
  (apply = lst))

Примеры:

> (list-equel? '(1 1 2 1))
#f
> (list-equel? '(1 1 1 1))
#t
> (list-equel? '(1))
#t
person andrykonchin    schedule 06.09.2011
comment
Определенно лучшее решение, и я не могу поверить, что не подумал об этом. Хороший звонок. - person JasonFruit; 06.09.2011
comment
Хотя вам даже не нужно условие длины. (equal?) без аргументов => #t. - person JasonFruit; 06.09.2011
comment
Веселье. Когда я проверил идею, я подсознательно исправил ее на equal?. Думаю, я исправлю это для @aaz. - person JasonFruit; 06.09.2011
comment
@JasonFruit: в стандартной схеме equal? не является вариативным, как =. :-) (Я тестировал с Racket, например: equal?: ожидает 2 аргумента, учитывая 3: 1 2 3) Вам придется использовать сворачивание, извините. :-П - person Chris Jester-Young; 06.09.2011
comment
@Chris Jester-Young --- Ах. Меня ввела в заблуждение хитрость --- Хитрость 1.8, т.е. Я вернусь с комментарием. - person JasonFruit; 06.09.2011

arrow_upward
2
arrow_downward

Решение andmap хорошее, но если andmap недоступно, вы можете использовать его. Он использует базовые операции (и, или, проверку на нуль, проверку на равенство) и обрабатывает пустые списки и списки с одним элементом. Подобно реализации Шона, но вспомогательное определение не требуется.

(define (list-equal? args)
  (or (or (null? args)
          (null? (cdr args)))
      (and (eq? (car args) (cadr args))
           (list-equal? (cdr args)))))
person Lorenz Forvang    schedule 02.02.2014
comment
(or 1 2 3) также является законным. - person Will Ness; 02.02.2014

arrow_upward
0
arrow_downward

Попробуйте что-то вроде этого:

(define (list-equal? lst)
 (define (helper el lst)
  (or (null? lst)
      (and (eq? el (car lst))
           (helper (car lst) (cdr lst)))))
 (or (null? lst)
     (helper (car lst) (cdr lst))))

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

person Sean Devlin    schedule 06.09.2011
comment
Этот работает хорошо. Большое спасибо, я думаю, что разобрался с этим. - person Joseph; 06.09.2011

arrow_upward
0
arrow_downward

В R6RS есть функция for-all, которая принимает предикат и список и возвращает #t, если предикат возвращает true для всех элементов в списке, и #f в противном случае, что вам здесь и нужно.

Поэтому, если вы используете R6RS (или любой другой диалект схемы, который имеет функцию for-all), вы можете просто заменить for-each на for-all в своем коде, и он будет работать.

person sepp2k    schedule 06.09.2011
comment
Жаль, что для меня нет доступа ко всем. Но приятно знать, что я был на правильном пути. - person Joseph; 06.09.2011
comment
Это будет работать с добавленным шагом, который вы все равно должны проверить, что lst не пусто. - person Sean Devlin; 06.09.2011
comment
@Sean: Да, хорошая мысль. Это или избавиться от переменной tmp и просто вызывать (car lst) каждый раз в предикате (который никогда не будет вызываться для пустого списка, избегая проблемы). - person sepp2k; 06.09.2011

arrow_upward
0
arrow_downward

Что-то вроде этого должно работать:

(define (list-equal? lst)
  (cond ((< (length lst) 2) #t)
        (#t (and (equal? (car lst) (cadr lst))
             (list-equal? (cdr lst))))))
person JasonFruit    schedule 06.09.2011
comment
Это хорошо, за исключением того, что он выполняется за время O(n*n) вместо времени O(n) (поскольку для каждой позиции в списке вычисляется длина остатка списка). Если бы это было скорректировано, чтобы базовый случай был (or (null? lst) (null? (cdr lst))), у него было бы намного лучшее время выполнения, а также он был бы красивым и кратким. - person Joshua Taylor; 20.09.2013

arrow_upward
0
arrow_downward

Все остальные ответы в этой ветке кажутся слишком сложными (я прочитал их все), так что вот мой взгляд на это:

(define (all-equal? lst)
  (define item (car lst))
  (let next ((lst (cdr lst)))
    (cond ((null? lst) #t)
          ((equal? item (car lst)) (next (cdr lst)))
          (else #f))))

(Это не работает с пустым списком по замыслу. При необходимости легко добавить (if (null? lst) #t ...).)

person Chris Jester-Young    schedule 06.09.2011

arrow_upward
0
arrow_downward

Короткое, лаконичное решение:

#lang racket
(define (all-equal? lst)
  (for/and
      ([i (in-permutations lst)])
    (equal? (first i) (second i))))

; TEST CASES

(require rackunit)

(check-false (all-equal? '(1 2 3)))
(check-true (all-equal? '(1 1 1)))
(check-true (all-equal? '()))

Обратите внимание, что здесь используется рэкет, поэтому это может не работать с реализацией вашей схемы.

person Majora320    schedule 20.04.2016

arrow_upward
0
arrow_downward

Еще одно решение:

(define (all-same ls)
    (cond
     ((or (null? ls)
          (null? (cdr ls))) #t)
     (else (and (equal? (car ls) (next ls))
                (all-same (cdr ls)))))))

(define (next ls)
    (cond
     ((or (null? ls)
          (null? (cdr ls))) '())
     (else (cadr ls)))))
person mepo    schedule 12.11.2018

arrow_upward
-1
arrow_downward

Ибо плохо на этих языках. Пытаться

(define list-equal?
 (lambda (lst)
   (if (= lst null)
   (true)
   (foldr = (car lst) (cdr lst))
)))
person Patrik    schedule 06.09.2011
comment
Это не сработает. Вы сравниваете элемент списка с логическим результатом. - person Daniel; 06.09.2011

arrow_upward

arrow_downward

person    schedule
comment
Кажется, это тоже не работает, я думаю, что оно доходит до конца и жалуется, что не может использовать cadr на одиночном элементе. Я использую ракетку/Pretty Big, если это имеет значение. - person Joseph; 06.09.2011
comment
Это взорвет список с одним элементом. РЕДАКТИРОВАТЬ: Джозеф прав, он взорвется в любом списке, когда вы дойдете до его конца. - person Sean Devlin; 06.09.2011
comment
@joseph: Ты прав. Просто небольшое изменение, которое я только что сделал, должно исправить это. - person Daniel; 06.09.2011
comment
Это все равно взорвется, когда вы попытаетесь взять cdr из пустого списка. Для вашей реализации вы должны сначала проверить, что lst не является null, а затем, что (cdr lst) не является null. - person Sean Devlin; 06.09.2011