The following is a blog post written for PureScript, but should be able to work with Haskell with only very few modifications.

The Tagless Final encoding has gained some steam recently, with some people hailing 2017 as the year of Tagless Final. Being conceptually similar to the Free Monad, different comparisons have been brought up and the one trade-off that always comes up is the lack or the difficulty of inspection of tagless final programs and in fact, I couldn’t find a single example on the web. This seems to make sense, as programs in the tagless final encoding aren’t values, like programs expressed in terms of free structures. However, in this blog post, I’d like to dispell the myth that inspecting and optimizing tagless final programs is more difficult than using Free.

To start with, this blog post is gonna use a different tagless final encoding not based on type classes, but records instead. This allows us to treat interpreters as values. This technique is described here.

Without further ado, let’s get into it, starting with our example algebra, a very simple key-value store:

newtype KVStore f = KVStore 
  { put :: String -> String -> f Unit
  , get :: String -> f (Maybe String)
  }

To get the easiest example out of the way, here’s how to achieve parallelism in a tagless final program:

program :: forall f m. Parallel m f => KVStore f -> f (Maybe String)
program (KVStore k) = do
  k.put "A" a
  x <- (<>) <$> k.get "B" `parApply` k.get "C"
  k.put "X" (fromMaybe "-" x)
  pure x

This programs makes use of the Parallel type class, that allows us to make use of the parApply combinator to use independent computations with a related Applicative type. This is already much simpler than doing the same thing with Free and FreeApplicative. For more info on Parallel check out the docs here.

However this is kind of like cheating, we’re not really inspecting the structure of our program at all, so let’s look at an example where we actually have access to the structure to do optimizations with.

Let’s say we have the following program:

program :: forall f. Apply f => KVStore f -> f (List String)
program mouse (KVStore k) = (\f s _ t -> catMaybes (f : s : t : Nil)) <$>
  k.get "Cats" <*> k.get "Dogs" <*> k.put "Mice" "42" <*> k.get "Cats"

Not a very exciting program, but it has some definite optimization potential. Right now, if our KVStore implementation is an asynchronous one with a network boundary, our program will make 4 network requests sequentially if interpreted with the standard Apply instance of something like Aff. We also have a duplicate request with the "Cats"-key.

So let’s look at what we could potentially do about this. The first thing we should do, is extract the static information. The easiest way to do so, is to interpret it into something we can use using a Monoid. This is essentially equivalent to the analyze function commonly found on FreeApplicative.

Getting this done, is actually quite simple, as we can use Const as our Applicative data type, whenever the lefthand side of Const is a Monoid. I.e. if m has a Monoid instance, Const m a has an Applicative instance. You can read more about Const here.

import Prelude
import Data.StrMap as M
import Data.Set as S
import Data.Const

analysisInterpreter :: KVStore (Const (Tuple (S.Set String) (M.StrMap String)))
analysisInterpreter = KVStore
  { put : \key value -> Const $ tuple2 S.empty (M.singleton key value)
  , get : \key -> Const $ tuple2 (S.singleton key) M.empty
  }

(Const (program analysisInterpreter))

By using a Tuple of Set and Map as our Monoid, we now get all the unique keys for our get and put operations. Next, we can use this information to recreate our program in an optimized way.

optimizedProgram :: forall f. Apply f => KVStore f -> f (List String)
optimizedProgram (KVStore k) = 
  let (Const (Tuple gets puts)) = program analysisInterpreter
  in traverse (\(Tuple k v) -> k.put k v) (fromFoldable puts) *> traverse k.get (fromFoldable gets)

And we got our first very simple optimization. It’s not much, but we can imagine the power of this technique. For example, if we were using something like GraphQL, we could sum all of our get requests into one large request, so only one network roundtrip is made. We could imagine similar things for other use cases, e.g. if we’re querying a bunch of team members that all belong to the same team, it might make sense to just make one request to all the team’s members instead of requesting them all individually.

Other more complex optimizations could involve writing a new interpreter with the information we gained from our static analysis. One could also precompute some of the computations and then create a new interpreter with those computations in mind.

Embedding our Applicative program inside a larger monadic program is also trivial:

program :: forall f. Apply f => String -> KVStore f -> f (List String)
program mouse (KVStore k) = (\f s _ t -> catMaybes (f : s : t)) <$>
  k.get "Cats" <*> k.get "Dogs" <*> k.put "Mice" mouse <*> k.get "Cats"

optimizedProgram :: forall f. Apply f => String -> KVStore f -> f (List String)
optimizedProgram mouse (KVStore k) = 
  let (Const (Tuple gets puts)) = program mouse analysisInterpreter
  in traverse (\(Tuple k v) -> k.put k v) (fromFoldable puts) *> traverse k.get (fromFoldable gets)

monadicProgram :: forall f. Bind f => KVStore f -> f Unit
monadicProgram (KVStore k) = do
  mouse <- k.get "Mice"
  list <- optimizedProgram (fromMaybe "64" mouse) k
  k.put "Birds" (fromMaybe "128" (head list))

Here we refactor our optimizedProgram to take an extra parameter mouse. Then in our larger monadicProgram, we perform a get operation and then apply its result to optimizedProgram.

