scalabook
Глава 2
Глава 2. Построение абстракций с помощью данных
В этой главе мы обращаемся к другой важной характеристике всякого языка программирования: тем средствам, которые он предоставляет для создания абстракций с помощью сочетания объектов данных и построения составных данных (compound data).
Составной объект данных (compound data object) – это структура данных, которая состоит из нескольких элементов данных различных типов. Эти элементы могут быть как простыми (например, числа, строки), так и сложными (например, массивы, другие составные объекты).
Общий метод отделения частей программы, которые имеют дело с представлением объектов данных, от тех частей, где эти объекты данных используются, — это мощная методология проектирования, называемая абстракция данных (data abstraction).
Абстракция является методом ограничения сложности. Абстракция данных позволяет возводить полезные барьеры абстракции (abstraction barriers) между разными частями программы.
Важная идея в работе с составными данными — понятие замыкания (closure): клей для сочетания объектов данных должен позволять склеивать не только элементарные объекты данных, но и составные. Еще одна важная идея состоит в том, что составные объекты данных могут служить стандартными интерфейсами (conventional interfaces), так, чтобы модули программы могли сочетаться методом подстановки.
Символьные выражения (symbolic expressions) — данные, элементарные части которых могут быть произвольными символами, а не только числами.
Обобщенные операции (generic operations) обрабатывают много различных типов данных. Поддержка модульности в присутствии обобщенных операций требует более мощных барьеров абстракции, чем тех, что получаются с помощью простой абстракции данных. А именно, мы вводим программирование, управляемое данными (data-directed programming) как метод, который позволяет проектировать представления данных отдельно, а затем сочетать их аддитивно (additively) (т.е., без модификации).
2.1. Введение в абстракцию данных
Абстракция данных (data abstraction) — это методология, которая позволяет отделить способ использования составного объекта данных от деталей того, как он составлен из элементарных данных.
Основная идея абстракции данных состоит в том, чтобы строить программы, работающие с составными данными, так, чтобы иметь дело с «абстрактными данными». То есть, используя данные, наши программы не должны делать о них никаких предположений, кроме абсолютно необходимых для выполнения поставленной задачи. В то же время «конкретное» представление данных определяется независимо от программ, которые эти данные используют. Интерфейсом между двумя этими частями системы служит набор процедур, называемых селекторами (selectors) и конструкторами (constructors), реализующих абстрактные данные в терминах конкретного представления.
2.1.1. Пример: арифметические операции над рациональными числами
Пары
Для реализации конкретного уровня абстракции данных в нашем языке имеется составная структура, называемая кортеж (tuple). Объекты данных, составленные из кортежей, называются данные со списковой структурой (list-structured data).
opaque type Pair = (Long, Long)val cons: Pair = (-5, 7)// cons: Tuple2[Long, Long] = (-5L, 7L)val car = cons._1// car: Long = -5Lval cdr = cons._2// cdr: Long = 7LПредставление рациональных чисел
Представление рациональных чисел в виде case class-а:
final case class Rational private (numer: Long, denom: Long): import Rational.makeRat
lazy val print: String = s"$numer/$denom"
def +(that: Rational): Rational = makeRat(numer * that.denom + that.numer * denom, denom * that.denom)
def -(that: Rational): Rational = makeRat(numer * that.denom - that.numer * denom, denom * that.denom)
def *(that: Rational): Rational = makeRat(numer * that.numer, denom * that.denom)
def /(that: Rational): Rational = makeRat(numer * that.denom, denom * that.numer)
def ===(that: Rational): Boolean = numer * that.denom == denom * that.numer
object Rational: def makeRat(numer: Long, denom: Long): Rational = Rational(numer, denom)
Rational.makeRat(-5, 7).print// res0: String = "-5/7"Rational.makeRat(-5, 7) + Rational.makeRat(3, 7)// res1: Rational = Rational(numer = -14L, denom = 49L)Rational.makeRat(-5, 7) - Rational.makeRat(3, 7)// res2: Rational = Rational(numer = -56L, denom = 49L)Rational.makeRat(-5, 7) * Rational.makeRat(3, 7)// res3: Rational = Rational(numer = -15L, denom = 49L)Rational.makeRat(-5, 7) / Rational.makeRat(3, 7)// res4: Rational = Rational(numer = -35L, denom = 21L)Rational.makeRat(-5, 7) === Rational.makeRat(-10, 14)// res5: Boolean = trueУпражнение 2.1
Определите улучшенную версию mul-rat, которая принимала бы как положительные, так и отрицательные аргументы. Make-rat должна нормализовывать знак так, чтобы в случае, если рациональное число положительно, то и его числитель, и знаменатель были бы положительны, а если оно отрицательно, то чтобы только его числитель был отрицателен.
object Rational: def makeRat(numer: Long, denom: Long): Rational = val g = gcd(numer, denom) val sign = if denom < 0 then -1 else 1 Rational(sign * numer / g, sign * denom / g)Rational.makeRat(14, 49).print// res7: String = "2/7"Rational.makeRat(1, 2).print// res8: String = "1/2"Rational.makeRat(-1, -2).print// res9: String = "1/2"Rational.makeRat(-1, 2).print// res10: String = "-1/2"Rational.makeRat(1, -2).print// res11: String = "-1/2"2.1.2. Барьеры абстракции
Упражнение 2.2
Рассмотрим задачу представления отрезков прямой на плоскости. Каждый отрезок представляется как пара точек: начало и конец. Определите конструктор make-segment и селекторы startsegment и end-segment, которые определяют представление отрезков в терминах точек. Далее, точку можно представить как пару чисел: координата x и координата y. Соответственно, напишите конструктор make-point и селекторы x-point и y-point, которые определяют такое представление. Наконец, используя свои селекторы и конструктор, напишите процедуру midpointsegment, которая принимает отрезок в качестве аргумента и возвращает его середину (точку, координаты которой являются средним координат концов отрезка). Чтобы опробовать эти процедуры, Вам потребуется способ печатать координаты точек
final case class Point(x: Double, y: Double): override def toString(): String = s"($x,$y)"
final case class Segment(start: Point, end: Point): lazy val midpoint: Point = Point((start.x + end.x) / 2, (start.y + end.y) / 2)
Segment(Point(1, 0), Point(0, 1)).midpoint.toString// res12: String = "(0.5,0.5)"Упражнение 2.3
Реализуйте представление прямоугольников на плоскости. (Подсказка: Вам могут потребоваться результаты упражнения 2.2.) Определите в терминах своих конструкторов и селекторов процедуры, которые вычисляют периметр и площадь прямоугольника. Теперь реализуйте другое представление для прямоугольников. Можете ли Вы спроектировать свою систему с подходящими барьерами абстракции так, чтобы одни и те же процедуры вычисления периметра и площади работали с любым из Ваших представлений?
final case class Point(x: Double, y: Double): override def toString(): String = s"($x,$y)"
final case class Segment(start: Point, end: Point): lazy val midpoint: Point = Point((start.x + end.x) / 2, (start.y + end.y) / 2) lazy val length: Double = math.sqrt(math.pow(start.x - end.x, 2.0) + math.pow(start.y - end.y, 2.0))
final case class Rectangle( topLeft: Point, topRight: Point, bottomRight: Point, bottomLeft: Point): private lazy val topSideLength: Double = Segment(topLeft, topRight).length private lazy val leftSideLength: Double = Segment(topLeft, bottomLeft).length
lazy val perimeter: Double = 2 * (topSideLength + leftSideLength) lazy val square: Double = topSideLength * leftSideLength
object Rectangle: def apply(segment1: Segment, segment2: Segment): Rectangle = Rectangle(segment1.start, segment1.end, segment2.start, segment2.end)
val rect = Rectangle(Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1))rect.perimeter// res14: Double = 4.0rect.square// res15: Double = 1.02.1.3. Что значит слово «данные»?
Данные — это то, что определяется некоторым набором селекторов и конструкторов, а также некоторыми условиями, которым эти процедуры должны удовлетворять, чтобы быть правильным представлением.
Пару можно реализовать, используя только одни процедуры:
def cons[A, B](a: A, b: B): Boolean => A | B = def dispatch(m: Boolean): A | B = if m then a else b
dispatch
def car[A, B](a: A, b: B): A | B = cons(a, b)(true)
def cdr[A, B](a: A, b: B): A | B = cons(a, b)(false)Упражнение 2.4
Вот еще одно процедурное представление для пар. Проверьте для этого представления, что при любых двух объектах x и y (car (cons x y)) возвращает x
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p)))Каково соответствующее определение cdr? (Подсказка: Чтобы проверить, что это работает, используйте подстановочную модель из раздела 1.1.5.)
final case class Cons[A](x: A, y: A): def lambda(f: (A, A) => A): A = f(x, y)
def car[A](z: Cons[A]): A = z.lambda((p: A, q: A) => p)
def cdr[A](z: Cons[A]): A = z.lambda((p: A, q: A) => q)Рассмотрим цепочку преобразований:
(car (cons x y))(cons x y).lambda((p: A, q: A) => p)((p: A, q: A) => p)(x, y)x
Аналогично для cdr.
Упражнение 2.5
Покажите, что можно представлять пары неотрицательных целых чисел, используя только числа и арифметические операции, если представлять пару a и b как произведение \(2^{a}*3^{b}\). Дайте соответствующие определения процедур cons, car и cdr.
final case class Cons(x: Int, y: Int): lazy val cons: Int = math.pow(2, x).toInt * math.pow(3, y).toInt
def degreeOfFactor(a: Int): Int = def loop(n: Int, count: Int): Int = if n % a == 0 then loop(n / a, count + 1) else count loop(cons, 0)
def car(z: Cons): Int = z.degreeOfFactor(2)
def cdr(z: Cons): Int = z.degreeOfFactor(3)Упражнение 2.6
Если представление пар как процедур было для Вас еще недостаточно сумасшедшим, то заметьте, что в языке, который способен манипулировать процедурами, мы можем обойтись и без чисел (по крайней мере, пока речь идет о неотрицательных числах), определив 0 и операцию прибавления 1 так:
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))Такое представление известно как числа Чёрча (Church numerals), по имени его изобретателя, Алонсо Чёрча, того самого логика, который придумал λ-исчисление. Определите one (единицу) и two (двойку) напрямую (не через zero и add-1). (Подсказка: вычислите (add-1 zero) с помощью подстановки.) Дайте прямое определение процедуры сложения + (не в терминах повторяющегося применения add-1).
Число Чёрча можно определить как n-кратное применение заданной функции к аргументу.
Например, вот так:
def zero[A](f: A => A): A => A = x => x
def add1[A](f: A => A, n: Int): A => A = if n == 0 then zero(f) else (a: A) => add1(f, n - 1)(a)Тогда единица - это однократное применение функции, двойка - двукратное, а сложение a и b -
это применение функции f к аргументу a + b раз.
2.1.4. Расширенный пример: интервальная арифметика
Упражнение 2.7
Программа Лизы неполна, поскольку она не определила, как реализуется абстракция интервала. Вот определение конструктора интервала:
(define (make-interval a b) (cons a b))Завершите реализацию, определив селекторы upper-bound и lower-bound.
final case class Interval(a: Double, b: Double): lazy val upperBound: Double = math.max(a, b) lazy val lowerBound: Double = math.min(a, b)
def add(that: Interval): Interval = Interval( this.lowerBound + that.lowerBound, this.upperBound + that.upperBound )
def mul(that: Interval): Interval = val p1 = this.lowerBound * that.lowerBound val p2 = this.lowerBound * that.upperBound val p3 = this.upperBound * that.lowerBound val p4 = this.upperBound * that.upperBound Interval( math.min(math.min(p1, p2), math.min(p3, p4)), math.max(math.max(p1, p2), math.max(p3, p4)) )
def div(that: Interval): Interval = mul(Interval(1.0 / that.upperBound, 1.0 / that.lowerBound))Упражнение 2.8
Рассуждая в духе Лизы, опишите, как можно вычислить разность двух интервалов. Напишите соответствующую процедуру вычитания, называемую sub-interval.
def sub(that: Interval): Interval = Interval( this.lowerBound - that.upperBound, this.upperBound - that.lowerBound )Упражнение 2.9
Радиус (width) интервала определяется как половина расстояния между его верхней и нижней границами. Радиус является мерой неопределенности числа, которое обозначает интервал. Есть такие математические операции, для которых радиус результата зависит только от радиусов интервалов-аргументов, а есть такие, для которых радиус результата не является функцией радиусов аргументов. Покажите, что радиус суммы (или разности) двух интервалов зависит только от радиусов интервалов, которые складываются (или вычитаются). Приведите примеры, которые показывают, что для умножения или деления это не так.
lazy val width: Double = (upperBound - lowerBound) / 2.0Радиус суммы интервалов будет вычисляться так:
((this.upperBound + that.upperBound) - (this.lowerBound + that.lowerBound)) / 2.0((this.upperBound - this.lowerBound) / 2.0 + (that.upperBound - that.lowerBound) / 2.0)this.width + that.width
Радиус разности интервалов будет вычисляться так:
((this.upperBound - that.lowerBound) - (this.lowerBound - that.upperBound)) / 2.0((this.upperBound - this.lowerBound) / 2.0 + (that.upperBound - that.lowerBound) / 2.0)this.width + that.width
С умножением и делением ситуация иная: если взять два интервала радиуса 1: (0, 2) и (2, 4),
то произведением интервалов будет интервал (0, 8) с радиусом 4,
а результат деления - интервал (0, 1) с радиусом 0.5.
Упражнение 2.10
Бен Битобор, системный программист-эксперт, смотрит через плечо Лизы и замечает: неясно, что должно означать деление на интервал, пересекающий ноль. Модифицируйте код Лизы так, чтобы программа проверяла это условие и сообщала об ошибке, если оно возникает.
def div(that: Interval): Option[Interval] = if that.lowerBound <= 0.0 && that.upperBound >= 0.0 then None else Some(mul(Interval(1.0 / that.upperBound, 1.0 / that.lowerBound)))Упражнение 2.11
Проходя мимо, Бен делает туманное замечание: «Если проверять знаки концов интервалов, можно разбить mul-interval на девять случаев, из которых только в одном требуется более двух умножений». Перепишите эту процедуру в соответствии с предложением Бена.
def mul(that: Interval): Interval = ( this.lowerBound < 0, this.upperBound < 0, that.lowerBound < 0, that.upperBound < 0 ) match case (true, true, true, true) => Interval( this.upperBound * that.upperBound, this.lowerBound * that.lowerBound ) case (true, true, true, false) => Interval( this.lowerBound * that.upperBound, this.lowerBound * that.lowerBound ) case (true, true, false, false) => Interval( this.lowerBound * that.upperBound, this.upperBound * that.lowerBound ) case (true, false, true, true) => Interval( this.upperBound * that.lowerBound, this.lowerBound * that.lowerBound ) case (true, false, true, false) => val p1 = this.lowerBound * that.lowerBound val p2 = this.lowerBound * that.upperBound val p3 = this.upperBound * that.lowerBound val p4 = this.upperBound * that.upperBound Interval( math.min(p2, p3), math.max(p1, p4) ) case (true, false, false, false) => Interval( this.lowerBound * that.upperBound, this.upperBound * that.upperBound ) case (false, false, true, true) => Interval( this.upperBound * that.lowerBound, this.lowerBound * that.upperBound ) case (false, false, true, false) => Interval( this.upperBound * that.lowerBound, this.upperBound * that.upperBound ) case (false, false, false, false) => Interval( this.lowerBound * that.lowerBound, this.upperBound * that.upperBound )Упражнение 2.12
Определите конструктор make-center-percent, который принимает среднее значение и погрешность в процентах и выдает требуемый интервал. Нужно также определить селектор percent, который для данного интервала выдает погрешность в процентах. Селектор center остается тем же, что приведен выше.
final case class Interval(a: Double, b: Double): lazy val upperBound: Double = math.max(a, b) lazy val lowerBound: Double = math.min(a, b) lazy val center: Double = (upperBound + lowerBound) / 2.0 lazy val width: Double = (upperBound - lowerBound) / 2.0 lazy val percent: Double = (width / center) * 100
// ...
object Interval: def makeCenterWidth(center: Double, width: Double): Interval = Interval(center - width, center + width)
def makeCenterPercent(center: Double, percent: Double): Interval = val width: Double = percent * center / 100.0 makeCenterWidth(center, width)Упражнение 2.13
Покажите, что, если предположить, что погрешность составляет малую долю величины интервала, то погрешность в процентах произведения двух интервалов можно получить из погрешности в процентах исходных интервалов по простой приближенной формуле. Задачу можно упростить, если предположить, что все числа положительные.
Рассмотрим произведение двух интервалов с маленькой погрешностью:
Interval(c1 - w1, c1 + w1) * Interval(c2 - w2, c2 + w2)Interval((c1 - w1) * (c2 - w2), (c1 + w1) * (c2 + w2))mulCenter = ((c1 * c2 + w1 * c2 + w2 * c1 + w1 * w2) + (c1 * c2 - w1 * c2 - w2 * c1 + w1 * w2)) / 2mulCenter = (c1 * c2 + w1 * w2)- т.к. погрешность малая величина, то слагаемым
w1 * w2можно пренебречь mulWidth = ((c1 * c2 + w1 * c2 + w2 * c1 + w1 * w2) - (c1 * c2 - w1 * c2 - w2 * c1 + w1 * w2)) / 2mulWidth = (w1 * c2 + w2 * c1)mulPercent = ((w1 * c2 + w2 * c1) / (c1 * c2)) * 100 = (w1 / c1) * 100 + (w2 / c2) * 100- таким образом погрешность произведения приближенно равна сумме погрешностей множителей
Упражнение 2.14
Покажите, что Дайко прав. Исследуйте поведение системы на различных арифметических выражениях. Создайте несколько интервалов A и B и вычислите с их помощью выражения A/A и A/B. Наибольшую пользу Вы получите, если будете использовать интервалы, радиус которых составляет малую часть от среднего значения. Исследуйте результаты вычислений в форме центр/проценты (см. упражнение 2.12).
def par1(r1: Interval, r2: Interval): Option[Interval] = (r1.mul(r2)).div(r1.add(r2))
def par2(r1: Interval, r2: Interval): Option[Interval] = for one <- Interval(1, 2).div(Interval(1, 2)) oneDivR1 <- one.div(r1) oneDivR2 <- one.div(r2) result <- one.div(oneDivR1.add(oneDivR2)) yield result
val r1 = Interval.makeCenterWidth(10, 0.01)// r1: Interval = Interval(a = 9.99, b = 10.01)val r2 = Interval.makeCenterWidth(20, 0.01)// r2: Interval = Interval(a = 19.99, b = 20.01)par1(r1, r2)// res17: Option[Interval] = Some(// value = Interval(a = 6.652235176548966, b = 6.681124082721815)// )par2(r1, r2)// res18: Option[Interval] = Some(// value = Interval(a = 1.6652776851234157, b = 26.6888874083944)// )Методы действительно отдают различные результаты, потому что деление интервала на себя (A/A) - это не единица, а интервал, имеющий небольшую погрешность.
2.2. Иерархические данные и свойство замыкания
Представление (cons 1 2) в виде стрелочной диаграммы:
flowchart LR A["..."] --> cons subgraph cons B1["#8901;"] B2["#8901;"] end B1 --> 1 B2 --> 2В этом представлении, которое называется стрелочная диаграмма (box-and-pointer notation), каждый объект изображается в виде стрелки (pointer), указывающей на какую-нибудь ячейку. Ячейка, изображающая элементарный объект, содержит представление этого объекта. Например, ячейка, соответствующая числу, содержит числовую константу. Изображение пары состоит из двух ячеек, причем верхняя из них содержит (указатель на) car этой пары, а нижняя — ее cdr.
На диаграмме ниже показаны два способа соединить числа 1, 2, 3 и 4 при помощи пар:
((1, 2), (3, 4))(1, (2, (3, 4)))
flowchart LR A["..."] --> cons1 subgraph cons1 B1["#8901;"] B2["#8901;"] end B1 --> cons2 B2 --> cons3 subgraph cons2 B3["#8901;"] B4["#8901;"] end B3 --> P1[1] B4 --> P2[2] subgraph cons3 B5["#8901;"] B6["#8901;"] end B5 --> P3[3] B6 --> P4[4]
P1 ~~~ B
B["..."] --> cons4 subgraph cons4 С1["#8901;"] С2["#8901;"] end С1 ---> cons5 С2 --> Q1[1] subgraph cons5 С3["#8901;"] С4["#8901;"] end С3 --> Q2[2] С4 ---> cons6 subgraph cons6 С5["#8901;"] С6["#8901;"] end С5 --> Q3[3] С6 --> Q4[4]Возможность создавать пары, элементы которых сами являются парами, определяет значимость списковой структуры как средства представления данных. Мы называем эту возможность свойством замыкания (closure property) для cons. В общем случае, операция комбинирования объектов данных обладает свойством замыкания в том случае, если результаты соединения объектов с помощью этой операции сами могут соединяться этой же операцией. Замыкание — это ключ к выразительной силе для любого средства комбинирования, поскольку оно позволяет строить иерархические (hierarchical) структуры, то есть структуры, составленные из частей, которые сами составлены из частей, и так далее.
2.2.1. Представление последовательностей
Одна из полезных структур, которые можно построить с помощью пар — это последовательность (sequence), то есть упорядоченная совокупность объектов данных.
Cons(1, Cons(2, Cons(3, Cons(4, Nil)))) - такая последовательность пар,
порождаемая вложенными cons-ами, называется список (list).
Или более кратко - 1 :: 2 :: 3 :: 4 :: Nil.
Значение Nil, которым завершается цепочка пар, можно рассматривать как последовательность без элементов,
пустой список (empty list).
Слово nil произошло от стяжения латинского nihil, что значит «ничто».
Операции со списками
Процедура list-ref берет в качестве аргументов список и число n и возвращает n-й элемент списка.
Обычно элементы списка нумеруют, начиная с 0. Метод вычисления list-ref следующий:
- Если n = 0,
list-refдолжна вернуть car списка. - В остальных случаях
list-refдолжна вернуть (n − 1)-й элемент от cdr списка.
def listRef[A](items: List[A], n: Int): Option[A] = if n <= 0 then items.headOption else items match case Nil => None case head :: tail => listRef(tail, n - 1)
listRef(List(1, 4, 9, 16, 25), 3)// Some(16)Процедура length, которая возвращает число элементов в списке:
def length[A](items: List[A]): Int = items match case Nil => 0 case _ :: tail => 1 + length(tail)
length(List(1, 3, 5, 7))// 4Процедура length реализует простую рекурсивную схему. Шаг редукции таков:
- Длина любого списка равняется 1 плюс длина cdr этого списка
Этот шаг последовательно применяется, пока мы не достигнем базового случая:
- Длина пустого списка равна
0.
Мы можем вычислить length и в итеративном стиле:
def length[A](items: List[A]): Int = @tailrec def loop(items: List[A], l: Int): Int = items match case Nil => l case _ :: tail => loop(tail, l + 1)
loop(items, 0)
length(List(1, 3, 5, 7))// 4Append также реализуется по рекурсивной схеме.
Чтобы соединить списки list1 и list2, нужно сделать следующее:
- Если список
list1пуст, то результатом является простоlist2. - В противном случае, нужно соединить
cdrотlist1сlist2, а к результату прибавитьcarотlist1с помощьюcons:
def append[A](list1: List[A], list2: List[A]): List[A] = list1 match case Nil => list2 case head :: tail => head :: append(tail, list2)
append(List(1, 4, 9, 16, 25), List(1, 3, 5, 7))// List(1, 4, 9, 16, 25, 1, 3, 5, 7)Упражнение 2.17
Определите процедуру
last-pair, которая возвращает список, содержащий только последний элемент данного (непустого) списка. (last-pair (list 23 72 149 34)) (34)
def lastPair[A](list: List[A]): List[A] = list match case Nil => Nil case h :: Nil => List(h) case _ :: t => lastPair(t)
lastPair(List(23, 72, 149, 34)) // List(34)Упражнение 2.18
Определите процедуру
reverse, которая принимает список как аргумент и возвращает список, состоящий из тех же элементов в обратном порядке: (reverse (list 1 4 9 16 25)) (25 16 9 4 1)
def reverse[A](list: List[A]): List[A] = list match case Nil => Nil case h :: t => t.reverse :+ h
reverse(List(1, 4, 9, 16, 25)) // List(25, 16, 9, 4, 1)Упражнение 2.19
Рассмотрим программу подсчета способов размена из раздела 1.2.2. Было бы приятно иметь возможность легко изменять валюту, которую эта программа использует, так, чтобы можно было, например, вычислить, сколькими способами можно разменять британский фунт. Эта программа написана так, что знание о валюте распределено между процедурами
first-denominationиcount-change(которая знает, что существует пять видов американских монет). Приятнее было бы иметь возможность просто задавать список монет, которые можно использовать при размене.Мы хотим переписать процедуру
ccтак, чтобы ее вторым аргументом был список монет, а не целое число, которое указывает, какие монеты использовать. Тогда у нас могли бы быть списки, определяющие типы валют:
val usCoins = List(50, 25, 10, 5, 1)
val ukCoins = List(100, 50, 20, 10, 5, 2, 1, 0.5)Можно было бы вызывать
ccследующим образом:
cc(100.0, usCoins) // 292Это потребует некоторых изменений в программе
cc. Ее форма останется прежней, но со вторым аргументом она будет работать иначе, вот так:Определите процедуры
firstDenomination,exceptFirstDenominationиnoMoreв терминах элементарных операций над списковыми структурами. Влияет ли порядок спискаcoinValuesна результат, получаемыйcc? Почему?
def noMore(coinValues: List[Double]): Boolean = coinValues match case Nil => true case _ => false
def exceptFirstDenomination(coinValues: List[Double]): List[Double] = coinValues match case Nil => Nil case _ :: t => t
def firstDenomination(coinValues: List[Double]): Double = coinValues match case Nil => 0.0 case h :: _ => hПорядок списка coinValues на результат не влияет, потому что вне зависимости от того, какая монета идет первой,
все варианты можно разделить на две категории: сумма использует первую монету или не использует.
Упражнение 2.20
Процедуры
+,*иlistпринимают произвольное число аргументов. Один из способов определения таких процедур состоит в использовании точечной записи (dotted-tail notation). В определении процедуры список параметров с точкой перед именем последнего члена означает, что, когда процедура вызывается, начальные параметры (если они есть) будут иметь в качестве значений начальные аргументы, как и обычно, но значением последнего параметра будет список всех оставшихся аргументов. Например, если дано определение
(define (f x y . z) <тело>)то процедуру
fможно вызывать с двумя и более аргументами. Если мы вычисляем
(f 1 2 3 4 5 6)то в теле
fпеременнаяxбудет равна1,yбудет равно2, аzбудет списком(3 4 5 6). Если дано определение
(define (g . w) <тело>)то процедура
gможет вызываться с нулем и более аргументов. Если мы вычислим
(g 1 2 3 4 5 6)то в теле
gзначением переменнойwбудет список(1 2 3 4 5 6).Используя эту нотацию, напишите процедуру
same-parity, которая принимает одно или более целое число и возвращает список всех тех аргументов, у которых четность та же, что у первого аргумента. Например,
(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
(same-parity 2 3 4 5 6 7)
(2 4 6)
import scala.annotation.tailrec
def sameParity(first: Int, others: Int*): List[Int] = @tailrec def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match case Nil => acc case head :: tail if head % 2 == first % 2 => loop(tail, head :: acc) case _ :: tail => loop(tail, acc)
loop(others.toList, List(first))
sameParity(1, 2, 3, 4, 5, 6, 7)// List(7, 5, 3, 1)sameParity(2, 3, 4, 5, 6, 7)// List(6, 4, 2)Отображение списков
Крайне полезной операцией является применение какого-либо преобразования к каждому элементу списка и порождение списка результатов. Например, следующая процедура умножает каждый элемент списка на заданное число.
def scaleList(items: List[Int], factor: Int): List[Int] = items match case Nil => Nil case h :: t => (h * factor) :: scaleList(t, factor)
scaleList(List(1, 2, 3, 4, 5), 10)// List(10, 20, 30, 40, 50)Мы можем выделить здесь общую идею и зафиксировать ее как схему,
выраженную в виде процедуры высшего порядка, в точности как в разделе 1.3.
Здесь эта процедура высшего порядка называется map.
Map берет в качестве аргументов процедуру от одного аргумента и список,
а возвращает список результатов, полученных применением процедуры к каждому элементу списка:
def map[A, B](items: List[A], proc: A => B): List[B] = items match case Nil => Nil case h :: t => proc(h) :: map(t, proc)
map(List(-10, 2.5, -11.6, 17), math.abs)// List(10.0, 2.5, 11.6, 17.0)map(List(1, 2, 3, 4), x => x * x)// List(1, 4, 9, 16)Теперь мы можем дать новое определение scale-list через map:
def scaleList(items: List[Int], factor: Int): List[Int] = map(items, _ * factor)Упражнение 2.21
Процедура square-list принимает в качестве аргумента список чисел и возвращает список квадратов этих чисел.
(square-list (list 1 2 3 4))
(1 4 9 16)Перед Вами два различных определения square-list. Закончите их, вставив пропущенные выражения:
(define (square-list items) (if (null? items) nil (cons <??> <??>))) (define (square-list items) (map h??i h??i))
def squareList(items: List[Int]): List[Int] = if items.isEmpty then Nil else val h = items.head (h * h) :: squareList(items.tail)
def squareList(items: List[Int]): List[Int] = map(items, x => x * x)Упражнение 2.22
Хьюго Дум пытается переписать первую из процедур square-list из упражнения 2.21 так, чтобы она работала как итеративный процесс:
(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons (square (car things)) answer)))) (iter items nil))К сожалению, такое определение square-list выдает список результатов в порядке, обратном желаемому. Почему?
Затем Хьюго пытается исправить ошибку, обменяв аргументы cons:
(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons answer (square (car things)))))) (iter items nil))И так программа тоже не работает. Объясните это.
В первом случае каждый следующий элемент списка после преобразования добавляется в начало ответа. В результате, после всех преобразований в начале итогового ответа будет преобразованный последний элемент исходного списка, а элементы будут идти в обратном порядке от исходного.
Во втором случае мы получаем не список элементов, а список от многих списков:
List(List(List(List(List(List(0), 1), 2), 3), 4), 5)
Упражнение 2.23
Процедура for-each похожа на map. В качестве аргументов она принимает процедуру и список элементов. Однако вместо того, чтобы формировать список результатов, for-each просто применяет процедуру по очереди ко всем элементам слева направо. Результаты применения процедуры к аргументам не используются вообще — for-each применяют к процедурам, которые осуществляют какое-либо действие вроде печати. Например,
(for-each (lambda (x) (newline) (display x)) (list 57 321 88)) 57 321 88Значение, возвращаемое вызовом for-each (оно в листинге не показано) может быть каким угодно, например истина. Напишите реализацию for-each.
def foreach[A](items: List[A], proc: A => Unit): Unit = items match case Nil => () case h :: t => proc(h) foreach(t, proc)
foreach(List(1, 2, 3), i => println(i))2.2.2. Иерархические структуры
Еще один способ думать о последовательностях последовательностей — деревья (trees). Элементы последовательности являются ветвями дерева, а элементы, которые сами по себе последовательности — поддеревьями.
Естественным инструментом для работы с деревьями является рекурсия, поскольку часто можно свести операции над деревьями к операциям над их ветвями, которые сами сводятся к операциям над ветвями ветвей, и так далее, пока мы не достигнем листьев дерева.
Например, подсчет листьев дерева:
enum Tree[+A]: self =>
case Leaf(value: A) case Branch(left: Tree[A], right: Tree[A])
lazy val countLeaves: Int = self match case Leaf(_) => 1 case Branch(left, right) => left.countLeaves + right.countLeaves
import Tree.*
val tree = Branch(Branch(Leaf(1), Leaf(2)), Branch(Leaf(3), Leaf(4)))tree.countLeaves // 4Упражнение 2.24
Предположим, мы вычисляем выражение (list 1 (list 2 (list 3 4))). Укажите, какой результат напечатает интерпретатор, изобразите его в виде стрелочной диаграммы, а также его интерпретацию в виде дерева (как на рисунке 2.6).
Стрелочная диаграмма:
flowchart TB one([1]) two([2]) three([3]) four([4]) p([.]) --> one p([.]) --> p1([.]) p1 --> two p1 --> p2([.]) p2 --> three p2 --> fourУпражнение 2.28
Напишите процедуру
fringe, которая берет в качестве аргумента дерево (представленное в виде списка) и возвращает список, элементы которого — все листья дерева, упорядоченные слева направо. Например,(define x (list (list 1 2) (list 3 4)))
(fringe x)
(1 2 3 4)
(fringe (list x x))
(1 2 3 4 1 2 3 4)
val tree = Branch(Branch(Leaf(1), Leaf(2)), Branch(Leaf(3), Leaf(4)))
def fringe[A](tree: Tree[A]): List[A] = tree match case Leaf(a) => List(a) case Branch(left, right) => fringe(left) ++ fringe(right)
fringe(tree) // List(1, 2, 3, 4)fringe(Branch(tree, tree))// List(1, 2, 3, 4, 1, 2, 3, 4)Отображение деревьев
Преобразование дерева реализуется аналогично преобразованию списка:
enum Tree[+A]: self =>
case Leaf(value: A) case Branch(left: Tree[A], right: Tree[A])
def map[B](f: A => B): Tree[B] = self match case Leaf(value) => Leaf(f(value)) case Branch(left, right) => Branch(left.map(f), right.map(f))Упражнение 2.30
Определите процедуру square-tree, подобную процедуре square-list из упражнения 2.21. А именно, square-tree должна вести себя следующим образом:
Определите square-tree как прямо (то есть без использования процедур высших порядков), так и с помощью
mapи рекурсии.
def squareTree(tree: Tree[Int]): Tree[Int] = tree match case Tree.Leaf(value) => Tree.Leaf(value * value) case Tree.Branch(left, right) => Tree.Branch(squareTree(left), squareTree(right))
def squareTree2(tree: Tree[Int]): Tree[Int] = tree.map(x => x * x)
val tree = Tree.Branch(Tree.Leaf(1), Tree.Branch(Tree.Leaf(2), Tree.Leaf(3)))squareTree2(tree)// Branch(Leaf(1),Branch(Leaf(4),Leaf(9)))Упражнение 2.31
Абстрагируйте свой ответ на упражнение 2.30, получая процедуру tree-map, так, чтобы square-tree можно было определить следующим образом:
(define (square-tree tree) (tree-map square tree))
def squareTree3[A, B](tree: Tree[A])( fmap: (Tree[A], A => B) => Tree[B], f: A => B): Tree[B] = fmap(tree, f)
val tree = Tree.Branch(Tree.Leaf(1), Tree.Branch(Tree.Leaf(2), Tree.Leaf(3)))squareTree3[Int, Int](tree)((t, f) => t.map(f), x => x * x)// Branch(Leaf(1),Branch(Leaf(4),Leaf(9)))Упражнение 2.32
Множество можно представить как список его различных элементов, а множество его подмножествкак список списков. Например, если множество равно (1 2 3), то множество его подмножеств равно (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Закончите следующее определение процедуры, которая порождает множество подмножеств и дайте ясное объяснение, почему она работает:
(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map <??> rest)))))
Для пустого входящего списка множество различных элементов - это список из одного элемента - самого пустого списка. Если список не пустой, то множество его элементов можно разделить на две части: множество элементов без первого члена списка и это же множество с добавление первого члена.
def subset[A](list: List[A]): List[List[A]] = list match case Nil => List(Nil) case head :: tail => val rest = subset(tail) rest ++ rest.map(head :: _)
subset(List(1, 2, 3))// List(List(), List(3), List(2), List(2, 3), List(1), List(1, 3), List(1, 2), List(1, 2, 3)) 2.2.3. Последовательности как стандартные интерфейсы
В этом разделе представлен еще один мощный принцип проектирования для работы со структурами данных — использование стандартных интерфейсов (conventional interfaces).
Операции над последовательностями
Просеивание последовательности, выбирающее только те элементы, которые удовлетворяют данному предикату, осуществляется при помощи:
def filter[A](predicate: A => Boolean, sequence: List[A]): List[A] = if sequence.isEmpty then Nil else if predicate(sequence.head) then sequence.head :: filter(predicate, sequence.tail) else filter(predicate, sequence.tail)
filter[Int](_ % 2 == 0, List(1, 2, 3, 4, 5))// List(2, 4) Накопление осуществляется посредством:
def accumulate[A, B](op: (A, B) => B, initial: B, sequence: List[A]): B = sequence match case Nil => initial case head :: tail => op(head, accumulate(op, initial, tail))
accumulate[Int, Int](_ * _, 1, List(1, 2, 3, 4, 5))// 120accumulate[String, String](_ + _, "", List("a", "b", "c", "d", "e"))// "abcde"Упражнение 2.33
Заполните пропущенные выражения, так, чтобы получились определения некоторых базовых операций по работе со списками в виде накопления:
(define (map p sequence) (accumulate (lambda (x y) <??>) nil sequence)) (define (append seq1 seq2) (accumulate cons <??> <??>)) (define (length sequence) (accumulate <??> 0 sequence))
def map[A, B](f: A => B, sequence: List[A]): List[B] = accumulate[A, List[B]]((a, listB) => f(a) :: listB, List.empty[B], sequence)
def append[A](seq1: List[A], seq2: List[A]): List[A] = accumulate[A, List[A]]((a, listA) => a :: listA, seq1, seq2)
def length[A](list: List[A]): Int = accumulate[A, Int]((_, acc) => acc + 1, 0, list)
map[Int, Int](_ * 2, List(1, 2, 3, 4, 5))// List(2, 4, 6, 8, 10)append[Int](List(1, 2, 3), List(4, 5, 6))// List(4, 5, 6, 1, 2, 3)length[Int](List(1, 2, 3, 4, 5))// 5 Упражнение 2.34
Вычисление многочлена с переменной x при данном значении x можно сформулировать в виде накопления. Мы вычисляем многочлен \(a_{n}x^{n} + a_{n−1}x^{n−1} + ... + a_{1}x + a_{0}\) по известному алгоритму, называемому схема Горнера (Horner’s rule), которое переписывает формулу в виде \((... (a_{n}x + a_{n−1})x + ... + a_{1})x + a_{0})\)
Другими словами, мы начинаем с \(a_{n}\), умножаем его на x, и так далее, пока не достигнем \(a_{0}\). Заполните пропуски в следующей заготовке так, чтобы получить процедуру, которая вычисляет многочлены по схеме Горнера. Предполагается, что коэффициенты многочлена представлены в виде последовательности, от \(a_{0}\) до \(a_{n}\).
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) <??>) 0 coefficient-sequence))Например, чтобы вычислить \(1 + 3x + 5x^{3} + x^{5}\) в точке x = 2, нужно ввести (horner-eval 2 (list 1 3 0 5 0 1))
def hornerEval(x: Int, coeff: List[Int]): Int = accumulate[Int, Int]((c, acc) => c + acc * x, 0, coeff)
hornerEval(2, List(1, 3, 0, 5, 0, 1)) // 79Упражнение 2.35
Переопределите count-leaves из раздела 2.2.2 в виде накопления:
(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))
enum Tree[+A]: self =>
case Leaf(value: A) case Branch(left: Tree[A], right: Tree[A])
def map[B](f: A => B): Tree[B] = self match case Leaf(value) => Leaf(f(value)) case Branch(left, right) => Branch(left.map(f), right.map(f))
def accumulate[A, B](op: (A, B) => B, initial: B, tree: Tree[A]): B = tree match case Tree.Leaf(value) => op(value, initial) case Tree.Branch(left, right) => accumulate(op, accumulate(op, initial, left), right)
def countLeaves[A](tree: Tree[A]): Int = accumulate[Int, Int](_ + _, 0, tree.map(_ => 1))
countLeaves(Tree.Branch(Tree.Leaf(1), Tree.Branch(Tree.Leaf(2), Tree.Leaf(3))))// 3Упражнение 2.36
Процедура accumulate-n подобна accumulate, только свой третий аргумент она воспринимает как последовательность последовательностей, причем предполагается, что все они содержат одинаковое количество элементов. Она применяет указанную процедуру накопления ко всем первым элементам последовательностей, вторым элементам последовательностей и так далее, и возвращает последовательность результатов. Например, если s есть последовательность, состоящая из четырех последовательностей, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), то значением (accumulate-n + 0 s) будет последовательность (22 26 30). Заполните пробелы в следующем определении accumulate-n:
(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init <??>) (accumulate-n op init <??>))))
def accumulateN[A, B]( op: (A, B) => B, initial: B, seqs: List[List[A]]): List[B] = seqs match case head :: tail if head.nonEmpty => accumulate(op, initial, seqs.map(_.head)) :: accumulateN(op, initial, seqs.map(_.tail)) case _ => Nil
accumulateN[Int, Int]((x, y) => x + y, 0, List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9), List(10,11,12)))// List(22, 26, 30) Упражнение 2.37
Предположим, что мы представляем векторы \(v = (v_{i})\) как последовательности чисел, а матрицы \(m = (m_{ij})\) как последовательности векторов (рядов матрицы). Например, матрица
\(\begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 6 \\ 6 & 7 & 8 & 9 \end{bmatrix}\)
представляется в виде последовательности ((1 2 3 4) (4 5 6 6) (6 7 8 9)). Имея такое представление, мы можем использовать операции над последовательностями, чтобы кратко выразить основные действия над матрицами и векторами. Эти операции (описанные в любой книге по матричной алгебре) следующие:
Скалярное произведение (dot-product v w) - возвращает сумму \(\sum_{i}^{}v_{i}w_{i}\);
Произведение матрицы и вектора (matrix-*-vector m v) возвращает вектор t, \(t_{i} = \sum_{i}^{}m_{ij}v_{i}\);
Произведение матриц (matrix-*-matrix m n) возвращает матрицу p, где \(p_{ij} = \sum_{k}^{}m_{ik}n_{kj}\)
Транспозиция (transpose m) возвращает матрицу n, где \(n_{ij} = m_{ji}\)
Скалярное произведение мы можем определить так:
(define (dot-product v w) (accumulate + 0 (map * v w)))Заполните пропуски в следующих процедурах для вычисления остальных матричных операций.
(define (matrix-*-vector m v) (map <??> m)) (define (transpose mat) (accumulate-n <??> <??> mat)) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map <??> m)))
Определим операцию map2, которая принимает два списка и возвращает список, в котором каждый элемент -
результат применения заданной функции к соответствующей паре элементов заданных двух списков.
dotProduct определяется через map2:
def map2[A, B, C](seq1: List[A], seq2: List[B], f: (A, B) => C): List[C] = seq1.lazyZip(seq2).map{ case (a, b) => f(a, b) }
def dotProduct(v: List[Int], w: List[Int]): Int = accumulate[Int, Int](_ + _, 0, map2(v, w, _ * _))
dotProduct(List(1, 2, 3), List(4, 5, 6))// 32Остальные операции определяются через dotProduct:
def matrixVectorMultiply(m: List[List[Int]], v: List[Int]): List[Int] = map(row => dotProduct(row, v), m)
matrixVectorMultiply( List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)), List(1, 2, 3))// List(14, 32, 50)
def transpose[A](m: List[List[A]]): List[List[A]] = accumulateN[A, List[A]]((a, acc) => a :: acc, List.empty, m)
transpose(List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)))// List(List(1, 4, 7), List(2, 5, 8), List(3, 6, 9))
def matrixMatrixMultiply(m: List[List[Int]], n: List[List[Int]]): List[List[Int]] = val cols = transpose(n) val matrix = map((col: List[Int]) => matrixVectorMultiply(m, col), cols) transpose(matrix)
matrixMatrixMultiply( List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)), List(List(1, 4, 7), List(2, 5, 8), List(3, 6, 9)))// List(List(14, 32, 50), List(32, 77, 122), List(50, 122, 194))Упражнение 2.38
Процедура accumulate известна также как fold-right (правая свертка), поскольку она комбинирует первый элемент последовательности с результатом комбинирования всех элементов справа от него. Существует также процедура fold-left (левая свертка), которая подобна fold-right, но комбинирует элементы в противоположном направлении:
(define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence))Каковы значения следующих выражений?
(fold-right / 1 (list 1 2 3)) (fold-left / 1 (list 1 2 3)) (fold-right list nil (list 1 2 3)) (fold-left list nil (list 1 2 3))Укажите свойство, которому должна удовлетворять op, чтобы для любой последовательности fold-right и fold-left давали одинаковые результаты.
Процедура foldLeft на Scala:
def foldLeft[A, B](op: (B, A) => B, initial: B, sequence: List[A]): B = def iter(result: B, rest: List[A]): B = rest match case Nil => result case head :: next => iter(op(result, head), next)
iter(initial, sequence)Результат выполнения операций:
foldRight[Double, Double](_ / _, 1.0, List(1.0, 2.0, 3.0))// 1.5foldLeft[Double, Double](_ / _, 1.0, List(1.0, 2.0, 3.0))// 0.16666666666666666
foldRight[Int, List[Int]](_ :: _, Nil, List(1, 2, 3))// List(1, 2, 3)foldLeft[Int, List[Int]]((b, a) => a :: b, Nil, List(1, 2, 3))// List(3, 2, 1)Если операция op ассоциативна, то результаты foldLeft и foldRight будут одинаковыми.
Ассоциативность операции означает, что для любых трех аргументов a, b и c выполняется следующее условие
op(a, op(b, c)) = op(op(a, b), c).
Упражнение 2.39
Закончите следующие определения reverse (упражнение 2.18) в терминах процедур fold-right и fold-left из упражнения 2.38.
(define (reverse sequence) (fold-right (lambda (x y) <??>) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) <??>) nil sequence))
def reverseViaFoldRight[A](sequence: List[A]): List[A] = foldRight((a: A, b: List[A]) => b :+ a, Nil, sequence)
def reverseViaFoldLeft[A](sequence: List[A]): List[A] = foldLeft((b: List[A], a: A) => a :: b, Nil, sequence)
reverseViaFoldRight(List(1, 2, 3))// List(3, 2, 1)reverseViaFoldLeft(List(1, 2, 3))// List(3, 2, 1)Вложенные отображения
Ссылки: