История изменений
Исправление Nervous, (текущая версия) :
условные cons, first и rest для абстрактного списка
Разные структуры данных обычно создаются потому, что у них разная масштабируемость операций. Например, по вектору можно пройтись в обратном направлении, а по односвязанному списку — нет.
На самом деле можно, просто это будет неэффективно. Вектор тут подходит лучше. Почему он подходит лучше? Потому что позволяет определение количества элементов и доступ по индексу элемента за постоянное время.
Поэтому может иметь смысл реализовать условный fold-right не в терминах абстрактного списка (последовательности), а в терминах абстрактной структуры данных с произвольным доступом по индексу элемента. И тогда fold-right будет автоматически работать с любым объектом, который такой интерфейс реализует. Строки, массивы, векторы, что угодно (но не односвязные списки).
И всё, что построено на fold-right, тоже будет работать со всеми этими объектами без дополнительных телодвижений. И с любыми новыми объектами — если они реализуют интерфейс нужного абстрактного типа данных.
Исправление Nervous, :
условные cons, first и rest для абстрактного списка
Разные структуры данных обычно создаются потому, что у них разная масштабируемость операций. Например, по вектору можно пройтись в обратном направлении, а по односвязанному списку — нет.
На самом деле можно, просто это будет неэффективно. Вектор тут подходит лучше. Почему он подходит лучше? Потому что позволяет определение количества элементов и доступ по индексу элемента за постоянное время.
Поэтому может иметь смысл реализовать условный fold-right не в терминах абстрактного списка (последовательности), а в терминах абстрактной структуры данных с произвольным доступом по индексу элемента. И тогда fold-right будет автоматически работать с любым объектом, который такой интерфейс реализует. Строки, массивы, векторы, что угодно.
И всё, что построено на fold-right, тоже будет работать со всеми этими объектами без дополнительных телодвижений. И с любыми новыми объектами — если они реализуют интерфейс нужного абстрактного типа данных.
Исправление Nervous, :
условные cons, first и rest для абстрактного списка
Разные структуры данных обычно создаются потому, что у них разная масштабируемость операций. Например, по вектору можно пройтись в обратном направлении, а по односвязанному списку — нет.
На самом деле можно, просто это будет неэффективно. Вектор тут подходит лучше. Почему он подходит лучше? Потому что позволяет доступ по индексу элемента за постоянное время.
Поэтому может иметь смысл реализовать условный fold-right не в терминах абстрактного списка (последовательности), а в терминах абстрактной структуры данных с произвольным доступом по индексу элемента. И тогда fold-right будет автоматически работать с любым объектом, который такой интерфейс реализует. Строки, массивы, векторы, что угодно.
И всё, что построено на fold-right, тоже будет работать со всеми этими объектами без дополнительных телодвижений. И с любыми новыми объектами — если они реализуют интерфейс нужного абстрактного типа данных.
Исходная версия Nervous, :
условные cons, first и rest для абстрактного списка
Разные структуры данных обычно создаются потому, что у них разная масштабируемость операций. Например, по вектору можно пройтись в обратном направлении, а по односвязанному списку — нет.
На самом деле можно, просто это будет неэффективно. Вектор тут подходит лучше. Почему он подходит лучше? Потому что позволяет доступ по индексу элемента за постоянное время.
Поэтому может иметь смысл реализовать условный fold-right не в терминах абстрактного списка (последовательности), а в терминах абстрактной структуры данных с произвольным доступом по индексу элемента. И тогда fold-right будет автоматически работать с любым объектом, который такой интерфейс реализует. Строки, массивы, векторы, что угодно.