Душкин Роман Викторович darkus@yandex ru Москва, 2001 лекция

Вид материала

Лекция

Содержание Пример 5. Операция prefix. Пример 6. Функция определения длины списка Length. Пример 7. Функция слияния двух списков Append. Ответы для самопроверки

Подобный материал:

• Евгений Викторович Петров, 12.9kb.
• Демонстрационная версия рабочей программы по ен. Ф. 05 «Биология» для специальности, 34.32kb.
• Роман Москва «Детская литература», 3628.68kb.
• Фалалеев Роман Викторович руководитель Делового центра предпринимательской активности., 16.14kb.
• Прогнозирование потребности в педагогических кадрах в регионе фролов Юрий Викторович, 113.56kb.
• Сорокин Павел Викторович. Предмет: история ­­­ Класс: 10 программа, 999.87kb.
• 2001 Утвержден Минтопэнерго России, 1942.6kb.
• 117042, г. Москва, ул. Адмирала Лазарева, д. 52, корп. 3; тел.  +7(495) 500-91-58;, 1396.81kb.
• Пособие для логопедов Москва 2001 бек 74. 3 Удк 371. 927, 514.36kb.
• Сергей Викторович Тютин* Это очень важная лекция, 119.72kb.

Примеры

Пример 5. Операция prefix.

Для начала необходимо рассмотреть более подробно работу операции prefix. По­яс­не­ние работы будет проведено на трёх более или менее общих примерах:

1. prefix (a₁, a₂) = a₁ : a₂ (при этом результат не является элементом List_str (A)).

2. prefix (a₁, [b₁, b₂]) = [a₁, b₁, b₂]

3. prefix ([a₁, a₂], [b₁, b₂]) = [[a₁, a₂], b₁, b₂]

Пример 6. Функция определения длины списка Length.

Перед тем, как собственно начать реализовывать функцию Length, необходимо понять, что она должна возвращать. Понятийное определение результата функции Length может зву­чать как «количество элементов в списке, который передан функции в качестве па­ра­мет­ра». Здесь возникает два случая — функции передан пустой список и функции передан не­пустой список. С первым случаем все ясно — результат должен быть нулевым. Во вто­ром случае задачу можно разбить на две подзадачи, путем разделения переданного списка на голову и хвост при помощи операций head и tail.

Осмысленно, что операция head возвращает первый элемент списка, а операция tail воз­вращает список из оставщихся элементов. Пусть известна длина списка, полученного при помощи операции tail, тогда длина исходного списка будет равна известной длина, уве­личенной на единицу. В этом случае можно легко записать определение самой фун­к­ции Length:

Length ([]) = 0

Length (L) = 1 + Length (tail (L))

Пример 7. Функция слияния двух списков Append.

Реализовать функцию слияния (или сцепления) списков можно многими способами. Пер­вое, что приходит в голову — деструктивное присваивание. Т.е. заменить указатель на [] в конце первого списка на указатель на голову второго списка и тем самым получить ре­зуль­тат в первом списке. Однако здесь изменяется сам первый список. Такие приёмы зап­ре­щены в функциональном программировании (хотя, в очередной раз необходимо за­ме­тить, что в некоторых функциональных языках всё-таки есть такая возможность).

Второй способ состоит в копировании верхнего уровня первого списка и помещении в последний указатель копии ссылку на первый элемент второго списка. Этот способ хорош с точки зрения деструктивности (не выполняет деструктивных и побочных действий), однако требудет дополнительных затрат памяти и времени.

Append ([], L₂) = L₂

Append (L₁, L₂) = prefix (head (L₁), Append (tail (L₁), L₂))

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

Упражнения

1. Построить функции, вычисляющие N-ый элемент следующих рядов:
   
   1. a_n = xⁿ
      
   2. a_n = _{i = 1,n} i
      
   3. a_n = _{j = 1,n} (_{i = 1,j} i)
      
   4. a_n = _{i = 1,p} n^-i
      
   5. a_n = eⁿ = _{i = 0,} (nⁱ / i!)
      
2. Объяснить результаты операции prefix, показанные в примере 5. Для объяснения мож­но воспользоваться графическим методом.
   
3. Объяснить результат работы функции Append (пример 7). Пояснить, почему функция не является деструктивной.
   
4. Построить функции, работающие со списками:
   
   1. GetN — функция вычленения N-ого элемента из заданного списка.
      
   2. ListSumm — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
      
   3. OddEven — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
      
   4. Reverse — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
      
   5. Map — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
      

Ответы для самопроверки

Большинство ответов для самопроверки представляют собой лишь одни из возможных ва­риантов (в большинстве случаев наиболее интуитивные).

1. Функции, вычисляющие N-ый элемент рядов:
   

1. Power:
   

Power (X, 0) = 1

Power (X, N) = X * Power (X, N – 1)

2. Summ_T:
   

Summ_T (1) = 1

Summ_T (N) = N + Summ_T (N – 1)

3. Summ_P:
   

Summ_P (1) = 1

Summ_P (N) = Summ_T (N) + Summ_P (N – 1)

4. Summ_Power:
   

Summ_Power (N, 0) = 1

Summ_Power (N, P) = (1 / Power (N, P)) + Summ_Power (N, P – 1)

5. Exponent:
   

Exponent (N, 0) = 1

Exponent (N, P) = (Power (N, P) / Factorial (P)) + Exponent (N, P – 1)


Factorial (0) = 1

Factorial (N) = N * Factorial (N – 1)

2. Объяснение работы операции prefix можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции prefix также используется инфиксная запись пос­ред­ством символа двоеточия.
   
   1. Первый пример работы операции — определение самой операции. Рассматривать его нет смысла, ибо операция prefix определяется именно таким образом.
      
   2. prefix (a₁, [b₁, b₂]) = prefix (a₁, b₁ : (b₂ : [])) = a₁ : (b₁ : (b₂ : [])) = [a₁, b₁, b₂]
      (Эти преобразование проведены по определению списка).
      
   3. prefix ([a₁, a₂], [b₁, b₂]) = prefix ([a₁, a₂], b₁ : (b₂ : [])) = ([a₁, a₂]) : (b₁ : (b₂ : [])) =
      = [[a₁, a₂], b₁, b₂].
      
3. В качестве примера работы функции Append рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов: [a, b] и [c, d]. Опять же для того, чтобы не заг­ро­мож­дать объяснение, для записи операции prefix используется инфиксная форма. Для бо­лее полного понимания приведенного объяснения необходимо помнить определение спис­ка.
   

Append ([a, b], [c, d]) = a : Append ([b], [c, d]) = a : (b : Append ([], [c, d])) =
= a : (b : ([c, d])) = a : (b : (c : (d : []))) = [a, b, c, d].

4. Функции, работающие со списками:
   

1. GetN:
   

GetN (N, []) = _

GetN (1, H:T) = H

GetN (N, H:T) = GetN (N – 1, T)

2. ListSumm:
   

ListSumm ([], L) = L

ListSumm (L, []) = L

ListSumm (H1:T1, H2:T2) = prefix ((H1 + H2), ListSumm (T1, T2))

3. OddEven:
   

OddEven ([]) = []

OddEven ([X]) = [X]

OddEven (H1:[H2:T]) = prefix (prefix (H2, H1), OddEven (T))

4. Reverse:
   

Reverse ([]) = []

Reverse (H:T) = Append (Reverse (T), [H])

5. Map:
   

Map (F, []) = []

Map (F, H:T) = prefix (F (H), Map (F, T))