Рекурсивное определение функций

Как правило функциональная программа явл совокупность рекурсивны функций. Применение рекурсии должно быть корректным. Если мы определим функцию

f x = f (x+1)

то такая рекурсивная функция будет выполняться бесконечно пока не кончится память…

мы уже рассматривали функцию, которая вычисляет факториал. Рассмотрим её.

f n = if n==0 then 1 else n*f(n-1)

Вычислим f 3

f 3 =>+

двойная стрелочка обознач шаг в вычислении, а если еще будем добавлять знак + то это значит один или более шагов.

f наход в контексте…вводим в контектс связь

[n->3] и мы получаем тело функции

If n==0 then 1 else n*f(n-1) =>+

Контекст остался, мы получили n*f(n-1) =>*

Первый операнд – обращение к контексту, второй – к фукнции.

Здесь функция f вызывается второй раз, нам понадобится другой аргумент n, назовем его n’(переименование как в прологе)

[n’->n-1] if n’==0 then 1 else n’*f(n’-1)

Мы получили новое выражение… мы вычислили условие n’==0…

Старый знак вычислить за несколько шагов =>+ …. У нас в контексте получится что n’ связано с двойкой но это условие будет ложным значит нужно пойти путем

=>+ [n’->2] n’*f(n’-1)

Мы поулчаем новый контекст

= > [n’’->n’-1]

Здесь важно видеть, что на каждом шаге связи…они редуцируются по мере обращения к ним…

Рассмотрим новые синтаксические расширения

Есть синтаксическое расширение …более компактно описывает варианты.

Рассмотрим функцию, которая вычисляет абсолютное значение числа.

abs x = if x>=0 then x else –x

ее можно записать в более компактном виде…

abs x

| x<0 =-x

| x>=0 =x

Эти вертикальные черточки должны располагаться друг под другом.

Здесь можно исп ключевое слове othernoise

Abs x

| x<0 =-x

| othernoise =x

Некоторые функции можно исп….

НОД (а,в) =а, при а=в

НОД (а-в,в), при а>в

НОД(а,в-а), иначе

Это мы можем переписать с обозначениями хаскеля.

gcd a b

| a==b =a

| a>b = gcd (a-b) b

| othernoise = gcd a (b-a)

Так мы будем описывать варианты …

Рассмотрим функцию, которая вычисляет элементы последовательности чисел Фибоначчи.

fib (n) = 1, при n=0

1,при n=1

fib(n-2)+fib(n-1), иначе

fib n | n==0 =1

| n==1 = 1

| othernoise = fib(n-2) + fib(n-1)

Аргумент должен совпасть….

Применимо синтаксическое расширение – сопоставление с образцом.

Определение функций можно давать в нескольких вариантах, в каждом из которых вместе с формальными параметрами могут использоваться и шаблоны.

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

fib 0 = 1 (шаблон)

fib 1 = 1

fib n = fib(n-2)+fib(n-1)

определения будут применяться по очереди, сначала аргумент сравнивается с 0, если истина, то 1, иначе аргумент сравнивается с 1.

Если мы пользуемся сопоставлением с образцом, то нам надо учитывать чтобы множество образцов было исчерпывающим.

Примитивно рекурсивные функции, такие как факториал, они сводят задачу к задаче проще на 1.

Рассмотрим функцию, которая возводит число в заданную степень.

X⁰=1

Xⁿ=x*x^n-1

exp x 0 =1

exp x n =x*exp x (n-1)

она сразу получается из мат определения.

X⁰=1

X²ⁿ=(x*x)ⁿ,

X²ⁿ⁺¹=(x*x)ⁿ*x

Это позволяет вести рекурсию более крупными шагами.

Можем….

exp’ x 0 = 1

exp’ x n

| n `mod` 2 ==0 = exp’ (x*x) (n `div` 2)

| othernoise = exp’ (x*x) (n `div` 2) * x

Для того чтобы исключить повтор нужно дать локальное определение.

Здесь …варианты…они не явл выражениями…в них трудно использовать форму let.

Тогда эти варианты нужно заменить на if.

В хаскеле есть возможность для перечислений использовать раздел where в котором можно давать локальные определения.

exp’ x 0 = 1

exp’ x n

| n `mod` 2 ==0 = next

| othernoise = next*x

where {next=exp’ (x*x) (n `div` 2)}

where – введение локальных определений.

Выравнивание

В хаскеле отступы имеют значения

Конструкции хаскеля как и паскля имеют блочную структуру.

let {x=5; y=10} in x+y

или же

let

x=5

y=10

in x+y

когда компилятор находит ключевое слово за которым должно следовать перечисление ( в нашем случае это ключевое слово let).

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

Можно

X=5

+1

Y=10

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

В одной строке можно писать несколько определений, тогда их придется разделять точкой с запятой.

let

x=5

y=10; z=2

in x+y+z

тут важно еще отметить как правило вся программа хранящаяся в файле – это одно перечисление.

Fib 0 = 1

Fib 1 =1

Fib n = fib(n-2)+fib(n-1)

