[Предыдущий пост]
Вот и ожидаемое, или не очень, продолжение. Сегодня мы проглотим синюю пилюлю, гордо олицетворяющую 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.