SICP. Абстракция данных. Обыкновенные дроби

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

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

Обыкновенные дроби

На листочке выглядит достаточно просто: \(\frac{5}{9}\). Но компьютеру нельзя просто сказать: «поставь палку между двумя числами и думай, что это дробь.» Надо писать абстракции для дробей и вообще не целых чисел.

Целое число — простейший элемент абстракции.

Библиотека дробей

Как мы сказали выше, дробь это пара чисел и палка деления между ними. Тип данных «пара» мы уже делали в прошлой статье, его и возьмём.

Тут будут использоваться селекторы и конструктор, сейчас объясним:
Селекторы — функции-манипуляторы, они достают по одному значению из пары
Конструктор — функция-упаковщик с замыканием, чтобы хранить значения пары

В функции cons есть ещё функция make_pair для замыкания данных между двумя областями видимости. Так данные принимают абстрактный вид и на месте пары «числитель-знаменатель» может быть две строки. Про замыкания у нас есть статья из курса по Пайтону.

a = cons(4, 5)  # В а лежит функция, она замкнула числитель 4 и знаменатель 5

print(car(a))  # Выводится числитель – 4
print(cdr(a))  # Выводится знаменатель – 5

Этот файл нужен чтобы разделить реализацию абстракции данных от её использования. То есть в pair.py ничего не изменяется и не проверяется, просто данные.

Пишем операции

Теперь сделаем ещё файл, он будет для операций и вывода.
Чисто теоретически-технически, мы можем использовать pair.py для склеивания строк и даже других пар, потому что абстракция.

В каждой операции числители и знаменатели отделены друг от друга, потому что для компьютера это всё равно два отдельно взятых целых числа. Когда всё сделано, из новых значений опять собирается дробь через make_rational.

Красиво дошлифуем

Всё работает, но дроби не сокращаются. Нужно написать ещё функцию для поиска общего знаменателя и сокращения на него. Евклид уже всё придумал, поэтому мы заворачиваем алгоритм в отдельную функцию.
Добавляем сокращение дробей в конструктор, «//» — деление без остатка

Поделиться
Отправить
 34   2 мес   sicp
Популярное