Схема домашнего задания помощи

Question

Хорошо, поэтому я начал новый язык в классе. Мы изучаем Схему, и я не уверен, как это сделать. Когда я говорю, изучая новый язык, я имею в виду бросил домашнее задание и сказал, чтобы понять это. Несколько из них поставили меня в тупик.

Моя первая проблема:

Напишите функцию Scheme, которая возвращает истину (булева константа #t), если параметром является список, содержащий n a, за которыми следуют n b. и false в противном случае.

Вот что у меня сейчас есть:

(define aequalb
  (lambda (list)
    (let ((head (car list)) (tail (cdr list)))
      (if (= 'a head)
          ((let ((count (count + 1)))
             (let ((newTail (aequalb tail))))
             #f
             (if (= 'b head)
                 ((let ((count (count - 1)))
                    (let ((newTail (aequalb tail))))
                    #f
                    (if (null? tail)
                        (if (= count 0)
                            #t
                            #f)))))))))))

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

Answer 1

Уловка, которую я выбрал из Essentials of Programming Languages, заключается в том, чтобы всегда писать рекурсивные функции списка, обрабатывая сначала два важных случая: null (конец списка) и не null.

Итак, базовая структура функции списка выглядит примерно так:

(define some-list-function 
  (lambda (list)
    (if (null? list)
        #f
        (do-some-work-here (head list)
                           (some-list-function (tail list))))))

Обычно вы (1) проверяете на ноль (2) выполняете некоторую работу над головой и (3) возвращаетесь к хвосту.

Первое, что вам нужно сделать, это решить, какой ответ для пустого списка. Это либо #t, либо #f, но какие? Нулевой список имеет то же число a, что и b?

Далее вам нужно что-то сделать с рекурсивным случаем. Ваш базовый подход довольно хорош (хотя ваш пример кода неверен): ведите счет, который увеличивается, когда вы видите a, и уменьшается, когда вы видите b. Проблема в том, как отследить счет. Схема не имеет циклов *, поэтому вы должны делать все с помощью рекурсии. Это означает, что вам нужно передать дополнительную переменную-счетчик.

(define some-list-function 
  (lambda (list counter)
    (if (null? list)
        ; skip null's code for a second

Теперь вы должны решить, является ли голова 'a или нет, и увеличить count, если это так (уменьшить в противном случае). Но здесь нет переменной count, она просто передается между функциями. Так как это сделать?

Ну, вы должны обновить его в строке, например:

(some-list-function (tail list) (+ 1 count))

Кстати, не используйте = ни для чего, кроме цифр. Более новые, более прохладные Lisps позволяют это, но Схема требует, чтобы вы использовали eq? для символов и = для чисел. Так что для теста 'a против 'b вам понадобится

(if (eq? 'a (head tail)) ...)
; not
(if (= 'a (head tail)) ...)

Надеюсь, это поможет. Я думаю, что дал вам все кусочки, хотя есть несколько вещей, которые я пропустил. Вам нужно изменить нулевой регистр сейчас, чтобы проверить счетчик. Если это не = 0 в конце, ответ ложный.

Вы должны также поддерживать отдельную переменную flag, чтобы убедиться, что после переключения на 'b вы вернете #f, если увидите другой 'a. Таким образом, список типа '(a a a b b a b b) не пройдет по ошибке. Добавьте флаг так же, как я добавил counter выше, добавив еще один параметр функции и передавая значение при каждом рекурсивном вызове.

Наконец, если ваш учитель действительно не оказывает вам никакой помощи, и не будет, тогда вы можете прочитать основную книгу по Схеме. Я сам не использовал ничего из этого, но слышал, что они хороши: Язык программирования схем , Как разрабатывать программы или ошибаться, я думал, что был третий Забронировать онлайн бесплатно, но я не могу найти это сейчас. Я думаю, если у вас много дополнительного времени и вы хотите поразить себя, вы можете прочитать Структура и интерпретация компьютерных программ . Он учит немного Scheme и много о языках программирования.

* У него есть некоторые из этих вещей, но лучше пока их игнорировать.

Answer 2

Я бы взглянул на andmap, take и drop, которые (между ними) делают это довольно тривиальным. Да, и, по крайней мере, на данный момент, я бы, наверное, попытался забыть, что let даже существует. Не то чтобы в этом что-то было не так, но я думаю, что большинство проблем, которые вы собираетесь получить (хотя бы на некоторое время), не требуют / не будут требовать.

Answer 3

Разве нет списка ключевых слов? Я всегда использовал «alist» в качестве имени моей переменной, чтобы обойти это.

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

params: alist

возвращает true, если список равен нулю,

false, если первый элемент не является,

false, если последний элемент не b,

(aequalb (реверс (cdr (реверс (cdr alist))))) ;; снять переднюю и заднюю часть и повторить

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

---

Кроме того, с точки зрения синтаксиса вам не нужно вводить лямбда-выражение ...

(define (foo arg) (+ 1 arg))

- это функция с именем foo, берет число и добавляет к нему. Вы бы назвали это (foo 1)

Answer 4

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

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

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

• Затем код проверяет, является ли первый элемент a, а последний - b. Если это так, он снимает эти символы и повторяет.

• В противном случае что-то не так, поэтому функция возвращает false

    (define (aeqb items)
     (cond
      ((equal? '() items) #t)
      ((and (equal? "a" (car items))
             (equal? "b" (car (reverse items))))
           (aeqb (cdr (reverse (cdr (reverse items)))))) 
      (else #f)))

    (aeqb '("a" "a" "b" "b"))