Длина списка в схеме

Question

Привет. Я пытаюсь написать программу, в которой дан список списков, чтобы проверить, равны ли они по размеру, и вернуть #t, если они есть.

Так, например, если бы я написал (list-counter? '((1 2 3) (4 5 6) (7 8 9))), программа вернула бы #t и (list-counter?' ( (1 2 3) (4 5 6) (7 8))) вернет # f.

Пока это то, что я сделал:

 (define list-counter?
  (lambda (x)
    (if (list? x)
        (if (list?(car x))
      (let (l (length (car x))))
        (if (equal? l (length(car x))))
        (list-counter?(cdr x))
 ) ) ) ) ) 

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

Answer 1

Есть несколько способов решить эту проблему.Например, от руки и пошагово:

(define (all-lengths lists)
  (if (null? lists)
      '()
      (cons (length (car lists))
            (all-lengths (cdr lists)))))

(define (all-equal? head lengths)
  (if (null? lengths)
      true
      (and (= head (car lengths))
           (all-equal? head (cdr lengths)))))

(define (list-counter? lists)
  (let ((lengths (all-lengths lists)))
    (all-equal? (car lengths) (cdr lengths))))

Позвольте мне объяснить вышеописанные процедуры.Я делю проблему в два этапа: сначала создайте новый список с длинами каждого подсписка - это то, что делает all-lengths.Затем сравните первый элемент в списке с остальными элементами и посмотрите, все ли они равны - это то, что делает all-equal?.Наконец, list-counter? объединяет все вместе, вызывая обе предыдущие процедуры с правильными параметрами.

Или даже проще (и короче), используя процедуры списка (процедуры высшего порядка):

(define (list-counter? lists)
  (apply = (map length lists)))

Для понимания второго решения обратите внимание, что all-lengths и all-equal? представляют собой особые случаи более общих процедур.Когда нам нужно создать новый список с результатом применения процедуры к каждому из элементов другого списка, мы используем map.И когда нам нужно применить процедуру (= в данном случае) ко всем элементам списка одновременно , мы используем apply.И это именно то, что делает вторая версия list-counter?.

Answer 2

Вы можете написать функцию all-equal? следующим образом:

(define (all-equal? list)
  ;; (all-equal? '()) -> #t
  ;; (all-equal? '(35)) -> #t
  ;; (all-equal? '(2 3 2)) -> #f
  (if (or (null? list) (null? (cdr list)))
      #t
      (reduce equal? list)
  ))

, затем сделать:

(all-equal? (map length listOfLists))

---

В качестве альтернативы вы можете сделать:

(define (lists-same-size? list-of-lists)
    (if (== (length listOfLists) 0)
      #t
      (let*
        (( firstLength
             (length (car listOfLists)) )
         ( length-equal-to-first?
             (lambda (x) (== (length x) firstLength)) )
        )
        (reduce and #t (map length-equal-to-first? listOfLists))
      )
    )))

Что это говорит о том, что: если длина списка равна 0, наше утверждение пусто верно, в противном случае мы фиксируем первый элемент длины списка (в части 'else' * -22-предложения), помещаем его взамыкание, определенное синтаксическим сахаром let (на самом деле лямбда), и использование его для определения функции length-equal-to-first?.

К сожалению reduce не ленив.Что нам действительно нужно, так это избегать вычисления длин списков, если мы обнаружим, что только один не равен.Таким образом, чтобы быть более эффективным, мы могли бы сделать:

    ...
       (let*
         ...   
         ( all-match?               ;; lazy
             (lambda (pred list)
               (if (null? list) 
                   #t 
                   (and (pred (first list)) (all-match? (cdr list)))
                      ;;^^^^^^^^^^^^^^^^^^^ stops recursion if this is false
             )) )
        )
        (all-match? length-equal-to-first? listOfLists)
      )
    )))

Обратите внимание, что all-match? уже эффективно определено для вас с (list-search-positive list pred) или (for-all? list pred) схемы MIT или в Racket как andmap.

---

Почему запись занимает так много времени?

Вы вынуждены писать базовый вариант, потому что ваше сокращение не имеет канонического элемента, поскольку оно опирается на первыйЭлемент и список манипуляций в большинстве языков не очень мощные.У вас даже будет такая же проблема в других языках, таких как Python.В случае, если это помогает:

второй метод:

if len(listOfLists)==0:
    return True
else:
    firstLength = len(listOfLists[0])
    return all(len(x)==firstLength for x in listOfLists)

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

первый метод:

if len(listOfLists)<2:
    return True
else:
    return reduce(lambda a,b: a==b, listOfLists)

Answer 3

Это может звучать немного странно, но я думаю, что это легко.

Запустите список вниз, создав новый список, содержащий длину каждого (содержащегося) списка, то есть длину карты.Запустите составленный список длин, сравнивая голову с остальными, верните #t, если они все совпадают с головой.Верните false, как только он не совпадет с головой.