Functional programming in Swift. Start

Preface translator.

Celebrating the end of 2014, the famous Swift group SLUG from San Francisco selected the 5 most popular Swift videos for 2014 from meetings organized by it. And among them was the performance of Chris Eidhof "Functional programming in Swift".
Now Chris Eidhof is a famous person in the Swift community, he is the author of the recently published book Functional programming in Swift , one of the founders of the objc.io magazine, the organizer of the conference Functional Swift Conference , which took place on December 6th in Brooklyn and the future UIKonf conference .
But I opened it when he, one of the first, published a very simple elegant article about the effectiveness of the functional approach in Swift to JSON parsing.
In this article, there are no inaccessible concepts, no mystical mathematical “chimeras” of the type “Monad, Functor, Applicative functor”, on which Haskell programmers swear to the rest of the world, rolling their eyes.
There are no such innovations Swift, as generics (generics) and "type inference" (type inference).
If you want to smoothly move into functional programming in Swift, then you should read his article “Parsing JSON in Swift” and the performance on SLUG “Functional Programming in Swift” .

In order to facilitate this task, I will present the translation of the article and that part of the Chris Eidhof speech, which concerns JSON parsing and which collected the most questions on this talk.
By the way, you will certainly come to the study of “Monads, Functors, Applicative Functors” and, apparently, they will form the functional future of Swift , but this will happen later, but for now 2 user operators and their ingenious combination give us the desired result.

So Chris took the example of JSON data from Brent and David’s skeptical colleagues:
')

 var json : [String: AnyObject] = [ "stat": "ok", "blogs": [ "blog": [ [ "id" : 73, "name" : "Bloxus test", "needspassword" : true, "url" : "http://remote.bloxus.com/" ], [ "id" : 74, "name" : "Manila Test", "needspassword" : false, "url" : "http://flickrtest1.userland.com/" ] ] ] ] 

and set the task to convert this JSON data in a typed and secure way into an array of Swift structures:

 struct Blog { let id: Int let name: String let needsPassword : Bool let url: NSURL } 

Translation of the article “Parsing JSON data in Swift”.

First, I will show the final parsing functions that contain two operators: >> = and <*>. (Translator’s note. In the Github code, instead of the >> = operator, the >>> = operator is used, since the >> = operator in Swift is already taken and is used for a broken offset.)
These operators look a bit strange in Swift , but using them to completely JSON structure becomes very simple.
The rest of the article will be devoted to the description of the library code.
The following parsing works in such a way that if the JSON structure is incorrect (for example, the name missing or the id is not an integer), then the result is nil .
In our case, neither reflection nor KVO , we just have a couple of simple functions and some smart way to combine them:

 func parseBlog(blog: AnyObject) -> Blog? { return asDict(blog) >>= { mkBlog <*> int($0,"id") <*> string($0,"name") <*> bool($0,"needspassword") <*> (string($0, "url") >>= toURL) } } let parsed : [Blog]? = dictionary(json, "blogs") >>= { array($0, "blog") >>= { join($0.map(parseBlog)) } } 

What does the above code do?
Let's go through the most important features.
Let's look at the function of the dictionary . This function takes as input the input: [String: AnyObject] and a specific key: Sting , and tries to find in the original dictionary input by the key key also a dictionary, which will be the return value of the Optional :

 func dictionary(input: [String: AnyObject], key: String) -> [String: AnyObject]? { return input[key] >>= { $0 as? [String:AnyObject] } } 

For example, in the above example of JSON data, we expect that the key "blogs" is a dictionary. If the dictionary exists, then we return it, otherwise we return nil . We can write similar functions for arrays ( array ), strings ( strings ) and integers ( int ) (here the signature is only for these types, and the full code is on GitHub ):

 func array(input: [String:AnyObject], key: String) -> [AnyObject]? func string(input: [String:AnyObject], key: String) -> String? func int(input: [NSObject:AnyObject], key: String) -> Int? 

