[Предыдущий пост]
Вот и ожидаемое, или не очень, продолжение. Сегодня мы проглотим синюю пилюлю, гордо олицетворяющую FP (functional programming), и погрузимся в функциональную часть F# еще глубже. Поговорим о функциях, рекурсии, pattern matching'е и еще о нескольких интересных вещах. Интересно? Тогда глотаем таблетку и начинаем погружение.
Для начала хотелось бы рассказать о истоках FP, о λ-исчислении. Ведь именно эта математическая теория, созданная Алонзо Чёрчем легла в основу функционального программирования. Долгую и нудную лекцию по математике я давать не буду, просто расскажу вкратце. В конце концов, потом можно будет удивить кого-нибудь своими познаниями не только в F#, но и в его математической подложке. В чем, собственно, заключается это страшное название λ-исчисление? В том, что Чёрч захотел обобщить математику так, чтобы абсолютно все можно было представить в виде одного из фундаментальных понятий — функции. Мало того, его теория предполагает что все есть функция. «А в чем проблема? Почему не использовать существующее понятие функции?» — спросит читатель. Дело в том, что математик хотел использовать функции везде и всюду, а, зачастую, им неудобно давать имя, как нас всех учили в школах/институтах:
Тогда Алонзо придумал нотацию, позволяющую записывать функцию без присваивания ей имени:
В данном случае функция абсолютно идентична предыдущему примеру, за исключением того, что у нее нет имени. Ей точно так же можно передать значение аргумента:
Так же в параметры к λ-функции можно передать другую λ-функцию. Думаю прямая аналогия с лямбда-функциями, с которыми мы встречались в предыдущей статье, ясно видна.
А я уже почти закончил с математикой. Почти. Ведь все знают что такое рекурсия? Вот и славно. Сейчас будем писать рекурсивную функцию (вызывающею саму себя) для вычисления чисел Фибоначчи. Числа Фибоначчи — последовательность чисел, где каждое последующее число равно сумме предыдущих:
Если записывать это на языке функций, то функция, возвращающая число Фибоначчи по его номеру в последовательности будет выглядеть вот так:
А на F# вот так:
Здесь есть два новых ключевых слова, на которые стоит обратить внимание:
Что происходит внутри функции? На самом деле, все очень просто: если аргумент n равен 1 или 2, то мы возвращаем 1, иначе мы возвращаем сумму двух предыдущих чисел в последовательности. На самом деле, match предоставляет намного больше возможностей, но к нему мы вернемся чуть позже, а для начала рассмотрим основные типы в F#.
Для того, чтобы объявить свой тип нужно, как ни странно, использовать ключевое слово type. Пока что мы ничего дельного объявить не можем, так что просто переопределим int:
Tuple, или кортеж — это некий композитный тип в F#. Для того, чтобы быстро понять что и как рассмотрим примеры:
Как видно из примера, кортеж — это сочетание двух или более типов (не именованных, но упорядоченных). point2d и point3d представляют точки на 2-х мерных и 3-х мерных плоскостях, personAndId — имя и id. Для удобства работы с кортежами в стандартной библиотеке F# есть две функции: fst и snd, которые возвращают первый и второй элемент кортежа соответственно. Как получить третий элемент?
А вот пример объявления типа-кортежа:
Конечно, речь пойдет не о пластинках. Записи — еще одна структурная единица F#. Отличаются они от кортежей тем, что каждое поле записи имеет имя, содержание все так же может быть любым. Рассмотрим синтаксис:
Думаю, пояснения не нужны.
Следующая структурная единица — объединения. Они позволяют совмещать данные различными путями. Вот пример простого объединения:
Теперь, когда читателю уже много известно о основных структурных единицах F# можно поговорить поподробнее о pattern matching'е. Match чем-то схож со switch'ем из императивных и ОО языков, только он предоставляет намного более широкие возможности. Единственное ограничение — шаблоны должны охватывать весь спектр возможных значений. Хочу заметить, что кажется это неудобным и абсурдным только сперва.
Более полное описание можно найти тут.
Допустим, нам нужна реализация бинарного дерева, имеющего тип, то есть дерево строк, дерево int'ов и т.п. Типы в F# можно обобщать, делается это таким образом:
Да, вот так просто выглядит обобщенное бинарное дерево на F#.
Ну что тут сказать, надеюсь, я старался не зря и этот пост тоже понравится многим. В следующий раз мы продолжим глотать синие пилюли, поговорим о списках и последовательностях, каррировании функций и о многом другом. Спасибо за чтение.
Во первых, msdn, там можно найти более подробное описание многого из того, о чем было рассказано сегодня.
Во вторых Functional Programming for the Real World (Tomas Petricek, Jon Skeet) — это книга для тех, кто привык к императивному подходу для решения проблем. несколько примеров из этого поста были частично взяты оттуда.
На самом деле, код, который был приведен в посте выше ужасен. Но, зато он прост для понимания. А для тех, кто хочет увидеть более функциональный подход приведу более грамотный пример (спасибо, onikiychuka):
Как уже говорилось выше, более подробно такие вот функции мы разберем в следующий раз.
Выражения вида
так же представляют собой механизм pattern matching'а. Спасибо, jack128 и onikiychuka.
Введение
Вот и ожидаемое, или не очень, продолжение. Сегодня мы проглотим синюю пилюлю, гордо олицетворяющую 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.