Схема, когда использовать символы вместо строк?

Question

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

Две недели назад я решил освежить свои знания о Схеме (и ее просветлениях), внедряя какой-то математический материал, который я получил между руками, в частности, «Регулярные языки» из курса по теории автоматов и вычислений, в который я записан.

До сих пор я представлял алфавиты в виде списков символов вместо

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

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

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

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

Answer 1

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

Это означает, что два символа идентичны тогда и только тогда, когда они составлены из одинаковых символов. Невозможно различить два символа с одинаковыми символами в коде, они являются константами, одинаковыми объектами, так же как 3 и 3.

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

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

(assq 'symb  '((foo 1 2 3) (bar symb) (symb "match")))

Возвращает список (symb "match") это так же дешево, как сравнение:

(assq 4  '((0 1 2 3) (1 symb) (4 "match")))

Что возвращает список (4 "match"). Однако при использовании строк в качестве ключей assq больше не достаточно, для сравнения используется процедура eq?, вместо этого следует использовать assoc, которая использует процедуру equal?, которая намного дороже, так как она рекурсивно сравнивает состав. Вышеприведенная реализация на самом деле достаточно дешева, чтобы ее можно было часто использовать для моделирования ассоциативных массивов и сред в интерпретаторах, даже если это, конечно, не произвольный доступ.

Редактировать: Как вы просили, в потоках:

Стандарт Scheme поддерживает красивую пару, одна из них - функция с именем force, другая - специальная форма , называемая delay. Эффективно, что

(delay (+ 1 2 3))

Или любой другой код вместо (+ 1 2 3) возвратов является так называемым «обещанием», оно задерживает вычисление ответа в этом обещании, но обещает, что результат будет идентичен при оценке с 6 попасть. Это может показаться совершенно бесполезным, но, скажем, результат зависит от некоторой переменной, которую можно изменить:

(define x 4) ; x is bound to 4.
(let ((promise (delay (+ 2 x)))) ; evaluating the expression now would result into 6, but we delay it.
  (set! x 5) ; we change the value of x.
  (display (force promise)) ; displays 7
  (set! x 6) ; change it again
  (force promise) ; ALSO displays 7, not 8
)

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

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

(define (stream-cdr x) (force (cdr x))) ; it forces that promise to evaluate it.
; and optionally
(define stream-car car) ; same

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

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons x y)
     (cons x (delay y))))

Ваш компилятор или интерпретатор Scheme теперь будет переводить каждый раз от (stream-cons x y) до (cons x (delay y)) для любых произвольных x и y.

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

(define zero-stream (stream-cons 0 zero-streams))

Список ограничился сам по себе, который, безусловно, никогда не закончился бы, если бы мы не использовали поток, бесполезный, но он показывает идею. Мы можем просто использовать stream-cdr снова и снова, даже не достигая пустого списка, мы просто возвращаем тот же «бесконечный список из 0».

Более практичным примером будет список всех чисел Фибоначчи, который несколько сложнее:

(define fibs 
  (stream-cons 0 (stream-cons 1
    (stream-map + fibs (stream-cdr fibs))))

Stream-map - это аналог карты нормалей, ее определение довольно сложное, но я уверен, что вы можете посмотреть его, оно генерирует сам поток. Таким образом, `(stream-map (lambda (x y) (+ 1 x y)) обнуляет нули) генерирует поток, полностью заполненный единицей. Поток fibs рекурсивно определен сам по себе. Первые два элемента даны, а остальные вычисляются из двух потоков, которые просто являются fib-файлами и stream-cdr самого fib-файла.