Компилятор расставит скобки фигурные. Точки с запятой, для перечисления…

Структурирование данных, списки, картежи.

Поговорим о списках.

В хаскелле есть спец объекты, назыв конструкторами данных., посредством которых данные можно собирать в структуры.

Эти конструкторы по сути своей такие как и функторы структур в прологе, и как функц символы в матлогике. Для построения списков требуется два конструктора.

Первый арности нуль, это пустой список. []

Т.е. это атом. Он обознач пустой список.

Есть конструктор арности два, двоеточие

:

Он исп …который конструирует 1:[]

Есть синтк расширение которое позволяет записывать списки перечислением элементов в квадратных скобках. [1,2,3]

А смысл его 1:2:3:[] . конструктор двоеточие ассоциативен вправо.

В хаскеле есть функции которые могут разбирать списки.

Функция head берет голову списка

Head[1,2,3] это будет значение 1.

Для хвоста есть tail,которая для tail[1,2,3]=>[2,3]

append.

append xs ys = if xs ==[]

then ys else head xs:

append(tail xs) ys

функция append обознач оператором ++, она ассоциативна вправо и имеет приоритет 5.

Рассмотрим сопоставление списков с образцом.

Здесь мы в качестве шаблонов можем брать конструкторы данных.

Если имеется аргумент

[]

(x:xs) то ждем список у которого есть голова и хвост. Шаблоны могут быть вложенными. Например

((x:xs)):ys)

Шаблон для списка списков, причем голова не пустая.

append [] ys = ys

append (x:xs) ys = x : append x sys

Функция принадлежности элемента списку member,

member _ [] = False

member x (y:ys) = x==y ||

member x ys

здесь мы исп еще один шаблон – анонимная переменная.

После разбора структур построенных структур можно исп выражение case

Оно позволяет рассматривать случай.

case xs of

[] -> e1

(y:ys) -> e2 y ys

Это элемент базового языка.

На его основе строится сопоставление с образцом. Строится смысл сопоставления. Т.е. когда встречается компилятору он строит case..

Мы тоже можем в функ прогр исп накапливающий параметр.

Мы уже рассматривали reverse.рассмотрим без накапл параметра

reverse [] =[]

reverse (x:xs) = reverse xs x ++ [x]

reverse xs = revrec [] xs

where

revrec acc [] = acc

revrec acc (x:sx)=

refrec (x:acc) xs

рассмотрим сортировки

1 сортировка слиянием.

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

Рассмотрим функцию слияния

Там оператор собака @ позволяет обозначить аргумент в целом и раскрыть его структуру.

merge lx@(x:xs) ly@ (y:ys)

| x<=y = x:merge x sly

| otherwise = y:merge lx ys

merge xs [] = xs

merge [] ys = ys

теперь мы рассмотрим основную функцию сортировки

в ней будут испо стандартные фукнции функция length, которая выч длину списка.

take n xs

drop n xs

строит список в котором отсутсвуют n первых элементов.

mergeSort [] = []

mergeSort [x] = [x]

mergeSort xs = merge

(mergeSort front) // первая часть списка

(mergeSort back) // остальные элементы

Where size = length xs `div` 2

Front = take size xs

Back = drop size xs

Картежи – фиксированная последовательность элементов, имеющая фикс длину

(1,2) пара

(True, 5, 8) тройка

(3, [1,2,3])

((True,5),8)

К базовому языку относятся пары

Конструкторы:

(,)

(,) 1 2

(,,) True 5 8 => (True, 5, 8)

Для пар определены 2 базовые функции

fst эта функция возвращ первый элемент пары

fst(1,2) => 1

snd (1,2) =>2

но основной способ это сопоставление с образцом.

fst (x,_) = x

snd(_,y) = y

есть важная укнция, раб с парами zip, она застегивает на молнию 2 списка.

Zip [1,2,3][4,5] =>

[(1,4),(2,5)]

Функцию zip очень легко определить рекурсивно.

Zip (x:xs) (y:ys) = (x,y): zip xs ys

Zip _ _ = []

Лекция

Картеж – особого рода функтор который позволяет несколько объектов объединить вместе. Конструктор составляет пару.

Есть функция zip3 строит…тройки…переменные

Рассмотрим пример функции, выч результат, это модификация функции fib.

Fib 5 -> fib 3 + fib 4 =>

Fib 3 + fib 2 + fib 3

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

Возьмем функцию с аргументом тройкой.

f ( i1, i2, n)

n – номер числа Фибоначчи. I2 его значение, а i1 - предыдущее значение.

Из этих данных можем вычислить след число Фибоначчи.

f ( i1, i2, n)= (i2,i1+i2,n+1)

эта функция делает один шаг вычисления.

fib 0 =1

fib n = fib’ (1,1,1)

where

fib’ t@(_,x,m)

|n==m = x

|otherwise = fib’(f t)

Математическая запись для списков

List comprehension…углубленное понимание того что представляют из себя списки.

Идея в том, что берем первый элемент и остальные элементы делим на большие меньшие, сортируем и сцепляем.