Функциональное программирование и язык F

let x : int = 3 + 5 + 3

Переменной с именем x будет сопоставлено значение выражения 3 + 5 + 3 (типа int). В общем виде переменные объявляются конструкцией

let hvari : htypei = hexpi.

При вычислении последовательности деклараций let, вычисляется первая декларация, а затем её значение подставляется в следующие выражения, в места, где упоминается соответствующая переменная. Например:

let x : int = 2 + 3

let y : int = x + 1

let z : int = 5 + y

Шаг 1:

let x : int = 5

let y : int = x + 1

let z : int = 5 + y

Шаг 2:

let x : int = 5

let y : int = 6

let z : int = 5 + y

Шаг 3:

let x : int = 5

let y : int = 6

let z : int = 11

Что произойдёт, если написать две  декларации с одинаковым именем переменной?

let x : int = 5

let x : int = 6

В отличии от переменных в императивной парадигме, в функциональном мире переменные не меняют своего значения. Их скорее следовало  бы называть “постоянными”. Имя переменной связывается с выражением (var binding).

Таким образом, во второй строке этого  примера будет создано новое связывание между именем x и выражением 6, а старое будет “забыто”.

Второй тип деклараций – это  декларация типов:

type coordinate = int ∗ int

После этой декларации переменная типа coordinate в программе будет означать int∗int. Общая форма декларации нового типа: htyvari = htypei.

Нотация int ∗ int здесь означает пару из двух int. Её также можно записать как (int, int).

Область видимости в F# – лексическая (она же статическая).

2.4.4 Проверка и вывод типов

F# – статически типизированный  язык с поддержкой определения типов. Это означает, что все конструкции имеют известный тип уже на этапе компиляции, а не на этапе выполнения программы.

Алгоритм проверки типов упрощённо  похож на вывод доказательства, где  типы элементарных выражений – это  аксиомы, а операции – это теоремы (правила вывода). Например, аксиомы:

23 : int

"He l lo " : string

Правила вывода:

<exp1> + <exp2> : int если <exp1> : int и <exp2> : int

<exp1> + <exp2> : string если <exp1> : string и <exp2> : string

Тогда 5 + 3 ∗ 2 : int, т.к. 5 : int – аксиома и 3 ∗ 2 : int, т.к. 3 : int и 2 : int – аксиомы.

Кроме того, F# – язык со строгой  типизацией. Это означает, что в выражениях отсутствует неявное приведение типов. Например, выражение 0.1+1 вызовет ошибку компиляции, т.к. операция + определена для двух int или двух float, но не для float и int.

2.4.5 Функции

Как и в других языках, функция  в языке F# имеет имя, может иметь параметры и принимать аргументы, а также функция имеет тело. В языке F# функции являются объектами первого порядка, т.е. могут возвращать функции и принимать функции в качестве аргумента.

Функции определяются с помощью  ключевого слова let. Формат декларации в общем виде: lethfunci hargi = hbodyi. Например, функцию

f(x) = 3 ∗ x + 2 можно определить как:

let f (x : int) : int = (3* x ) + 2

В случае, когда функции необходимо рекурсивно вызывать себя, в определение добавляется ключевое слово rec. Пример – функция вычисления факториала:

let rec fact =

if n = 0 then 1

else n ∗ fact(n − 1);;

2.4.6 Функциональный тип

Тип функции определяется как htype1i → htype2i, где htype1i – это тип аргумента, а htype2i – тип возвращаемого значения. Например, тип функции из первого примера будет int → int.

Как быть с функцией, у которой  количество аргументов превышает единицу? Например, функция суммы:

let sum a b = a + b

Её тип будет int → int → int или же int → (int → int). Таким образом исходную функцию можно рассматривать как функцию от одного параметра типа int, которая возвращает другую функцию типа int → int. Всякая функция с более чем одним аргументом может интерпретироваться как функция от первого аргумента, возвращающая функцию от оставшихся при фиксированном значении первого.

Этот приём функционального  программирования называется каррированием или каррингом в честь математика и логика Хаскелла Карри.

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

2.4.7 Применение и его порядок

Главная операция для функции –  это применение – подстановка  аргументов в тело функции:

|−> (3 ∗ 2) + 2

|−> 6 + 2

|−> 8

Есть несколько вариантов порядка  применения:

• aппликативный – самый “естественный” порядок, при котором аргументы функции полностью вычисляются до её вызова. Такой порядок используется в большинстве языков программирования;
• нормальный – порядок, при котором аргументы функции начинают вычисляться только тогда, когда в них возникает необходимость;
• ленивый – вариант реализации нормального порядка, при котором не происходит дублирования вычислений.

Для примера определим функцию double:

let double x = x + x

Пример аппликативного порядка:

double ( double 5)

|−> double (5 + 5)

|−> double 10

|−> 10 + 10

|−> 20

Пример нормального порядка:

double ( double 5)

|−> ( double 5) + ( double 5)

|−> 10 + 10

|−> 20

В F# есть поддержка ленивого порядка  редукции с помощью ключевого  слова lazy.

5. Работа в F#

2.5.1 Примеры кода

// открытие некоторых стандартных  пространств имен

open System

/// Очень простое константное  целое

let int1 = 1

/// Другое очень простое константное  целое

let int2 = 2

/// Добавление двух целых

let int3 = int1 + int2

// Функции на целых  

// ---------------------------------------------------------

/// Функция на целых

let f x = 2*x*x - 5*x + 3

/// Результат простого вычисления

let result = f (int3 + 4)

/// Другая функция на целых

let increment x = x + 1

/// Вычисление факториала целого

let rec factorial n = if n=0 then 1 else n * factorial (n-1)

