5. Примеры рекурсивного описания функций для обработки линейных списков

Length(L). Функция Length (Длина) подсчитывает отличные от nil атомы в данном списке L.

Length(L) = if Null(L) then 0

else 1+ Length(Tail(L))

HasMember(L, x). Функция HasMember (Элемент списка) возвращает значение True, если в списке L есть элемент x

HasMember(L, x) = if Null(L) then False

else if Eq(Head(L), x) then True

else HasMember(Tail(L), x)

FindMember(L, x). Функция FindMember (Найти элемент) ищет в списке L элемент x. Найденный элемент возвращается, но не удаляется из L. Если искомый элемент не найден, то возвращается nil. Если в L содержится несколько экземпляров одного и того же элемента, то функцией будет возвращен последний вставленный в L элемент.

Delete(L, x). Функция Delete (Удалить) удаляет указанный элемент x из списка L. Если в L содержится несколько экземпляров одного и того же элемента, то удаляется последний вставленный в L элемент.

Delete(L, x) = if Null(L) then nil

else if Eq(Head(L), x) then Tail(L)

else Cons(Head(L), Delete(Tail(L), x))

Destroy(L). Функция Destroy (Разрушить) удаляет все элементы из L.

ForEach(L, f). Функция ForEach (Для каждого) применяет функцию f ко всем элементам списка L и возвращает список результирующих значений, т. е.

ForEach(L, f) = (f(e₁), f(e₂), ..., f(e_n)).

Рекурсивное определение функции ForEach будет иметь вид

ForEach(L, f) = if Null(L) then nil

else Cons(f(Head(L)), ForEach(Tail(L), f))

FirstThat(L, f). Функция FirstThat (Первый, для которого) используется для выбора первого элемента списка L, для которого функция f возвращает значение True. Если в L содержится несколько экземпляров одного и того же элемента, то возвращается последний вставленный в L элемент. Если элемент не найден, то возвращается nil.

FirstThat(L, f) = if Null(L) then nil

else if f(Head(L)) then Head(L)

else FirstThat(Tail(L), f)

LastThat(L, f). Функция LastThat (Последний, для которого) сходна с предыдущей, но выбирается последний элемент списка L, для которого функция f возвращает значение True. Если в L содержится несколько экземпляров одного и того же элемента, то возвращается первый вставленный в L элемент. Если элемент не найден, то возвращается nil.

Функции ForEach, FirstThat и LastThat являются примерами функций, которые принято называть функциями высших порядков, т. к. они используют имена функций в качестве аргументов. Интересным примером функции высшего порядка является Reduction (Редуцирование). Функция Reduction берет в качестве аргументов списк L = (e₁, e₂, e₃, …, e_n), функцию g(y, z), где y и z – атомы, атом a и вычисляет значение по формуле g(e₁, g(e₂, g(e₃, …, g(e_n, a) … )).

Рекурсивно функцию Reduction можно определить так

Reduction(L, g, a) = if Null(L) then a

else g(Head(L), Reduction(Tail(L), g, a))

Например, если L – числовой список и Plus – операция, определенная как

Plus(y, z) = y + z, то будем иметь

Reduction(L, Plus, 0) = Summa(L),

где смысл функции Summa очевиден – сумма списка чисел.

Merge(L, M). Функция Merge (Соединить) берет в качестве аргументов два списка L и M и выдает как результат единый список, содержащий последовательно все элементы списка L и все элементы списка M.

Merge(L, M) = if Null(L) then M

else Сons(Head(L), Merge(Tail(L), M))

Интересной функцией является функция Revers (Обратить), которая выдает список с элементами, перечисленными в обратном порядке. Если предварительно определить функцию Append (Добавить), которая берет в качестве аргументов список L и элемент x и делает x новым последним членом списка L, то функцию Revers можно определить так

Revers(L) = if IsEmpty(L) then nil

else Append(Revers(Tail(L)), Head(L))

Определение подфункции Append будет иметь вид

Append(L, x) = if Null(L) then Cons(x, nil)

else Cons(Head(L), Append(Tail(L), x))

Между прочим, можно было бы определить подфункцию Append через функцию Merge следующим образом:

Append(L, x) = Merge(L, Cons(x, nil))

В этом случае программа обращения списка состояла бы из трех функциональных определений. Однако привычнее включить вызов Merge непосредственно в функцию Append и избавиться от функции Append, что приводит к программе

Revers(L) = if Null(L) then nil

else Merge(Revers(Tail(L)), Cons(Head(L), nil))

Merge(L, M) = if Null(L) then M

else Сons(Head(L), Merge(Tail(L), M))

Написание рекурсивных процедур часто кажется неестественным при отсутствии соответствующей практики. Для приобретения соответствующей практики рекомендуется самостоятельно рассмотреть рекурсивные варианты других известных алгоритмов обработки списков, используя не только “чистые” функции, не имеющие побочных эффектов, но и функции с побочным эффектом, вычисляющие значения своих аргументов, и функции высших порядков.