6 functional programming concepts. Use and examples of use
Good day! My name is Ivan Smolin, I am a developer of mobile applications on the iOS platform. Today I invite you to plunge into the world of functional programming. The article is mostly theoretical in nature than practical. In it, I will try to define the basic concepts of functional programming and show examples of implementations in C, Objective-C, Swift, Haskell.
Functional programming is a programming paradigm that focuses on computation through functions in the mathematical style, immutability, expressiveness and reduction in the use of variables and states ( link ).
There are 6 main concepts:
')
This is an entity that supports operations that are usually available for other entities. These operations are usually. include: passing an entity as an argument, returning an entity from a function, and assigning it to a variable.
Simplifies working with functions, giving more features and ways to use them.
In the above example, the get_print_func function creates a variable in which it stores the function reference, and then returns it. And below the code, we pass the result returned to us by the function get_print_func to another function. These are the operations available to us through first-class functions.
This is a function that operates on other functions. Operates by getting them as a parameter or returning them.
As in the case of functions of the first order, this concept gives us more opportunities to work with functions. This concept also opens up the possibility of using functions as event handlers that the system or a library can tell us by calling the first-class function passed to it.
See previous example. There is a function that reads the directory. And recursively reads all subfolders. For each file found, it calls the function we passed - callback.
The example in C shows that in the 70s of the last century it was possible to operate with functions of the first class and higher order. Blocks appeared in Objective-C. Unlike functions, they can capture variables and some state. Closure appeared in Swift. In essence, this is the same thing as blocks in Objective-C.
This is a function that fulfills two conditions. The function always returns the same result with the same input parameters. And the result calculation does not cause visible semantic side effects or output to the outside.
A pure function is usually an indicator of well-written code, since such functions are easy to cover with tests, they can be easily transferred and reused.
The following fragment shows examples of pure functions (they are marked with the comment “pure”).
Used everywhere. For example, standard math libraries in almost all programming languages contain mostly pure functions.
The immutable state is the state of an object that cannot be changed after the object has been created. The state of an object here implies a set of values for its properties.
Since immutable objects guarantee us that during their life cycle they cannot change their state, we can be sure that using or transferring such objects to other places of the program will not lead to any unintended consequences. This is especially important when working in a multithreaded environment.
In C language “out of the box” there is no possibility to create immutable objects. The const keyword prohibits changing the value only in the current context, however, if we pass a reference to this value to a function, then this function will be able to change the data found on this link. You can solve this problem through encapsulation (through public and private header files). However, in this case we must independently implement the mechanism of “protecting” data from changes.
In Objective-C, too, nothing new has come. Added only base classes that do not allow to change their internal state and their mutable (mutable) counterparts.
In Swift, we have the let keyword, which ensures that a variable or structure cannot be changed after creation.
An example of using immutable values in Swift:
An optional type is a generic type that represents the encapsulation of an optional value. This type contains either a specific value or a null value.
Bring the notion of a null value to a higher level. Allows you to work with optional values using the syntax constructs of the language.
Practically in all modern, especially young, languages there is a concept of an optional type and syntactic constructions for working with it. In Swift, this is a construction if let, or switch case:
Pattern Matching - the act of checking the sequence of tokens for a match with a specific pattern.
Lets us write shorter, problem-focused code.
Here is an example on Haskell. In my opinion, the best example of pattern matching.
The sum function takes as its input an array of objects. If the sum function gets an empty array, the sum of the elements is 0. If the array contains one object, we simply get this object. If there are more objects, then we add the first object and the tail of the array, then we repeat the operation recursively until we have elements in the tail of the array. We have described this function as a pattern. This means that we describe all the possible (or necessary for us at the moment) options for the operation of this function depending on the input values. Without if and other conditional statements.
The addOne function adds one to the number. It takes as input an argument of type Maybe Int and returns a value of the same type as output. Maybe is a monad that contains either a value (Just a) or nothing (Nothing). The addOne function works as follows: if there is a value in the function argument, (Just a), then we add one and return the argument, if there is nothing (Nothing), then we return nothing (Nothing).
In Swift, pattern-matching looks like this:
Pattern Matching, in my opinion, is quite limited in Swift, you can only check cases in the switch statement, however, this can be done quite flexibly.
Lazy evaluation is a calculation strategy that defers the evaluation of an expression until the moment when the value of this expression is necessary.
Allows you to postpone the calculation of some code until a certain or predetermined point in time.
It can be used to initialize fields in a class after it is initialized. This technique allows you to avoid duplication of the field initialization code in several class constructors and to postpone the initialization of this field until it becomes necessary. In the example above, the value of the createdAt field is calculated at the time of the first access to it.
An infinite data structure is a structure whose definition is given in terms of infinite ranges or incessant recursion, but real values are calculated only at the moment they are needed.
Allows us to determine data structures of infinite or enormous size without spending resources on the calculation of the values of this structure.
Here is an example on Swift. We take Range from one to trillion. Make a map on this Range - turn a billion values into strings. Such a number of lines hardly fit in the RAM of a personal computer. But, nevertheless, we can easily do it and take the necessary values. In the example, the lambda passed to the map function is called only twice. Everything is done very lazily.
In Swift, we are always limited to Range. We cannot create an infinite range of values. You can fake it and do it differently, but out of the box there is no such thing. But in Haskell is.
You can make a list from one to infinity. Make a map to all elements (number and number, which will turn into a string). Then take any elements of either a slice or a list. The cut will also be returned by a lazy list.
Haskell is the laziest language I've ever seen. In it, arrays can contain boxed (packed) and unboxed (unpacked) elements. In the case when the array elements are packed (not yet computed) during array operations that do not require obtaining the value of the elements, these values will not be calculated. An example of such an operation is the length method.
Lambda calculus is a formal system in mathematical logic for expressing computation based on the operations of application and abstraction of functions by means of linking and changing variables.
The concept of lambda calculus brings to programming languages the concept of anonymous functions that can capture external (with respect to a function) variables.
Below is an example on Swift, where we use lambda instead of named functions.
Here is an example of how to calculate the sum or average of one line. And filter.
The concept of lambda calculus also introduces the concept of currying into programming languages. Currying allows us to split a function with several parameters into several functions with one parameter. This enables us to obtain the result of the calculation of intermediate functions and apply different arguments to these functions to obtain several results.
Here we get the result of calculating the power of the numbers in the array and then add a certain number to this result. It is important to note that the calculation of degrees occurs only once when the call to the raiseToPowerThenAdd function is called.
In my opinion, the most important concepts for developing mobile software (in terms of code quality) are: the concept of pure functions and the concept of optionality. The first one gives us a clear and simple idea how to make our code more portable, high-quality and testable. The second one makes us think about possible extreme cases and errors that may come from outside, and process them correctly.
I hope the material will be useful and your code will be even better.
Ivan Smolin, iOS developer.
Functional programming is a programming paradigm that focuses on computation through functions in the mathematical style, immutability, expressiveness and reduction in the use of variables and states ( link ).
There are 6 main concepts:
')
- first class concept and higher order functions
- clean function concept
- immutable state concept
- concept of optionality and image matching
- concept of laziness and endless data structures
- lambda calculus concept
First class function
What is it
This is an entity that supports operations that are usually available for other entities. These operations are usually. include: passing an entity as an argument, returning an entity from a function, and assigning it to a variable.
What is useful
Simplifies working with functions, giving more features and ways to use them.
Examples of using
typedef void (*callback_func_t) (char*); void list_files(char* path, callback_func_t callback) { // recursive read directory structure ... } void print_file_path(char* file_path) { printf("%s\n", file_path); } callback_func_t get_print_func() { callback_func_t callback_var = &print_file_path; return callback_var; } list_files("/tmp/", get_print_func()); In the above example, the get_print_func function creates a variable in which it stores the function reference, and then returns it. And below the code, we pass the result returned to us by the function get_print_func to another function. These are the operations available to us through first-class functions.
Higher order function
What is it
This is a function that operates on other functions. Operates by getting them as a parameter or returning them.
What is useful
As in the case of functions of the first order, this concept gives us more opportunities to work with functions. This concept also opens up the possibility of using functions as event handlers that the system or a library can tell us by calling the first-class function passed to it.
Examples of using
See previous example. There is a function that reads the directory. And recursively reads all subfolders. For each file found, it calls the function we passed - callback.
The example in C shows that in the 70s of the last century it was possible to operate with functions of the first class and higher order. Blocks appeared in Objective-C. Unlike functions, they can capture variables and some state. Closure appeared in Swift. In essence, this is the same thing as blocks in Objective-C.
Net function
What is it
This is a function that fulfills two conditions. The function always returns the same result with the same input parameters. And the result calculation does not cause visible semantic side effects or output to the outside.
What is useful
A pure function is usually an indicator of well-written code, since such functions are easy to cover with tests, they can be easily transferred and reused.
Examples of using
The following fragment shows examples of pure functions (they are marked with the comment “pure”).
func quad1(x: Int) -> Int { // pure func square() -> Int { return x * x } return square() * square() } func quad2(x: Int) -> Int { // pure func square(y: Int) -> Int { // pure return y * y } return square(x) * square(x) } func square(x: Int) -> Int { // pure return x * x } func cube(x: Int) -> Int { return square(x) * x } func printSquareOf(x: Int) { print(square(x)) } let screenScale = 2.0 func pixelsToScreenPixels(pixels: Int) -> Int { return pixels * Int(screenScale) } Used everywhere. For example, standard math libraries in almost all programming languages contain mostly pure functions.
Immutable state
What is it
The immutable state is the state of an object that cannot be changed after the object has been created. The state of an object here implies a set of values for its properties.
What is useful
Since immutable objects guarantee us that during their life cycle they cannot change their state, we can be sure that using or transferring such objects to other places of the program will not lead to any unintended consequences. This is especially important when working in a multithreaded environment.
In C language “out of the box” there is no possibility to create immutable objects. The const keyword prohibits changing the value only in the current context, however, if we pass a reference to this value to a function, then this function will be able to change the data found on this link. You can solve this problem through encapsulation (through public and private header files). However, in this case we must independently implement the mechanism of “protecting” data from changes.
In Objective-C, too, nothing new has come. Added only base classes that do not allow to change their internal state and their mutable (mutable) counterparts.
In Swift, we have the let keyword, which ensures that a variable or structure cannot be changed after creation.
Examples of using
An example of using immutable values in Swift:
let one = 1 one = 2 // compile error let hello = "hello" hello = "bye" // compile error let argv = ["uptime", "--help"] argv = ["man", "reboot"] // compile error argv[0] = "man" // compile error Optional type
What is it
An optional type is a generic type that represents the encapsulation of an optional value. This type contains either a specific value or a null value.
What is useful
Bring the notion of a null value to a higher level. Allows you to work with optional values using the syntax constructs of the language.
Examples of using
Practically in all modern, especially young, languages there is a concept of an optional type and syntactic constructions for working with it. In Swift, this is a construction if let, or switch case:
let some: String? = nil switch (some) { case .None: print("no string") case .Some(let str): print("string is: \(str)") } Pattern Matching
Pattern Matching - the act of checking the sequence of tokens for a match with a specific pattern.
What is useful
Lets us write shorter, problem-focused code.
Examples of using
Here is an example on Haskell. In my opinion, the best example of pattern matching.
sum :: (Num a) => [a] -> a sum [] = 0 -- no elements sum (x:[]) = x -- one element sum (x:xs) = x + sum xs -- many elements The sum function takes as its input an array of objects. If the sum function gets an empty array, the sum of the elements is 0. If the array contains one object, we simply get this object. If there are more objects, then we add the first object and the tail of the array, then we repeat the operation recursively until we have elements in the tail of the array. We have described this function as a pattern. This means that we describe all the possible (or necessary for us at the moment) options for the operation of this function depending on the input values. Without if and other conditional statements.
addOne :: Maybe Int -> Maybe Int addOne (Just a) = Just (a + 1) -- not empty value addOne Nothing = Nothing -- empty value The addOne function adds one to the number. It takes as input an argument of type Maybe Int and returns a value of the same type as output. Maybe is a monad that contains either a value (Just a) or nothing (Nothing). The addOne function works as follows: if there is a value in the function argument, (Just a), then we add one and return the argument, if there is nothing (Nothing), then we return nothing (Nothing).
In Swift, pattern-matching looks like this:
let somePoint = (1, 1) switch somePoint { case (0, 0): print("point at the origin") case (_, 0): print("(point on the x-axis") case (0, _): print("point on the y-axis") case (-2...2, -2...2): print("point inside the box") default: print("point outside of the box") } Pattern Matching, in my opinion, is quite limited in Swift, you can only check cases in the switch statement, however, this can be done quite flexibly.
Laziness or lazy calculations
What is it
Lazy evaluation is a calculation strategy that defers the evaluation of an expression until the moment when the value of this expression is necessary.
Than useful
Allows you to postpone the calculation of some code until a certain or predetermined point in time.
Usage example
let dateFormatter = NSDateFormatter() struct Post { let id: Int let title: String let creationDate: String lazy var createdAt: NSDate? = { return dateFormatter.dateFromString(self.creationDate) }() } It can be used to initialize fields in a class after it is initialized. This technique allows you to avoid duplication of the field initialization code in several class constructors and to postpone the initialization of this field until it becomes necessary. In the example above, the value of the createdAt field is calculated at the time of the first access to it.
Infinite data structure
An infinite data structure is a structure whose definition is given in terms of infinite ranges or incessant recursion, but real values are calculated only at the moment they are needed.
What is useful
Allows us to determine data structures of infinite or enormous size without spending resources on the calculation of the values of this structure.
Examples of using
Here is an example on Swift. We take Range from one to trillion. Make a map on this Range - turn a billion values into strings. Such a number of lines hardly fit in the RAM of a personal computer. But, nevertheless, we can easily do it and take the necessary values. In the example, the lambda passed to the map function is called only twice. Everything is done very lazily.
let bigRange = 1...1_000_000_000_000 // from one to one trillion let lazyResult = bigRange.lazy.map { "Number \($0)" } // called 3 times let fourHundredItem = lazyResult[400] // "Number 400" let lazySlice = lazyResult[401...450] // Slice<LazyMapCollection<Range<Int>, String>> let fiveHundredItem = lazyResult[500] // "Number 500" In Swift, we are always limited to Range. We cannot create an infinite range of values. You can fake it and do it differently, but out of the box there is no such thing. But in Haskell is.
You can make a list from one to infinity. Make a map to all elements (number and number, which will turn into a string). Then take any elements of either a slice or a list. The cut will also be returned by a lazy list.
infiniteList = [1..] mappedList = map (\x -> "Number " ++ show x) infiniteList -- called 2 times fourHundredItem = mappedList !! 400 -- “Number 400” lazySlice = take (450 - 400) (drop 400 mappedList) -- [401..450] fiveHundredItem = mappedList !! 500 -- “Number 500” lazyArray = [2+1, 3*2, 1/0, 5-4] -- item values not evaluated lengthOfArray = length lazyArray -- still not evaluated Haskell is the laziest language I've ever seen. In it, arrays can contain boxed (packed) and unboxed (unpacked) elements. In the case when the array elements are packed (not yet computed) during array operations that do not require obtaining the value of the elements, these values will not be calculated. An example of such an operation is the length method.
Lambda calculus
What is it
Lambda calculus is a formal system in mathematical logic for expressing computation based on the operations of application and abstraction of functions by means of linking and changing variables.
Than useful
The concept of lambda calculus brings to programming languages the concept of anonymous functions that can capture external (with respect to a function) variables.
Usage example
Below is an example on Swift, where we use lambda instead of named functions.
let numbers = [0,1,2,3,4,5,6,7,8,9,10] let stringNumbers = numbers.map { String($0) } // ["0","1","2","3","4","5","6","7","8","9","10"] let sum = numbers.reduce(0, combine: { $0 + $1 }) // 55 let avg = numbers.reduce(0.0, combine: { $0 + Double($1) / Double(numbers.count) }) // 5.0 let from4To7SquareNumbers = numbers.filter { $0 > 3 }.filter { $0 < 7 }.map { $0 * $0 } // [16, 25, 36] Here is an example of how to calculate the sum or average of one line. And filter.
The concept of lambda calculus also introduces the concept of currying into programming languages. Currying allows us to split a function with several parameters into several functions with one parameter. This enables us to obtain the result of the calculation of intermediate functions and apply different arguments to these functions to obtain several results.
Curry usage example
func raiseToPowerThenAdd(array: [Double], power: Double) -> ((Double) -> [Double]) { let poweredArray = array.map { pow($0, power) } return { value in return poweredArray.map { $0 + value } } } let array = [3.0, 4.0, 5.0] let intermediateResult = raiseToPowerThenAdd(array, power: 3) intermediateResult(0) // [27, 64, 125] intermediateResult(5) // [32, 69, 230] intermediateResult(10) // [37, 74, 135] Here we get the result of calculating the power of the numbers in the array and then add a certain number to this result. It is important to note that the calculation of degrees occurs only once when the call to the raiseToPowerThenAdd function is called.
Conclusion
In my opinion, the most important concepts for developing mobile software (in terms of code quality) are: the concept of pure functions and the concept of optionality. The first one gives us a clear and simple idea how to make our code more portable, high-quality and testable. The second one makes us think about possible extreme cases and errors that may come from outside, and process them correctly.
I hope the material will be useful and your code will be even better.
Ivan Smolin, iOS developer.
Source: https://habr.com/ru/post/314510/
All Articles