Functional programming in Swift. Start

Foreword by the translator.

Celebrating the end of 2014, the well-known Swift group SLUG from San Francisco selected the 5 most popular Swift videos for 2014 from its meetings. And among them was a performance by Chris Eidhof "Functional Programming in Swift".
Now Chris Eidhof is a famous personality in the Swift community, he is the author of the recently published book Functional programming in Swift , one of the creators of objc.io magazine , the organizer of the Functional Swift Conference held on December 6 in Brooklyn and the upcoming UIKonf conference .
But I opened it when he, one of the first, published a very simple elegant articleabout the effectiveness of the functional approach in Swift to JSON parsing.
In this article, there are no concepts that are inaccessible to understanding, no mystical mathematical "chimeras" such as "Monad, Functor, Applicative Functor", on which Haskell programmers swear before the rest of the world, rolling their eyes.
There are no such Swift innovations as generics and type inference.
If you want to smoothly “enter” into functional programming in Swift, then you should familiarize yourself with his article “Parsing JSON in Swift” and his presentation at SLUG “Functional Programming in Swift” .

In order to facilitate this task, I will present a translation of the article and that part of Chris Eidhof's speech regarding parsingJSONand which gathered the most questions at this presentation.
By the way, you will definitely come to the study of "Monads, Functors, Applicative Functors" and, apparently, they will make up the functional future of Swift , but this is later, but for now 2 user operators and their ingenious combination give us the necessary result.

So, Chris took an example of JSON data from the posts of skeptical colleagues Brent and David :

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 safe 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, which contain two operators: >> = and <*>. (Translator’s note. In the Github code , the >>> = operator is used instead of the >> = operator, since the >> = operator in Swift is already taken and is used for a beat shift.)
These operators look a bit strange in Swift , but using them full parsing of the JSONstructure becomes very simple.
The rest of the article will be devoted to the description of the library code.
The parsing below works so that if the structure JSONis incorrect (for example, missing nameor idnot an integer), then the result is equal nil.
In our case, neither reflection, norKVO, we just have a couple of simple functions and some ingenious 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 walk through the most important features.
Let's look at the function dictionary. This function receives a dictionary input: [String: AnyObject]and a specific key as an input key: Sting, and tries to find a dictionary in the original dictionary inputby key key, which will be the return Optionalvalue:

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