So now we have a way to optimize our one specific program, next we should see if we can introduce some abstraction.

First we’ll have to look at the shape of a generic program, they usually are functions from an interpreter algebra f to an expression inside the type constructor f, such as f a.

type Program alg a = forall f. Applicative f => alg f -> f a

The program is only defined by the algebra and the resulting a, so it should work for all type constructors f.

optimize :: forall alg f a m. Applicative f
         => Monoid m 
         => Program alg a
         -> alg (Const m)
         -> m -> f a
         -> alg f
         -> f a
optimize program extract restructure =
  let (Const m) = program extract
  in restructure m

Now we should be able to express our original optimization with this new generic approach:

optimizedProgram :: forall f. Apply f => String -> KVStore f -> f (List String)
optimizedProgram mouse (KVStore k) =
  optimize program analysisInterpreter (\(Tuple gets puts) -> 
  traverse (\(Tuple k v) -> k.put k v) (fromFoldable puts) *> traverse k.get (fromFoldable gets))

So far so good, we’ve managed to write a function to generically optimize tagless final programs. However, one of the main advantages of tagless final is that implementation and logic should be separate concerns. With what we have right now, we’re violating the separation, by mixing the optimization part with the program logic part. Our optimization should be handled by the interpreter, just as the sequencing of individual steps of a monadic program is the job of the target Monad instance.

One way to go forward, is to create a typeclass that requires certain algebras to be optimizable. This typeclass could be written using the generic function we wrote before, so let’s see what we can come up with:

type OptimizerReqs alg f m =
  { extract :: alg (Const m)
  , rebuild :: m -> alg f -> f (alg f)
  }

class (Monad f, Monoid m) <= Optimizer alg f m | alg -> f , f -> m where
  reqs :: OptimizerReqs alg f m

optimize :: forall alg f m a. Optimizer alg f m
         => Program alg a
         -> alg f
         -> f a
optimize prog interpreter =
  let (Const m2) = prog (reqs :: OptimizerReqs alg f m).extract
  in (reqs.rebuild m2 interpreter) >>= prog

This might look a bit daunting at first, but we’ll go through it bit by bit. First we define our type class Optimizer parameterized by an algebra alg :: (* -> *) -> * and a type constructor f :: * -> *. This means we can define different optimizations for different algebras and different target types. For example, we might want a different optimization for a production Optimizer KVStore (EitherT Task e) m and a testing Optimizer KVStore Identity m. Next, for our interpreter we need a Monoid m for our static analysis, so we parametrize the Optimizer with an extra parameter m.

The next two functions should seem familiar, the extract function defines an interpreter to get an m out of our program. The rebuild function takes that value of m and the interpreter and produces an f alg f, which can be understood as an f of an interpreter. This means that we can statically analyze a program and then use the result of that to create a new optimized interpreter and this is exactly what the optimize function does. This is also why we needed the Monad constraint on f, we could also get away with returning just a new interpreter alg f from the rebuild method and get away with an Applicative constraint, but we can do more different things this way.

Let’s see what our program would look like with this new functionality:

monadicProgram :: forall f m. Optimizer KVStore f m => KVStore f -> f Unit
monadicProgram (KVStore k) = do
  mouse <- k.get "Mice"
  list <- optimize (program $ fromMaybe "64" mouse) (KVStore k)
  k.put "Birds" (fromMaybe "128" (head list))

Looking good so far, now all we need to run this is an actual instance of Optimizer. We’ll use the standard Aff for this and for simplicity our new optimization will only look at the get operations:

extract :: KVStore (Const (S.Set String))
extract = KVStore 
  { get : \key -> Const $ S.singleton key
  , put : \_ _ -> Const $ S.empty
  }

