Справочная информация : я пишу небольшого переводчика в Scheme (R5RS).
Считыватель / лексер берет (иногда длинную) строку из ввода и маркирует ее. Он делает это путем сопоставления первых нескольких символов строки с некоторым токеном и возврата токена и оставшейся непревзойденной части строки.
Проблема : чтобы вернуть оставшуюся часть строки, новая строка создается каждый раз, когда читается токен. Это означает, что читатель равен O (n ^ 2) по количеству токенов в строке.
Возможное решение : преобразовать строку в список, что можно сделать за время O (n), затем вытянуть токены из списка вместо строки, возвращая остаток списка вместо остаток строки. Но это кажется ужасно неэффективным и искусственным.
Вопрос : я представляю себе это или просто нет другого способа сделать это эффективно в Схеме из-за его чисто функциональной перспективы?
Редактировать: в схеме R5RS нет способа вернуть указатель на строку. Функция "substring" является единственной функцией, которая извлекает объект, который сам является строкой. Но стандарт Scheme настаивает на том, чтобы это была вновь выделенная строка. Зачем? Потому что строки не являются неизменными в схеме R5RS, например, увидеть "набор строк!" функция !!
Одним из предложенных ниже решений, которое работает, является сохранение индекса в строку. Затем можно прочитать символы по одному из этого индекса, пока токен не будет прочитан. Жаль, что библиотека регулярных выражений, которую я использую для токенизации, требует фактической строки, а не индекса в одну ...