Now let's look at the outermost structure of our JSON data. This is a dictionary that is present in the structure under the key "blogs" . And under the key "blog" contains an array. For such parsing we can write the following code:

 if let blogsDict = dictionary(parsedJSON, "blogs") { if let blogsArray = array(blogsDict, "blog") { //  -    } } 

Instead, we define the >> = operator, which takes an Optional value and applies the function f to it only if this Optional not nil . This forces us to use the flatten “leveling” function, which removes (“aligns”) the nested Optional and leaves the only Optional .

 infix operator >>= {} func >>= <A,B> (optional : A?, f : A -> B?) -> B? { return flatten(optional.map(f)) } func flatten<A>(x: A??) -> A? { if let y = x { return y } return nil } 

Another operator that will be used very intensively is the <*> operator. To parse a single blog (Blog structure), we will have the following code:

 mkBlog <*> int(dict,"id") <*> string(dict,"name") <*> bool(dict,"needspassword") <*> (string(dict, "url") >>= toURL 

)

You can read it as a function call, which becomes executable only if all Optional values ​​are non- nil :

 mkBlog(int(dict,"id"), string(dict,"name"), bool(dict,"needspassword"), (string(dict, "url") >>= toURL)) 

Let's look at the definition of the <*> operator. It combines two Optional values: it takes a function as the left operand, and a parameter of this function as the right operand. He checks that both operands are not nil , and only then he applies the function.

 infix operator <*> { associativity left precedence 150 } func <*><A, B>(l: (A -> B)?, r: A?) -> B? { if let l1 = l { if let r1 = r { return l1(r1) } } return nil } 

What is mkBlog ? This is the curried function (curried function), which “wraps” our initializer.
First, we create a type function (Int, String, Bool, NSURL) -> Blog .
Then the curry function converts it to a function of type Int -> String -> Bool -> NSURL -> Blog :

 let mkBlog = curry {id, name, needsPassword, url in Blog(id: id, name: name, needsPassword: needsPassword, url: url) } 

This is necessary so that we can use mkBlog together with the <*> operator.
Let's look at the first line of code:

 // mkBlog : Int -> String -> Bool -> NSURL -> Blog // int(dict,"id") : Int? let step1 = mkBlog <*> int(dict,"id") 

We see that the combination of mkBlog and int (dict,"id") using the <*> operator gives us a new function of the type (String -> Bool -> NSURL -> Blog)? . And if we combine it with a string:

 let step2 = step1 <*> string(dict,"name") 

We get the function type (Bool -> NSURL -> Blog)? . And if we continue to do this, then we end up with the Optional value of Blog? .

I hope you understand how all these pieces fit together. By creating a small number of helper functions and operators, we can make strongly typed JSON parsing really very simple. Instead of Optional , you could also use another type, which includes errors (errors), but this is a topic for another post.

We write about all these things in our book in more detail. If you are interested, you can now access the book Functional Programming in Swift .

Translator's note.

The code for Chris Eidhof 's article “JSON parsing in Swift” with an improved print feature on the Playground on Github .
Although Chris said that it’s understandable how this all interacts together, in fact it’s not quite so, and that’s why I cite the translation of his speech at the SLUG meeting , where he shows in detail how to arrive at the desired result.

Translation of the speech "Functional programming in Swift".

This is an excerpt from the Chris Eidhof talk at a meeting in San Francisco in which he spoke about functional programming possibilities in Swift , but not as a substitute for object-oriented programming (OOP), but as an additional application development tool.
I provide only the translation of the part that relates to JSON parsing, and answers to questions.

Why functional programming?

There are many ways to solve problems besides object-oriented programming (OOP). You already know how to solve problems with OOP, but now Swift also offers very easy and convenient functional programming. In fact, some tasks are even easier to solve using functional programming!

One of these tasks is parsing JSON.

This is a conversion of untypical JSON dictionaries into regular, typed dictionaries.
JSON data are considered and the same task is set to convert them into an array of blogs [Blog] , as in the above article.

First try

The first version of the parseBlog function returns Blog if the types of all components are correct.
Nested if continue to run for each key and the corresponding type only if the conditions are met.
If all the conditions are met, we can construct the Blog value with the correct types and values ​​from the Optionals values.

 func parseBlog(blogDict: [String:AnyObject]) -> Blog? { if let id = blogDict["id"] as NSNumber? { if let name = blogDict["name"] as NSString? { if let needsPassword = blogDict["needspassword"] as NSNumber? { if let url = blogDict["url"] as NSString? { return Blog(id: id.integerValue, name: name, needsPassword: needsPassword.boolValue, url: NSURL(string: url) ) } } } } return nil } 

The first change is to create a string function that checks whether the type is NSString , because in our case we used it twice. This function takes a dictionary, searches for the key and returns the corresponding value only if the key matches the string. Otherwise, it returns nil .

 func string(input: [String:AnyObject], key: String) -> String? { let result = input[key] return result as String? } 

Second try

The second version now includes the above string function, and looks like this:

 func parseBlog(blogDict: [String:AnyObject]) -> Blog? { if let id = blogDict["id"] as NSNumber? { if let name = string(blogDict, "name") { if let needsPassword = blogDict["needspassword"] as NSNumber? { if let url = string(blogDict, "url") { return Blog(id: id.integerValue, name: name, needsPassword: needsPassword.boolValue, url: NSURL(string: url) ) } } } } return nil } 

Other changes in the code are due to the fact that for numbers we will create a function similar to the string function. This function searches for a number and makes a cast, if it exists. We can create similar functions for the int and bool types. For Optionals we can also use map , which is executed only if the value exists.

 func number(input: [NSObject:AnyObject], key: String) -> NSNumber? { let result = input[key] return result as NSNumber? } func int(input: [NSObject:AnyObject], key: String) -> Int? { return number(input,key).map { $0.integerValue } } func bool(input: [NSObject:AnyObject], key: String) -> Bool? { return number(input,key).map { $0.boolValue } } 

Third attempt

The code that we refactorized now looks a bit more declarative:

 func parseBlog(blogDict: [String:AnyObject]) -> Blog? { if let id = int(blogDict, "id") { if let name = string(blogDict, "name") { if let needsPassword = bool(blogDict, "needspassword") { if let url = string(blogDict, "url") { return Blog(id: id, name: name, needsPassword: needsPassword, url: NSURL(string: url) ) } } } } return nil } 

We can continue to improve our code, trying to get rid of nested if . Our flatten function checks whether all Optionals have values, and if so, this “large” Optional as a tuple.

 func flatten<A,B,C,D>(oa: A?,ob: B?,oc: C?,od: D?) -> (A,B,C,D)? { if let a = oa { if let b = ob { if let c = oc { if let d = od { return (a,b,c,d) } } } } return nil } 

Fourth attempt

So, we calculate our 4 variables, “align” them with the help of the flatten function flatten and if they are all non- nil , return the Blog .

 func parseBlog(blogData: [String:AnyObject]) -> Blog? { let id = int(blogData,"id") let name = string(blogData,"name") let needsPassword = bool(blogData,"needspassword") let url = string(blogData,"url").map { NSURL(string:$0) } if let (id, name, needsPassword, url) = flatten(id, name, needsPassword, url) { return Blog(id: id, name: name, needsPassword: needsPassword, url: url) } return nil } 

We can continue to work on our code, trying to get rid of the last if . This will require the functions A,B,C,D -> R , which converts the arguments A,B,C,D to R , as well as the tuple (A, B, C, D) , and if they are not both nil , then the function is applied to the tuple.

 func apply<A, B, C, D, R>(l: ((A,B,C,D) -> R)?, r: (A,B,C,D)?) -> R? { if let l1 = l { if let r1 = r { return l1(r1) } } return nil } 

Fifth attempt

Now our code looks like this:

 func parseBlog(blogData: [String:AnyObject]) -> Blog? { let id = int(blogData,"id") let name = string(blogData,"name") let needsPassword = bool(blogData,"needspassword") let url = string(blogData,"url").map { NSURL(string:$0) } let makeBlog = { Blog(id: $0, name: $1, needsPassword: $2, url: $3) } return apply(makeBlog, flatten(id, name, needsPassword, url)) } 

We can call the function apply with an argument that is our “aligned” structure. But to continue refactoring the code, you need to make the apply function more generalized, and also to perform currying.

 func apply<A, R>(l: (A -> R)?, r: A?) -> R? { if let l1 = l { if let r1 = r { return l1(r1) } } return nil } 

It may be difficult at first sight to understand currying as a concept. It returns nested functions that can be very useful in functional programming. Swift allows us to omit the parentheses when defining a type for nested functions. By calling the apply function again, we can make the code more compact and finally get our Blog .

 func curry<A,B,C,D,R>(f: (A,B,C,D) -> R) -> A -> B -> C -> D -> R { return { a in { b in { c in { d in f(a,b,c,d) } } } } } //  : (Int, String, Bool, NSURL) -> Blog let blog = { Blog(id: $0, name: $1, needsPassword: $2, url: $3) } //  : Int -> (String -> (Bool -> (NSURL -> Blog))) let makeBlog = curry(blog) // : Int -> String -> Bool -> NSURL -> Blog let makeBlog = curry(blog) // : Int? let id = int(blogData, "id") //  : (String -> Bool -> NSURL -> Blog)? let step1 = apply(makeBlog,id) //  : String? let name = string(blogData,"name") //  : (Bool -> NSURL -> Blog)? let step2 = apply(step1,name) 

Sixth try

Now, after simplifying the apply function and after currying, our code has a lot of calls to the apply function.

 func parse(blogData: [String:AnyObject]) -> Blog? { let id = int(blogData,"id") let name = string(blogData,"name") let needsPassword = bool(blogData,"needspassword") let url = string(blogData,"url").map { NSURL(string:$0) } let makeBlog = curry { Blog(id: $0, name: $1, needsPassword: $2, url: $3) } return apply(apply(apply(apply(makeBlog, id), name), needsPassword), url) } 

We can define one more operator, <*> . This is the same as the apply function.

 infix operator <*> { associativity left precedence 150 } func <*><A, B>(l: (A -> B)?, r: A?) -> B? { if let l1 = l { if let r1 = r { return l1(r1) } } return nil } 

Seventh attempt ... already close to goal

Now our code is almost complete. We replaced a set of calls to the apply function with our <*> operator.

 //    return apply(apply(apply(apply(makeBlog, id), name), needsPassword), url) //  return makeBlog <*> id <*> name <*> needsPassword <*> url } 

Eighth (and last!) Attempt.

All intermediate offers and designs if lets removed. All types are correct, but if we randomly specify other types, the compiler will “complain”. The final version of our code looks like this:

 func parse(blogData: [String:AnyObject]) -> Blog? { let makeBlog = curry { Blog(id: $0, name: $1, needsPassword: $2, url: $3) } return makeBlog <*> int(blogData,"id") <*> string(blogData,"name") <*> bool(blogData,"needspassword") <*> string(blogData,"url").map { NSURL(string:$0) } } 

Questions and answers

Question : Your currying is very limited, is there a way to write a more generalized currying?
Chris : In some programming languages, this is present by default. As far as I know, you cannot write curry by default, but you can write these curry functions with a certain number of arguments, and the compiler will choose one of them for you. Perhaps in the future it will be added to Swift .

Q : Is there any support for tail recursion optimization (tail-call optimization - TCO)?
Chris : I don't think so. When I performed many recursive calls, I had many crashes. But the Swift development team knows these problems and will solve them in the future.

Question : In your slides a lot of custom (custom) operators. Can you say a little about how this affects new developers in the team?
Chris: Awful. But it all depends on the context - if you come from Objective-C, and just start using Swift, I would not recommend doing it. I would also say if you work in a big company. If you have people with functional programming languages, these operators are more familiar to them.

Question : If you come from the world of OOP (object-oriented programming), then the goal is a sensible code. How would you organize your code in functional programming?
Chris : At the topmost level, it's almost the same. At a lower level, I find it useful to use a lot of helper functions. You see a lot of support functions in my code, which makes working with code more convenient. This is a bit like the UNIX philosophy, in which you have smaller functions that can be combined with each other. In the beginning, it is a bit confusing, because you have to rebuild your thoughts.

Question : In your book, you talk about processing collections and such things as the map and reduce functions?
Chris : Of course. When you start to get acquainted with functional programming, the first thing you learn is these functions. You can map everything, even arrays and Optionals , and, of course, you have to master it.

Question : What can you say about Swift in comparison with other programming languages ​​that you used?
Chris : I was on a walking tour of Poland, and was sitting in a mountain hut when I updated Twitter, found out that WWDC was under way. When they submitted Swift, I was in seventh heaven and immediately downloaded the eBook. Now we can do all these really cool functional things, but if we consider Swift as a functional programming language, then there really is not a lot of possibilities. But what I really love about Swift is that you can use functional programming, and at the same time have access to everything Cocoa does. It is very difficult for most programming languages ​​like Haskell to interact with Cocoa, and this is a super powerful combination.

Question : Are any efforts being made to create open for functional operators and functions, like the Scala Z library for Scala?
Chris : Yes, it's called Swift Z.

Question : I noticed that there is no declaration of var variables in your presentation, could you comment on this?
Chris : For me, functional programming is basically immutability, that is, when you create values ​​and do not modify them. This makes it easier to develop code because you know for sure that your values ​​will not change. Another advantage of this is manifested in parallel computing, because it is very difficult to work with variable objects. But there are some drawbacks - in classical programming languages ​​it is hard to write “quick sort” (the so-called quicksort) in one line. But if I use var, I try to isolate it inside a function, and from the outside, the function looks “immutable” (immutable).

Question : Can you explain your considerations when you set the priority (precedence) for the custom operator <*>, but for other setting operators there was no priority?
Chris : I was looking at the priority of operators in Haskell, and was thinking about how to transfer this to Swift to improve its performance. I also looked at the priorities for normal Swift operators and also had it in mind when setting the priorities of the operators.

Question : Do you think these decisions are scaled, given the learning curves of some organizations?
Chris : I would say that you should work with the best possible solutions. It is not either / or, you can take some functional programming features and then slowly begin to embed them in your programming style.

Question : Have you noticed some changes in the consumption of "memory" or other landmarks when using functional programming?
Chris : I think that if you use “mutable” data, the use of “memory” will be better. With a lot of constants, you use more “memory” and CPU, but you can win a lot in a different way. Your code may be faster and you can optimize execution in another way. For example, when used maptwice for an array. If thispuretransformations, then you can combine the two mapinto one mapand then iterate over the array once. This will be very hard to write optimally in programming languages ​​like C. Clarity is a huge gain, and, besides, I have never experienced performance problems.

Q : One of the big benefits of functional programming is laziness, is there a way to do this in Swift?
Chris : Yes, there is the keyword "lazy", which can make some thing "lazy", but I don't know exactly all the details of that. You can also write generators (sequences) and sequences (sequences), although there is little documentation on this. I don’t know exactly how these things work in Swift .

PS As for currying, in Swift, although manually, you can make a curried function for creating a Blog structure without writing curry functions, but by placing each parameter in a makeBlog wrapper in a separate parenthesis:

 static func makeBlog(id: Int)(name: String)(needsPassword: Int)(url:String) -> Blog { return Blog(id: id, name: name, needsPassword: Bool(needsPassword), url: toURL(url)) } 

The code for that part of the speech that concerns JSON parsing can be found on GitHub .

Afterword translator.

Chris sticks to the idea that functional programming in Swift is better to learn in small pieces of code that does useful work, and therefore in its journal objc.io publishes such small functional sketches .
But if it seems to you to be bland and too simple, that is, functional developments in Swift , from which they really “blow the roof off”, that is, a kind of “functional extreme” . But this may be the subject of the following articles.