Введение в F#, the blue pill

[Предыдущий пост]

Введение

Вот и ожидаемое, или не очень, продолжение. Сегодня мы проглотим синюю пилюлю, гордо олицетворяющую FP (functional programming), и погрузимся в функциональную часть F# еще глубже. Поговорим о функциях, рекурсии, pattern matching'е и еще о нескольких интересных вещах. Интересно? Тогда глотаем таблетку и начинаем погружение.

Погружение

Для начала хотелось бы рассказать о истоках FP, о λ-исчислении. Ведь именно эта математическая теория, созданная Алонзо Чёрчем легла в основу функционального программирования. Долгую и нудную лекцию по математике я давать не буду, просто расскажу вкратце. В конце концов, потом можно будет удивить кого-нибудь своими познаниями не только в F#, но и в его математической подложке. В чем, собственно, заключается это страшное название λ-исчисление? В том, что Чёрч захотел обобщить математику так, чтобы абсолютно все можно было представить в виде одного из фундаментальных понятий — функции. Мало того, его теория предполагает что все есть функция. «А в чем проблема? Почему не использовать существующее понятие функции?» — спросит читатель. Дело в том, что математик хотел использовать функции везде и всюду, а, зачастую, им неудобно давать имя, как нас всех учили в школах/институтах:
f(x) = x - 5
f(6) = 6 - 5 = 1

Тогда Алонзо придумал нотацию, позволяющую записывать функцию без присваивания ей имени:
λx.x-5

В данном случае функция абсолютно идентична предыдущему примеру, за исключением того, что у нее нет имени. Ей точно так же можно передать значение аргумента:
(λx.x - 5) 6 = 6 - 5 = 1

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

«Хватит нести бред! Больше кода.»

А я уже почти закончил с математикой. Почти. Ведь все знают что такое рекурсия? Вот и славно. Сейчас будем писать рекурсивную функцию (вызывающею саму себя) для вычисления чисел Фибоначчи. Числа Фибоначчи — последовательность чисел, где каждое последующее число равно сумме предыдущих:
Fib = {0, 1, 1, 2, 3, 5, 8, ...}

Если записывать это на языке функций, то функция, возвращающая число Фибоначчи по его номеру в последовательности будет выглядеть вот так:
f(n) = f(n - 1) + f(n - 2)
f(1) = 1
f(2) = 1

А на F# вот так:

let rec fib n =
    match n with
    | 1 | 2 -> 1
    | n -> fib(n-1) + fib(n-2)

Здесь есть два новых ключевых слова, на которые стоит обратить внимание:

• rec — указывает, что функция рекурсивная
• match, with — это механизм pattern matching'а, для знакомых c C# или C/C++ pattern matching можно представить как некий switch на стероидах

Что происходит внутри функции? На самом деле, все очень просто: если аргумент n равен 1 или 2, то мы возвращаем 1, иначе мы возвращаем сумму двух предыдущих чисел в последовательности. На самом деле, match предоставляет намного больше возможностей, но к нему мы вернемся чуть позже, а для начала рассмотрим основные типы в F#.

Объявление типов

Для того, чтобы объявить свой тип нужно, как ни странно, использовать ключевое слово type. Пока что мы ничего дельного объявить не можем, так что просто переопределим int:

type myInt = int

Tuples

Tuple, или кортеж — это некий композитный тип в F#. Для того, чтобы быстро понять что и как рассмотрим примеры:

// тип int*int; в данном случае * - не умножение
let point2d = (10, 5)
// тип int*int*int
let point3d = (1, 1, 2)
// тип string*int
let personAndId = ("Some Name", 3)

let x2d = fst point2d
let y2d = snd point2d

Как видно из примера, кортеж — это сочетание двух или более типов (не именованных, но упорядоченных). point2d и point3d представляют точки на 2-х мерных и 3-х мерных плоскостях, personAndId — имя и id. Для удобства работы с кортежами в стандартной библиотеке F# есть две функции: fst и snd, которые возвращают первый и второй элемент кортежа соответственно. Как получить третий элемент?

// функция принимает в параметры кортеж; _ означает, что данное значение нам не интересно/может быть любым
let third (_, _, t) = t

А вот пример объявления типа-кортежа:

// объявляем тип-кортеж; первый элемент имеет тип string, второй int
type personAndId = string*int
// объявляем значение типа personAndId; при помощи оператора : мы явно указываем тип значения, привязываемого к идентификатору 
let person:personAndId  = ("Habr", 1)

Records aka записи