rebuild :: forall e. S.Set String -> KVStore (Aff e) -> Aff e (KVStore (Aff e))
rebuild gs (KVStore interp) = 
  precomputed <#> (\m -> KVStore $ interp
        { get = \key -> case (M.lookup key m) of
            Just a -> pure $ Just a
            Nothing -> interp.get key
        })
  where 
    tupleList :: Aff e (List (Maybe (Tuple String String)))
    tupleList =
          parTraverse (\key -> interp.get key <#> (\m -> m <#> \s -> key /\ s)) (fromFoldable gs)
    precomputed :: Aff e (M.Map String String)
    precomputed = tupleList <#> (M.fromFoldable <<< catMaybes)


instance kvStoreAffOptimizer :: Optimizer KVStore (Aff e) (S.Set String) where
  reqs = { extract , rebuild }

Our Monoid type is just a simple Set String here, as the extract function will only extract the get operations inside the Set. Then with the rebuild we build up our new interpreter. First we want to precompute all the values of the program. To do so, we just run all the operations in parallel and put them into a Map, while discarding values where the get operation returned Nothing. Now when we have that precomputed Map, we’ll create a new interpreter with it, that will check if the key given to get operation is in the precomputed Map instead of performing an actual request. We can then lift the value into a Aff e (Maybe String). For all the put operations, we’ll simply run the interpreter.

Now we should have a great optimizer for KVStore programs interpreted into an Aff. Let’s see how we did by interpreting into a silly implementation that only prints whenever you use one of the operations:

testInterpreter :: forall e. KVStore (Aff e)
testInterpreter = KVStore
  { put : \_ value -> do
      liftEff $ unsafeCoerceEff $ log $ "Put something " <> value
      pure unit
  , get : \key -> do
      liftEff $ unsafeCoerceEff $ log $ "Hit network for " <> key
      pure $ Just $ key <> "!"
  }

Now let’s run our program with this interpreter and the optimizations!

launchAff $ monadicProgram testInterpreter
// Hit network for Mice
// Hit network for Cats
// Hit network for Dogs
// Put something: Mice!
// Put something: Cats!

And it works, we’ve now got a principled way to write programs that can then be potentially optimized.

Conclusion

Designing a way to completely separate the problem description from the actual problem solution is fairly difficult. The tagless final encoding allows us one such fairly simple way. Using the technique described in this blog post, we should be able to have even more control over the problem solution by inspecting the structure of our program statically.

Another thing we haven’t covered here, are programs with multiple algebras, which is quite a bit more complex as you can surely imagine, maybe that will be the topic of a follow up blog post.

The code for this blog post can be found here, if people find it useful enough, I’ll publish and document it!

What kind of problems and techniques would you like to see with regards to tagless final? Would love to hear from you in the comments!

Today I’d like us to build our own Reactive Mobile Framework. A Reactive UI Framework should allow us to build apps declaratively by manipulating User Event Streams.

Now we’re not going to write such a Framework from scratch, but we’d like to use an existing Framework and create some Bindings, so that we can use it reactively. Examples for these types of wrappers are RxCocoa for the Cocoa and Cocoa Touch Frameworks, RxBinding for Android or RxSwing for the Java Swing toolkit.

First we have to choose the UI Framework we’re going to work with. I’ve spent a lot of time working with mobile Reactive Frameworks, so for today, I’d like to create some Bindings for the Xamarin.Forms toolkit. Xamarin.Forms is a cross-platform UI Framework that lets you create native UIs for both Android and iOS, by leveraging the .NET Framework. We’re going to write our code in F#, since it just supports the functional paradigm a lot better.

Now without further ado let’s identify what exactly it takes to create such a Wrapper.

Firstly, we’ll need to have a way to create an event stream from user interactions, for example, we should be able to create an event stream from a toggle or checkbox, that emits boolean values. We’ll call these interactions event sources, some frameworks like RxBinding will only support bindings for event sources.

Next, we will need a way to take event streams and bind them to a View. An easy example is a function that takes a stream of Strings and binds them to a Label. We’ll call these event sinks, since that’s where our streams will go into.

So one of the easiest programs we can imagine with this kind of setup is a Switch that emits boolean values that then get mapped to some kind of text which finally gets bound to a Label. I made a small diagram to illustrate what’s happening:

SimpleMarbles

Alright, now let’s get codin’! The first thing we’re gonna do is create the source function for the Switch. The function will accept a Switch and return an Observable<bool>. Creating new Observables is fairly straight forward. Let’s look at a small example:

Observable.Create(fun (o: IObserver<int>) ->
o.OnNext(1)
o.OnNext(2)
o.OnError("Damn")
o.OnNext(4)
o.OnCompleted
)

We use the Observable.Create function and call the OnNext, OnError and OnCompleted functions to emit values and errors.

Now that we know how to create Observables, let’s finally create one for the Switch:

module RxForms =
let fromSwitch (s: Switch) = Observable.Create(fun (o: IObserver<bool>) ->
s.Toggled.Subscribe(fun t -> o.OnNext(t.Value)))

Here we again create an Observable that emits the value of the Switch everytime it’s toggled. We don’t need to call OnError or OnCompleted, since the Switch won’t error out or stop emitting. Yay! We created our first source binding! We placed in a module called RxForms, where we’ll place all of our binding functions from now on.

Okay, so let’s continue by defining a sink. We’ll call our function bindLabel and it’ll take an Observable<string> and a Label and it’ll return a Subscription.

let bindEntry (l: Label) (o: IObservable<string>) =
o |> Observable.subscribe(fun s -> l.Text <- s)

Now that we’ve created functions to extract sources and bind to sinks, we have a basis on which we could expand and wrap around all of the Xamarin.Forms widgets. So go! No time to lose, the Api has dozens of Views to wrap, but first let’s see if our cute little program actually works. Here’s the code:

type App() =
inherit Application()

let stack =
StackLayout(VerticalOptions = LayoutOptions.Center)
let switch = Switch()
let label = Label()

let switchEvents =
RxForms.fromSwitch switch |> Observable.map (fun b -> if b then "On" else "Off")

let subscription =
switchEvents |> RxForms.bindLabel label

do stack.Children.Add(switch)
do stack.Children.Add(label)
do base.MainPage <- ContentPage(Content = stack)

We’re using the simplest layout With a StackLayout and then create both a Switch and a Label and then use our functions to wire everything up. Here’s how this would look on iOS:

SwitchGif

Notice, though, that we currently have to handle the subscription manually. If we fleshed out our Framework, we could create a mechanism, that unsubscribes automatically, whenever the bound view get’s destroyed (This is what RxCocoa’s DisposeBag does, maybe we’ll implement this in another article).

I could probably end this article here, but let’s look at a few more examples. First, some easy stuff:

let fromButton (b: Button) = Observable.Create(fun (o: IObserver<unit>) -> 
b.Clicked.Subscribe(fun _ -> o.OnNext( () )))

let bindEntry (e: Entry) (o: IObservable<string>) =
o |> Observable.subscribe(fun s -> e.Text <- s)

let bindListView (list: ListView) (o: IObservable<List<_>>) =
o |> Observable.subscribe(fun ts -> list.ItemsSource <- ts)

With these, we can easily use Buttons, ListViews and Entrys (Entrys are simple Textfields). So let’s use these new widgets to create the most over used example app: The Todo app! Yaaaay! The Todo app is great though, because it usually demonstrates how to handle state.

One option for implementing such an app would be to add both a Button and an Entry and combine them, but Entry also offers a Event that emits once the user ends input. Let’s add a function to extract such a source:

let fromEntryCompleted (e: Entry) = Observable.Create(fun (o: IObserver<_>) -> 
e.Completed.Subscribe(fun s -> o.OnNext(e.Text)))

We’ll start by adding both an Entry and a ListView and extracting an Observable<string> from the Entry:

type App() =
inherit Application()

let stack =
StackLayout(Padding = Thickness(0.0, 40.0, 0.0, 0.0))
let editText =
Entry(Placeholder = "What needs to be done?", Margin = Thickness(10.0, 0.0))
let listView =
ListView(Margin = Thickness(10.0, 0.0))

let submittedTodos =
RxForms.fromEntryCompleted editText

Now what we’d like to accumulate these todos into a list of todos, a List<string>. To do that, we’ll use the scan operator, which is like a reducer, but emits all the intermediary values. Once again, I made a diagram to explain this (a picture speak a thousand words).

ScanMarbles

So every time our Entry completes, we add a new item to our list. This is how that looks in code:

let todoLists = 
Observable.scan (fun acc cur -> acc |> List.append [cur]) [] submittedTodos

let subscription =
todoLists |> RxForms.bindListView listView

And with that, we’re done right? Well not quite, since now every time we submit a Todo, our Entry doesn’t clear, which kinda sucks. So we need to write another binding for Entrys. However, I’m going to leave that as an exercise for you, dear reader! Instead, here’s a gif on how it should look in the end (I’ll upload the final code, just in case you get stuck).

TodoGif

Conclusion

So that’s it for now, I hope, that with your help, we can bring Reactive Programming to more and more UI Frameworks. Me, personally, I’d really like to see a full fledged Library made out of what we started in this article. In case you have any questions, I’d love to hear them, so just post them in the comments down below. The full code of this article can be found here. Happy Coding everyone!

What makes a language functional? Well, that’s a good question! Some people say that lambdas make a language a functional language. Others say it’s the ability to bind functions to variables. But that in itself isn’t really all it takes right? After all, we could do this with function pointers in C! And I don’t think many would claim C is a functional language, right?

In this article I’ll try to go over some specific features that I personally think make or break a functional programming language. Now pay in mind, that a lot of this is going to be fairly subjective, but I’d love to hear your thoughts in the comments!

So without further ado here’s what we will take a look at throughout this article (in order of most to last important to functional programming):

  • First Class Functions
  • Immutability
  • Recursion
  • Expression-Oriented Programming
  • Currying
  • Lazy Evaluation
  • Algebraic Data Types
  • Other topics (Higher Kinded Types, Existential Types)

First class functions

Most languages support this nowadays, Java 8 brought First Class functions to the language and C++ also included them in C++11. Having functions be first class basically only really means that you can use them the same way you would use any other value, like being able to bind functions to variables and pass them around your application.

Now there have been a lot of different names for what is basically just a couple of concepts, so we’ll try and go through them shortly.

Anonymous Functions AKA Lambda Expressions

Lambdas and anonymous functions are essentially the same thing, it’s just a function that doesn’t have a binding to an identifier. So they’re just easy ways for creating functions, in the same sense that some languages allow literals for Arrays or dictionaries. Anonymous functions originate in Alonzo Church’s Lambda Calculus, hence the name. Here’s an example in python: With that we’ve defined a variable holding a function that will square a given number when applied. Pretty straight forward!

Lexical Closures

Now closures are often confused with lambdas and it’s not difficult to understand why. All closures are anonymous functions, but it doesn’t work vice versa. Closures are special functions, that close over the environment where it was created, meaning it can gain access to values not in its parameter list. Very similar to how methods can access instance variables. You’ve probably already heard of the saying “Closures are the poor man’s objects”. Let’s take a look at an example in Kotlin: In this snippet we can see that the function passed to forEach gets access to the sum variable and can even modify it. So closures and lambdas go hand in hand, then what’s the deal with Higher order functions?

Higher Order Functions

Most of you have probably already used Higher Order Functions. HOFs are just functions that take another function as a parameter. So any function that takes a callback function could be considered a HOF. Other very notable example include functions like map, filter reduce. Here’s an example for a filter-function in Swift: Here predicate is a function that takes a parameter of type T and returns a Bool depending on if the element matches the predicate or not. You’ll find many of these HOFs in most functional languages and it’s almost an absolut must for doing any kind of functional programming.

Immutability

Immutability plays a big part in FP, a small subset of functional languages are so called “pure” functional languages. Purity means, that absolutely everything is immutable. Examples for this are Haskell, Elm and (as the name suggests) PureScript.

So on the one side we’ve got languages where everything is immutable, but on the other side we also have languages where immutability is unavailable. JavaScript has often been touted as a functional language, butit didn’t have any way to make variables immutable until ES6 and even then it’s only limited to local variables and there’s still no way to declare instance variables to be immutable (unless you’re using Object.freeze). Other languages where immutability is also lacking are Python and Ruby.

Now this is not the only metric for how much a given language supports immutability. Another is of course, how much the language encourages you to write immutable code. In Java and C# for example you need to add an extra keyword to make a value immutable (C# also doesn’t allow Type Inference on immutable values).

Put this in contrast to Rust:

It’s quite clear which programming language wants to encourage you to use immutable values. Some compilers (like Rust and Swift) also emit a warning if you use a mutable variable, but don’t mutate it.

Lots of functional languages also offer a way to copy an Object or Record, but with one or multiple values modified. This makes creating a new value almost exactly as easy as modifying the original. Here’s an example of what that might look like in Elm:

Another thing to consider is something traditionally called “const correctness”, which means that you can’t mutate parts of a value if it’s declared immutable. For example this is legal in Java: Where as the equivalent would throw a compiler error in C++.

Now the last thing to consider is whether or not your language supports performant immutable data structures. Languages like Kotlin and Swift support simple readonly data structures, that are the same as their mutual counterpart, but not being able to modify it.

Other more functional languages offer us special collections that are optimized for immutability. These immutable data structures have operators that can modify and return a copy of the original. Most of the time, however we don’t even need to copy most of the collection and can instead reuse it, because we don’t need to worry about subsequent code making changes to our data. So there’s no need to defensively copy the whole structure, saving both memory and time! This is called data sharing and is a huge benefit of immutable data structures.

The coolest collections come from the late Scala community leader Phil Bagwell (R.I.P.), essentially they offer amortized O(1) lookups, insertions and deletions on Vectors and HashMaps. You can find these data structures in Clojures and Scalas standard library as well as in libraries such as Immutable.js. There’s a lot of super interesting stuff to talk about, so if you’re interested check out this great series on how these data structures actually work.

Recursion

Most if not all of modern programming languages support the notion of recursion However it plays a much bigger part in functional programming than in imperative programming. That is because when programming in a functional way, iterating over data structure recursively is not just much more elegant, but also the only way to iterate without invoking side-effects.

In order for this to be efficient, most functional languages offer an optimization technique called “Tail Call Optimization”. With this technique it’s possible for recursive functions to not increase the size of the call stack. In other words: the compiler more or less replaces the original function with the equivalent of an imperative loop.

Going into too much detail here would break the scope of the article, so here’s the gist of it: if the last thing you do (i.e. the “tail” position) in a function is a recursive call to itself, the compiler can optimize this to act like iteration instead of recursion.

So if you want to do functional programming in your language without having to worry about stack overflows, your language should probably provide some form of TCO.

Some languages make writing tail recursive functions a lot easier by giving you a way to mark them as such. For example Scala supports a way explicitly annotate a function as tail recursive and let the compiler throw an error when it isn’t.

This guarantees that an error is issued whenever tail call optimization cannot be performed by the compiler.

Expression-Oriented Programming

To understand Expression-Oriented programming we first need to define the difference between expressions and statements. This is best explained by contrasting return types of different functions. For example a void type means the method is probably a statement, since it doesn’t a result. Everything else is an expression and yields a value when computed. Typically the former looks something like list.sort() while expressions look like sorted = sort(list).

To put it simply, in Expression-Oriented programming languages everything is an expression! Which means that everything has a return value. This is something we aspire to because statements always have side effects and should be avoided as much as possible in functional programming.

Rust, Ruby, Kotlin and more functional languages like Scala, Elm, Haskell or F# all use this paradigm. This means that for example the if-construct always returns a result:

Another neat example are Scala’s “for-expressions” which involve some syntactical sugar that looks very similar to for-loops found in imperative languages.

Currying

Currying is when you break down a function that takes multiple parameters into a series of functions each taking a parameter and returning a new function. A simple example would be this:

I’ve written in depth about the workings and advantages of Currying and the most often confused technique of partial application in an earlier article. Both Currying and partial application are very useful tools in the functional programming world and most functional languages make it very easy to do so. For example in Haskell or one of the different ML-derived languages, it’s mostly impossible to even write an uncurried version of functions. Functions are just curried by default! Here’s some Haskell code: The type signature of the add function is Integer -> Integer -> Integer, meaning it takes an Int and returns a function that takes an Int and returns an Int. This allows us to just pass one argument to the add function and get another generic function that adds the passed argument. Different languages handle this differently, but it’s a pretty important tool in the functional programmers toolkit!

Scala for example lets you partially apply functions easily by passing an underscore _ as a function parameter. Swift is a rather curious example, because it supported a very way of writing curried functions, but has since deprecated them without any real replacement.

Lazy evaluation

Lazy evaluation is a technique to defer the computation of expressions to when they are really needed. This is in contrast to eager evaluation, where every expression is evaluated immediately. Lazy evaluation can be very beneficial when programming in a functional way. Let’s look at an example of eager evaluation in JavaScript:

In this example each operation returns a new copy immediately once called. What we’d like to do is use higher-order functions like map and filter instead of manually fusing passes, but without having to create intermediate data structures and having to iterate the structure multiple times. This can be solved quite handily using lazy evaluation.

So now let’s have a look at equivalent code using lazy evaluation: Wait a minute… it’s the same basic code! Well yeah it is, the truly interesting stuff is happening behind the scenes, but this code can demonstrate a few things.

Firstly, we no longer create intermediate copys of the list, in fact nothing even gets computed untill we access the first element by calling the head method. Secondly, since we’re only accessing the first element of the list, all the operations are only applied once and we can save a lot of execution time. We do not need to evaluate the whole list, when all we want to do is print out the first element.

In Haskell lazy evaluation is the default, but in most other functional languages it’s opt in. Examples for these are the various Lisps, Scala and F#.

Algebraic Data Types

Algebraic data types? Aw man, what’s this fancy maths stuff? I just want to program cool stuff! Alright! I won’t go into too much detail here, so bear with me for a moment! Okay, so most functional languages allow you to define simple data types. These ADTs are simple data cointainers that can be defined recursively. They can be easily constructed and deconstructed and usually come with built in structural equality checking.

All of this allows us to utilize a technique called “Pattern matching”. Pattern matching is a kind of switch-case on steroids, it can do type-testing, it can check exhaustiveness and it can destructure it’s arguments. Let’s have a look at an example written in Scala:

This is just a rather simple example, but I’m sure you can imagine how powerful the match expression can be. An ADT can be anything by the way, from Tuples to Lists, to Records. So Pattern matching is extremely useful because we can decompose any kind of data structure by its shape instead of its contents.

With pattern matching navigating and decomposing data structures becomes very convenient, with a compact syntax.

Other advanced features

There’s two other things I’d like to atleast give a mention, they’re both fairly complex and probably warrant a whole article just to get a good understanding. Furthermore they’re both features of a type system, which might be interesting in staticly typed languages, but no so much for dynamic ones.

Higher kinded Types

The first feature is the ability to create “Higher Kinded Types”, which can be seen as providing a way to is the ability to generically abstract over things that take type parameters Here’s an example with a Functor in Scala: Here F[_] could be anything that takes a generic parameter, so Option[T] or List[T] would both be fine.

Existential Types

The other feature is called “Existential Types” can be used for several different purposes, but what they do is to ‘hide’ a type parameter for outside use. Sometimes you don’t care about the actual type but only that it exists. Existential types can make this a reality without making the type parameter covariant.

Conclusion

Now I’d like to conclude without telling you which language is a functional language or which one isn’t. The line is probably more blurred than not and it’s impossible to find some objective criteria for a functional language. We could argue for ages about what or what doesn’t constitute one and how we should weigh these features on a scale from 1 to 100, instead I think we’ve got a fair overview of features functional programmers use everyday.

My hope is that after reading this article, you understand that lambdas aren’t the only criteria and what else might play a role in programming in a functional way. Yes we can do functional programming in almost any language, but in most that would be more cumbersome than we’d like and we should probably strive to use the right tool for the right job. Once you try out a language that has a lot of these “functional” features, you’ll probably find programming with pure functions a lot more pleasant. And I hope you guys can also enjoy functional programming more once you’ve got a hold on some of these cool features.

Asynchronous Programming is hard. Especially without the right tools. In one of my previous posts, I talked about how to make asynchronous programming more bearable using RxJS. Today we’re going to look at another implementation of the ReactiveX Api, RxSwift.

I’m not going to go into much detail on the basics of FRP, so if you don’t know what Reactive Programming is all about, I suggest you check out my previous posts or this great article about the fundamentals of RxSwift.

In its most basic way Functional Reactive Programming is about using event streams as your data and composing them via functions. In FRP, everything is a stream of events. We can then observe these streams and react accordingly. Swift already has a feature called Property Observers which go in a similar direction, but are much less powerful than RxSwift.

The actual term “Functional Reactive Programming” was originally coined in the 90s and it’s disputed whether the ReactiveX Api’s really are formulations of FRP. But I personally like to think of FRP as a programming style streching across different formulations (Elm creator Evan Czaplicki made a great video about this).

RxCocoa

RxCocoa is to Cocoa what RxSwift is to Swift. RxSwift provides the fundamentals of Observables and RxCocoa provides extensions to the Cocoa and Cocoa Touch frameworks to take advantage of RxSwift.

Now without further ado, let’s start building our first iOS application utlizing our reactive approach. For that you’ll need to install RxSwift and RxCocoa, so add them to your Pod- or Cartfile, depending on which you use.

Once that’s done we can begin for real. We’re going to create an application where we can save and review different movies on a scale from 0.0 to 10.0.

For starters, we’ll create a TableView and a corresponding TableViewCell in our Interface Builder. In our cell, we’d like to display the Title and the score, so we’ll add to UILabels to it. Then let’s also add an “Add” Button in our Navigation Bar, to dynamically add new Movies to our Table.

So far so good, next we’ll start writing some code for our model and our Cell. Our model is very simple right now and should only contain data for our title and our rating. Here’s how it should look:

class Movie {
let title: Variable<String>
let rating: Variable<Float>

init(){
title = Variable("")
rating = Variable(Float(5.0))
}

init(title: Variable<String>, rating: Variable<Float>){
self.title = title
self.rating = rating
}
}

Notice, we define our title and rating as type Variable. If you know other flavors of Rx you can think of them as BehaviourSubjects. Basically it emits the most recent item it has observed immediatly to each subscriber. This allows us to push data to a Variable, but also allow subscribing to it, this will be useful later on.

Next up is our movie table cell:

class MovieTableViewCell: UITableViewCell {

@IBOutlet weak var ratingLabel: UILabel!
@IBOutlet weak var titleLabel: UILabel!

var movie: Movie?
}

Really nothing special going on here at all. We’ve connected our two Labels to our Class via the @IBOutlet Annotation.

Now it’s time for the real meat of the application, our TableView. Because it’s quite a lot to handle, I’ve segmented the code into several smaller pieces:

class MovieTableController: UIViewController {

@IBOutlet weak var movieTable: UITableView!

@IBOutlet weak var addButton: UIBarButtonItem!

let disposeBag = DisposeBag()

let initialMovies: [Movie] = [
Movie(title: Variable("Die Hard"), rating: Variable(Float(10.0))),
Movie(title: Variable("Twilight"), rating: Variable(Float(1.0)))
]

func initState(addButton: UIBarButtonItem) -> Observable<[Movie]> {

let add = addButton.rx_tap
.map{_ in Movie()}
.scan(initialMovies, accumulator: { (acc,cur) in
var copy = acc
copy.append(cur)
return copy
})

return add.startWith(initialMovies)
}

func setupCell(row: Int, element: Movie, cell: MovieTableViewCell){
cell.movie = element

element.title.asObservable()
.bindTo(cell.titleLabel.rx_text)
.addDisposableTo(self.disposeBag)

element.rating.asObservable()
.map{String($0)}
.bindTo(cell.ratingLabel.rx_text)
.addDisposableTo(self.disposeBag)
}


Now this certainly looks like a lot, but it’s actually kind of simple. At first we set up our DisposeBag. This is needed, because the Swift runtime doesn’t have Garbage Collection, but relies on Automatic Reference Counting. To avoid memory leaks, we’ll have to put our Subscriptions into a DisposeBag.

In our initState function we retrieve a Stream of button pressed from our addButton, map each press, to create a new Movie, then use the scan operator to add the new movie to our array and finally tell it to start with our initial movies. Sadly Swift doesn’t support immutable appends, so we have to do it the verbose way of copying, appending and returning the copy.

In our setupCell method we configure our two labels, by binding our Observables to the rx_text field of the labels. In the case of the Rating we first have to transform our Float values to Strings.

Now for the next part:

   
override func viewDidLoad() {
super.viewDidLoad()

let movies = initState(addButton)

movies.bindTo(movieTable.rx_itemsWithCellIdentifier("movieCell", cellType: MovieTableViewCell.self)) (configureCell: setupCell)
.addDisposableTo(disposeBag)

}

}

In this snippet, we bind the Observable of Movie-Arrays to our TableView using the rx_itemsWithCellIdentifer method. This returns a partially applied function, where we can pass the setup code we defined earlier for each individual cell.

Now the basics of our app should run. However, we now always add an empty Movie which we can’t edit at all. That’s rather unfortunate so let’s change that by adding a detail view where we can edit and add new Movies.

For that let’s start by creating a ViewController in the Interface Builder with a TextField for our movie title, a Slider for our review score and a Label to display the score in text. Next we’ll define a segue from our TableController to our DetailController.

Then we’ll need to define when to actually perform the segue. In our TableView add the following code to the end of viewDidLoad:

movies.skip(1).subscribeNext { arr in
self.performSegueWithIdentifier("editMovie", sender: self.movieTable.visibleCells.last)
}.addDisposableTo(disposeBag)

movieTable.rx_itemSelected.subscribeNext { index in
self.performSegueWithIdentifier("editMovie", sender: self.movieTable.cellForRowAtIndexPath(index))
}.addDisposableTo(disposeBag)

And then also add this method:

override func prepareForSegue(segue: UIStoryboardSegue, sender: AnyObject?) {
if let movieController = segue.destinationViewController as? MovieDetailController {
if let movieCell = sender as? MovieTableViewCell{
movieController.movie = movieCell.movie
}
}
}

When performing side effects such as switching views, we need to manually subscribe to our Observables using subscribeNext. We can do this everytime we add to our movies and when we select a specific movie using rx_itemSelected.

In our prepareForSegue method we pass the movie from our cell to our MovieDetailController, which we have yet to define so let’s start right now.

First we create a ViewController in the Interface Builder with a TextField for our movie title, a Slider for our review score and a Label to display the score in text.

Then we create a class for our new controller:

class MovieDetailController: UIViewController {

@IBOutlet weak var titleField: UITextField!
@IBOutlet weak var ratingSlider: UISlider!
@IBOutlet weak var ratingLabel: UILabel!

var movie: Movie?
let disposeBag = DisposeBag()

override func viewDidLoad() {
super.viewDidLoad()

//define our stuff here
}

}

Pretty straightforward. Now let’s define the relationships of our components and our movie. I’m not going to post the full code here since it’s just more of the same and the article is already quite code heavy, but here’s an idea of what to expect:

let rating = ratingSlider.rx_value.map { round(10 * $0)/10}

rating
.bindTo(movie!.rating)
.addDisposableTo(disposeBag)

rating
.map{String($0)}
.bindTo(ratingLabel.rx_text)
.addDisposableTo(disposeBag)

Now after getting up to this point, this shouldn’t look very alien to you anymore. We use the round function to truncate to 1 digit of precision and then bind it to our Movie model and our label’s rx_text.

If you’ve done everything right your app should now look something like this:

RxCocoaApp

And with that we’re done a fully reactive approach to iOS programming. I hope you enjoyed this piece and try it out sometime. If you’re intrigued at all I suggest checking out the RxSwift Repo for more information. You don’t need to commit to it fully, but I feel RxSwift also works really well for just a couple of your Views.

As usual, all code shown here, can also be found in this GitHub repo

In my last post, I tried to show how to do Functional Reactive Programming in Angular 2. Now I’ve heard from some people that it’s too complicated and you shouldn’t ever really do it. I definitely understand that, switching programming paradigms is probably the most difficult change you can make, as it requires you to forget almost everything you already learned.

While showing the benefits of another programming paradigm is quite difficult and always to some extent subjective, showing some real performance benefits is a lot more objective. The real problem with mutable data, is that it can be slow while performing change detection.

Change detection

This problem, of course isn’t exclusive to Angular, but can be applied to e.g. React as well. There are some great resources out there to fully understand how Angular 2’s change detection system really works, but I’ll give it a shot and try to recap the most important points here.

The first problem really is how do you know a change occured? When using mutable data, what you have to do is do a deep equality check, i.e. checking every single property of an object if it’s still the same. If our component tree is very large, this can be very very expensive, because change detection will trigger on every browser event. Starting to sound really ineffecient, right? I did a quick diagram in draw.io to visualize what I’m saying: Tree

When something changes (in red) all components have to be checked.

One solution to this problem would be to make our data immutable, preferably with some framework like Immutable.js. With immutable data, we no longer have to do deep equality checks. This is because the data can never be changed, so if we want to check for changes, we can just do a reference equality check. So now instead of checking every single leaf of our tree, we just need to check the paths where our components aren’t referentially equal. Here’s another diagram, to show you what’s changed: Tree with Immutable data

This time we only have to check those that aren’t referentially equal and don’t have to check their children (in grey).

Also, if you want even more insight check out this video from React Conf about Immutable.js.

Moving on to Observables we can get even better performance! This is because we can simply subscribe to our Observable to get notified when it emits an event immediatly. We no longer have to go through all components from the root, but only the path from the root to our changed component. This is how that looks: Tree with Observables

So what does this mean in real terms?

In Angular 2 for normal use, we can guarantee that the change detection is O(n) where n is the number of components in the tree (which is already much faster than Angular 1 thanks to the Unidirectional data flow). When using Observables, we get essentially O(log(n)) which is awesome!

Now of course this still isn’t “real” data, so I took it upon myself to create a little “benchmark”. I rewrote the app from the last article using ngModel and mutable data to see the differences. So our new template now looks like this:

<div>
<h2>{{ form.name }}</h2>
<form>
<label>Name:</label>
<input type="text" [(ngModel)]="form.name"><br/>

<label>Height (cm):</label>
<input type="number" [(ngModel)]="form.height"><br/>

<label>Weight (kg):</label>
<input type="number" [(ngModel)]="form.weight"><br/>
</form>

<div><strong> Body Mass Index (BMI) = {{ getBmi() }}</strong></div>
<div><strong> Category: {{ getCategory() }}</strong></div>
</div>

I ran both versions with lots and lots of these components and profiled them with Chrome. These are the results:

Using ngModel

Here we’re using ngModel and we can see it takes about 58ms for one change detection cycle. The total aggregated time of change detection throughout the period of testing is 119.15 ms.

Using Observables

Here we’re using Observables and it’s already much quicker. We get 20 ms for this one function and an aggregated result of 46.18 ms. That’s about a 2.5-3x performance increase! Not bad if you ask me.

Conclusion

Of course, most of the time performance is not going to be that big of an issue, but if you have a complex app and you want it to also run on mobile, where cpu cycles are much more valuable, you might want to consider one of these approaches. You don’t even have to commit to one approach fully, but you can mix and match as you please. Check out Victor Savkin’s talk about change detection if you’d like to learn more. Another great resource, is this article by Pascal Precht, where he gives a complete breakdown about change detection in the more general sense. Hope you enjoyed reading this and would love to hear your thoughts!