/// Вычисление наибольшего общего  делителя двух целых

let rec hcf a b =// 2 параметра, разделенные пробелами

    if a=0 then b

    elif a<b then hcf a (b-a)// 2 аргумента, разделенные пробелами

    else hcf (a-b) b

    // аргументы функции  обычно разделяются пробелами

    // "let rec" определяет  рекурсивную функцию

// Кортежи

// ---------------------------------------------------------

// Простой кортеж целых

let pointA = (1, 2, 3)

// Простой кортеж целого, строки  и числа с плавающей точкой  двойной точности

let dataB = (1, "fred", 3.1415)

/// Функция, которая переставляет  два числа в кортеже

let Swap (a, b) = (b, a)

// Логические значения

// ---------------------------------------------------------

/// Простое логическое значение

let boolean1 = true

/// Другое простое логическое  значение

let boolean2 = false

/// Вычисление нового логического  значения с помощью операторов and, or и not

let boolean3 = not boolean1 && (boolean2 || false)

// Строки

// ---------------------------------------------------------

/// Простая строка

let stringA  = "Hello"

/// Другая простая строка

let stringB  = "world"

/// "Здравствуй, мир", вычисленная  с помощью соединения строк

let stringC  = stringA + " " + stringB

/// "Здравствуй, мир", вычисленная  с помощью функции библиотеки .NET

let stringD = String.Join(" ",[| stringA; stringB |])

// Функциональные списки

// ---------------------------------------------------------

/// Пустой список

let listA = [ ]          

/// Список с тремя целыми

let listB = [ 1; 2; 3 ]    

/// Список с тремя целыми, заметьте :: является операцией "cons"

let listC = 1 :: [2; 3]   

/// Вычисления суммы списка целых  с помощью рекурсивной функции

let rec SumList xs =

    match xs with

    | []    -> 0

    | y::ys -> y + SumList ys

/// Сумма списка

let listD = SumList [1; 2; 3] 

/// Список целых от 1 до 10 включительно

let oneToTen = [1..10]

/// Квадраты первых 10 целых

let squaresOfOneToTen = [ for x in 0..10 -> x*x ]

// Изменяемые массивы

// ---------------------------------------------------------

/// Создание массива

let arr = Array.create 4 "hello"

arr.[1] <- "world"

arr.[3] <- "don"

/// Вычисление длины массива  с помощью экземплярного метода  на объекте массива

let arrLength = arr.Length       

// Извлечение подмассива с помощью  slice-нотации

let front = arr.[0..2]

// Дополнительные коллекции

// ---------------------------------------------------------

/// Словарь с целыми ключами  и строковыми значениями

let lookupTable = dict [ (1, "One"); (2, "Two") ]

let oneString = lookupTable.[1]

// Функции

// ---------------------------------------------------------

/// Функция, возводящая в квадрат  свой входной параметр

let Square x = x*x             

// Сопоставление функции по списку  значений

let squares1 = List.map Square [1; 2; 3; 4]

let squares2 = List.map (fun x -> x*x) [1; 2; 3; 4]

// Конвейеры

let squares3 = [1; 2; 3; 4] |> List.map (fun x -> x*x)

let SumOfSquaresUpTo n =

  [1..n]

  |> List.map Square

  |> List.sum

// Типы: объединения

// ---------------------------------------------------------

type Expr =

  | Num of int

  | Add of Expr * Expr

  | Mul of Expr * Expr

  | Var of string

 

let rec Evaluate (env:Map<string,int>) exp =

    match exp with

    | Num n -> n

    | Add (x,y) -> Evaluate env x + Evaluate env y

    | Mul (x,y) -> Evaluate env x * Evaluate env y

    | Var id    -> env.[id]

let envA = Map.ofList [ "a",1 ;

                        "b",2 ;

                        "c",3 ]

            

let expT1 = Add(Var "a",Mul(Num 2,Var "b"))

let resT1 = Evaluate envA expT1

// Типы: записи

// ---------------------------------------------------------

type Card = { Name  : string;

              Phone : string;

              Ok    : bool }

let cardA = { Name = "Alf" ; Phone = "(206) 555-0157" ; Ok = false }

let cardB = { cardA with Phone = "(206) 555-0112"; Ok = true }

let ShowCard c =

  c.Name + " Phone: " + c.Phone + (if not c.Ok then " (unchecked)" else "")

// Типы: классы

// ---------------------------------------------------------

/// Двумерный массив

type Vector2D(dx:float, dy:float) =

    // Предварительно вычисленная длина вектора

    let length = sqrt(dx*dx + dy*dy)

    /// Смещение по оси  X

    member v.DX = dx

    /// Смещение по оси  Y

    member v.DY = dy

    /// Длина вектора

    member v.Length = length

    // Смещение вектора на  константу

    member v.Scale(k) = Vector2D(k*dx, k*dy)

// Типы: интерфейсы

// ---------------------------------------------------------

type IPeekPoke =

    abstract Peek: unit -> int

    abstract Poke: int -> unit

// Типы: классы с реализациями  интерфейсов

// ---------------------------------------------------------

/// Элемент интерфейса, подсчитывающий, сколько раз он был щелкнут

type Widget(initialState:int) =

    /// Внутреннее состояние  элемента интерфейса

    let mutable state = initialState

    // Реализация интерфейса IPeekPoke

    interface IPeekPoke with

        member x.Poke(n) = state <- state + n

        member x.Peek() = state

    /// Элемент интерфейса был щелкнут?

    member x.HasBeenPoked = (state <> 0)

let widget = Widget(12) :> IPeekPoke

widget.Poke(4)

let peekResult = widget.Peek()

// Печать