For example, in the above JSONdata example , we expect that the key "blogs"is a dictionary. If the dictionary exists, then we return it, otherwise we return it nil. We can write similar functions for arrays ( array), strings ( strings) and integers ( int) (the signature is presented here 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 most external structure of our JSONdata. This is a dictionary that is present in the structure under the key "blogs". And under the key "blog"is 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 a Optionalvalue and applies the function to it f only if it is Optionalnot nil. This forces us to use the “alignment” function flatten, which removes (“aligns”) the nested ones Optionaland leaves the only one Optional.

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

Another operator that will be used very intensively is the operator <*> . For parsing 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 this as a function call that becomes executable only if all Optionalvalues ​​are not nil:

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

Let's look at the definition of an operator <*> . It combines two Optionalvalues: 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 applies the function.

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

What is it mkBlog? This curried function (curried function), which "wrap" our initializer.
First, we create a type function (Int, String, Bool, NSURL) -> Blog.
Then the function curryconverts it to a function of the 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 it mkBlogtogether 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 mkBlogand int (dict,"id")using the operator <*>gives us a new type function (String -> Bool -> NSURL -> Blog)?. And if we combine it with the line:

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

We get a type function (Bool -> NSURL -> Blog)?. And if we continue to do this further, we will end with the Optionalvalue Blog?.

I hope you understand how all these pieces stack together. By creating a small number of helper functions and operators, we can make strongly typed parsing JSONreally very simple. Instead Optional, you could also use a different type that includes 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, then you can now access the book Functional Programming in Swift .

Note by the translator.

Code for Chris Eidhof 's article “JSON parsing in Swift” with enhanced Playground printing on Github .
Although Chris said that it’s understandable how this all works together, it’s actually not quite right, and that’s why I bring the translation of his speech to the SLUG meeting , where he shows in detail how to achieve the desired result.

Translation of "Functional Programming in Swift".

This is an excerpt from a presentation by Chris Eidhof at a meeting in San Francisco in which he talked about the possibilities of functional programming in Swift , but not as a replacement for object-oriented programming (OOP), but as an additional tool for application development.
I give a translation of only the part that relates to parsing JSON, 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 using OOP, but now Swift also offers a 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 the conversion of untyped JSONdictionaries into regular, typed dictionaries.
We consider the JSONdata and pose the same task of converting them into an array of blogs [Blog]as in the above article.

First try

The first version of the function parseBlogreturns Blogif the types of all components are correct.
Nested ones ifcontinue to be executed for each key and corresponding type only if the conditions are met.
If all conditions are met, we can construct a value Blogwith the correct types and values ​​from the Optionalsvalues.

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 function stringthat checks if the type matters NSString, because in our case we used it twice. This function takes a dictionary, searches for a key, keyand returns the corresponding value only if a string matches the key. Otherwise returns nil.

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

Second attempt

The second version now includes the function presented above string, 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 related to the fact that for numberswe will create a function similar to a function string. This function searches numberand casts, if it exists. We can create similar functions for types intand bool. For Optionalswe 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 we refactored 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 sentences. Our function flattenchecks if everyone Optionalshas a value, and if so, it creates such a “big” Optionaltuple.

func flatten(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 function, flattenand if all of them are not nil, we return 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 ifsentence. This will require a function A,B,C,D -> Rthat converts the arguments A,B,C,D to R , as well as a tuple (A, B, C, D), and if they are both not nil, then the function is applied to the tuple.

func apply(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 a function applywith an argument, which is our “aligned” structure. But to continue refactoring the code, you need to make the function applymore generalized, as well as perform currying.

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

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

func curry(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 attempt

Now, after simplifying the function applyand after currying, our code has many calls to the function apply.

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 another operator <*>. This is the same as the function apply.

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

Seventh attempt ... already close to the goal

Now our code is almost finished. We have replaced many function calls with applyour operator <*>.

// перед введением оператора
return apply(apply(apply(apply(makeBlog, id), name), needsPassword), url) 
// после
return makeBlog <*> id <*> name <*> needsPassword <*> url }

The eighth (and last!) Attempt.

All intermediate offers and designs if letsremoved. 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 general currying?
Chris : In some programming languages, this is present by default. As far as I know, you cannot write by default curry, but you can write these curryfunctions with a certain number of arguments, and the compiler will choose one of them for you. Perhaps in the future this will be added to Swift .

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

Question : Your slides have a lot of custom operators. Can you tell a little about how this affects new developers on the team?
Chris: Awful. But it all depends on the context - if you came from Objective-C, and just starting to use Swift, I would not recommend doing this. I would also say if you work in a large company. If you have people with functional programming languages, they are more familiar with these operators.

Question : If you come from the world of OOP (Object Oriented Programming), then the goal is reasonable code. How would you organize your code in functional programming?
Chris: At the highest level, it is almost the same. At a lower level, it seems useful to me to use a lot of helper functions. You see a lot of helper functions in my code, which makes working with the 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, this is a bit embarrassing because you have to rearrange your thoughts.

Question : In your book do you talk about processing collections and things like functions mapand reduce?
Chris : Of course. When you first become acquainted with functional programming, the first thing you learn is these functions. You can perform mapeverything, even arrays andOptionals, and of course you have to master it.

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

Question : Are there any efforts to create open for functional operators and functions, like the Scala Z libraryfor Scala?
Chris : Yes, she called Swift the Z .

Question : I noticed that in your presentation there is no declaration of var variables, 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 code development easier 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 mutable objects there. 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 the function, and on the outside the function looks “immutable”.

Question: Can you explain your considerations when you set precedence for the user operator <*>, but for other operators of setting the priority was not?
Chris : I looked at the priority of statements in Haskell, and thought about how to port this to Swift to improve its performance. I also looked at the priorities for normal Swift statements and also had this in mind when setting the priorities of the statements.

Question do You think these solutions are scalable, given the learning curves of some organizations
Chris: I would say that you should work with the best possible solutions. This is not either / or, you can take some functional programming features and then slowly begin to build them into your programming style.

Question : Have you noticed some changes in the consumption of “memory” or other guidelines when using functional programming?
Chris : I think that if you use “mutable” data, using “memory” would be better. With many constants, you use more memory and CPU, but you can win a lot in another way. Your code can be faster and you can optimize execution in a different way. For example, when used map twice for an array. If these are puretransformations, then you can combine twomapinto one mapand then iterate over the array once. This will be very difficult to write optimally in type C programming languages. Clarity is a huge gain, and, moreover, I have never experienced performance problems.

Question : One of the great advantages of functional programming is laziness, is there a way to do this in Swift?
Chris : Yes, there is a keyword “lazy” that can do some thing “lazy”, but I don’t know exactly all the details of this. You can also write generators and sequences, although there is little documentation on this. I don’t know exactly how these things work in Swift .

PS As for currying, then inAlthough it’s manual Swift , you can make a curried function to create a Blog structure without writing curry functions by placing each parameter in the 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 talk about JSON parsing can be found on GitHub .

Afterword of the translator.

Chris adheres to the idea that it is better to master functional programming in Swift in small pieces of code that does useful work, and therefore objc.io publishes such small functional sketches in his journal .
But if it seems fresh and too simple to you, that is, functional developments in Swift that really “blow the roof” away, that is, a kind of “functional extreme” . But this is perhaps the subject of the following articles.