Конечно, речь пойдет не о пластинках. Записи — еще одна структурная единица F#. Отличаются они от кортежей тем, что каждое поле записи имеет имя, содержание все так же может быть любым. Рассмотрим синтаксис:

type person = {name : string; surname : string; id : int}
let sampleUser = {name = "Habra"; surname = "Habr"; id = 1}
let sampleUserName = sampleUser.name

Думаю, пояснения не нужны.

Discriminated unions, или размеченные объединения

Следующая структурная единица — объединения. Они позволяют совмещать данные различными путями. Вот пример простого объединения:

type Currency = 
    | Liter of float
    | Pint of float

let liter = Liter 5.0
let pint = Pint 10.0

Pattern matching, или сопоставление шаблонов

Теперь, когда читателю уже много известно о основных структурных единицах F# можно поговорить поподробнее о pattern matching'е. Match чем-то схож со switch'ем из императивных и ОО языков, только он предоставляет намного более широкие возможности. Единственное ограничение — шаблоны должны охватывать весь спектр возможных значений. Хочу заметить, что кажется это неудобным и абсурдным только сперва.

// функция, определяющая четность числа
let isOdd n = (n % 2 = 1)

// функция, выводящая числа от 1 до 3 в словесном виде
let oneToThree n = 
    match n with
    | 1 -> printfn "One"
    | 2 -> printfn "Two"
    | 3 -> printfn "Three"
    // для всех остальных значений используем следующий шаблон; тут так же возможно использовать _ вместо n
    | n -> printfn "Geather than three"

// определим кортеж
type Point = int * int
// пример matching'а для кортежей
let findZero point =
    match point with
    | (0, 0) -> printfn "x = 0 and y = 0"
    | (0, y) -> printfn "(0, %d)" y
    | (x, 0) -> printfn "(%d, 0)" x
    | _ -> printfn "x <> 0 and y <> 0"

type Person =
    | NameOnly of string
    | IdOnly of int
    // в этом объединении один из членов - кортеж
    | IdAndName of string * int
// пример matching'а для объединений
let personInfo person = 
    match person with
    | NameOnly(name) -> printf "Name is %s" name
    | IdOnly(id) -> printf "Id is %d" id
    | IdAndName(name, id) -> printf "Name is %s and Id is %d?" name id
// пример matching'a с дополнительными условиями
let matchWithCondition x = 
    match x with
    | x when x >= 5. && x <= 10. -> printfn "x is between 5.0 and 10.0"
    | _ -> ()

Более полное описание можно найти тут.

Обобщенные типы

Допустим, нам нужна реализация бинарного дерева, имеющего тип, то есть дерево строк, дерево int'ов и т.п. Типы в F# можно обобщать, делается это таким образом:

// обобщаемый тип помечается символом ' перед его названием
type 'a BinaryTree =
    // узлом дерева будет являться кортеж из дерева и дерева, кхе-кхе
    | Node of 'a BinaryTree * 'a BinaryTree
    | Value of 'a

(*
многим другой синтаксис может показаться более знакомым и понятным:
type BinaryTree<'a> =
    | Node of BinaryTree<'a> * BinaryTree<'a>
    | Value of 'a
*)

// так же, как и было с функциями и значениями, компилятор автоматически определит тип дерева
let tree1 = 
    Node(
        Node (Value 1, Value 2),
        Node (Value 5, Value 100)
        )

let tree2 = 
    Node(
        Node (Value "Binary tree", Value "in F#"),
        Node (Value "is so", Value "Simple")
        )

Да, вот так просто выглядит обобщенное бинарное дерево на F#.

Заключение

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

Что почитать

Во первых, msdn, там можно найти более подробное описание многого из того, о чем было рассказано сегодня.
Во вторых Functional Programming for the Real World (Tomas Petricek, Jon Skeet) — это книга для тех, кто привык к императивному подходу для решения проблем. несколько примеров из этого поста были частично взяты оттуда.

Для тех, кому было мало

Фибоначчи

На самом деле, код, который был приведен в посте выше ужасен. Но, зато он прост для понимания. А для тех, кто хочет увидеть более функциональный подход приведу более грамотный пример (спасибо, onikiychuka):

let fib = Seq.unfold (fun state ->Some(fst state + snd state, (snd state, fst state + snd state))) (1,1)
fib |> Seq.take 20

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

Сопоставление шаблонов

Выражения вида

let second (x, y) = y

let getValueFromOption (Some value) = value

так же представляют собой механизм pattern matching'а. Спасибо, jack128 и onikiychuka.