C# – How to we calculate Big-O complexity in Functional & Reactive Programming

Architectureasynchronous-programmingcfunctional programming

I started learning functional programming, I am trying to compare between different algorithms that are written in an imperative, functional , parallel programming and using Collections and Lambda expressions.
In order to make my question clear and avoid sharing long algorithms that I am working on. I will take as an example the well-known modified Fibonacci algorithm (Euler Problem 2):

Here is the problem : http://projecteuler.net/problem=2

//Iterative way: 

int result=2;
int first=1;
int second=2;
int i=2;

while (i < 4000000)
{
    i = first + second;

    if (i % 2 == 0)
    {
       result += i;
    }

    first = second;
    second = i;
 }

 Console.WriteLine(result);

// Recursive functional way: 
FibonacciTerms(1, 2).TakeWhile(x => (x <= 4000000) )
private static int SumEvenFibonarciTerms()
{
    return FibonacciTerms(1, 2)
            .TakeWhile(x => (x <= 4000000)).Where(x => x % 2 == 0)
            .Sum();
}

//Asynchrounous way 
let rec fib x = if x <= 2 then 1 else fib(x-1) + fib(x-2)

let fibs =
    Async.Parallel [ for i in 0..40 -> async { return fib(i) } ]
    |> Async.RunSynchronously

How can I calculate the Big-O in algorithms that are written using Lamda expression (Complexity of functions like: filter, where, reduceleft, reducright, .. )

In the functional and Asynchrounous algo, the both are written in the same way ? Should we consider their complexity the same knowing that there is difference in the time of execution ?

Best Answer

Your programming language paradigm may help you to write code in less line or to express yourself in an easier. It won't change complexity of your program. The questions remaining are the same:

What's the worst case ?
How much "unit" operations are require to perform your algorithm ?

This means that you have to mostly understand how your data structures behave and your code by itself.

Pure Functional vs Functional Style

Consider what you want to gain from this functional refactoring. Do you really want a pure functional implementation, or just some of the benefits a functional programming style can bring, such as referential transparency.

I have found the latter approach, what I call functional style, to mesh well with JavaScript and is usually what I want. It also allows selective non functional concepts to be carefully used in code where they make sense.

Writing code in a more purely functional style is also possible in JavaScript, but is not always the most appropriate solution. And Javascript can never be purely functional.

Functional Style Interfaces

In functional style Javascript, the most important consideration is the boundary between functional and the imperative code. Clearly understanding and defining this boundary is essential.

I organize my code around functional style interfaces. These are collections of logic that behave in a functional style, ranging from individual functions to entire modules. The conceptual separation of interface and implementation is important, a functional style interface may be implemented imperatively, as long as the imperative implementation does not leak across the boundary.

Unfortunately in Javascript, the burden of enforcing functional style interfaces falls entirely on the developer. Also, language features, such as exceptions, make a truly clean separation impossible.

Since you will be refactoring an existing codebase, start by identifying existing logical interfaces in your code that can be cleanly moved to a functional style. A surprising amount of code may already be functional style. Good starting points are small interfaces with few imperative dependencies. Everytime you move over code, existing imperative dependencies are eliminated and more code can be moved over.

Keep iterating, gradually working outwards to push large parts of your project onto the functional side of the boundary, until you are happy with the results. This incremental approach allows testing individual changes and makes identifying and enforcing the boundary easier.

Rethink Algorithms, Data Structures, and Design

Imperative solutions and design patterns often don't make sense in functional style. Especially for data structures, direct ports of imperative code to functional style can be ugly and slow. A simple example: would you rather copy every element of a list for a prepend or cons the element onto the existing list?

Research and evaluate existing functional approaches to problems. Functional programming is more than just a programming technique, it is a different way of thinking about and solving problems. Projects written in the more traditional functional programming languages, such as lisp or haskell, are great resources in this regard.

Understand the Language and Builtins

This is an important part of understanding the functional imperative boundary and will effect interface design. Understand what features can be safely used in functional style code and which can not. Everything from which builtins may throw exceptions and which, like [].push, mutate objects, to objects being passed by reference and how prototype chains work. A similar understanding of any other libraries you consume in your project is also required.

Such knowledge allows making informed design decisions, like how to handle bad input and exceptions, or what happens if a callback function does something unexpected? Some of this can be enforced in code, but some just requires documentation on the proper usage.

Another point is how strict your implementation should be. Do you really want to try enforcing the correct behavior on maximum call stack errors or when the user redefines some builtin function?

Using Non Functional Concepts Where Appropriate

Functional approaches are not always appropriate, especially in a language like JavaScript. The recursive solution may be elegant until you start getting maximum call stack exceptions for larger inputs, so perhaps an iterative approach would be better. Similarly, I use inheritance for code organization, assignment in constructors, and immutable objects where they make sense.

As long as the functional interfaces are not violated, do what makes sense and what will be easiest to test and maintain.

Example

Here is an example of converting some very simple real code to functional style. I don't have a very good large example of the process, but this small one touches on a number of interesting points.

This code builds a trie from a string. Ill start with some code based on the top section of John Resig's trie-js build-trie module. Many simplifications / formatting changes have been made and my intent is not to comment on the quality of original code (There are much clearer and cleaner ways to build a trie, so why this c style code comes up first in google is interesting. Here's a quick implementation that uses reduce).

I like this example because I don't have to take it all the way to a true functional implementation, just to functional interfaces. Here is the starting point:

var txt = SOME_USER_STRING,
    words = txt.replace(/\n/g, "").split(" "),
    trie = {};

for (var i = 0, l = words.length; i < l; i++) {
    var word = words[i], letters = word.split(""), cur = trie;
    for (var j = 0; j < letters.length; j++) {
        var letter = letters[j];
        if (!cur.hasOwnProperty(letter))
            cur[letter] = {};
        cur = cur[ letter ];
    }
    cur['$'] = true;
}

// Output for text = 'a ab f abc abf'
trie = {
    "a": {
        "$":true,
        "b":{
            "$":true,
            "c":{"$":true}
        "f":{"$":true}}},
    "f":{"$":true}};

Let's pretend this is the entire program. This program does two things: convert a string to a list of words and build a trie from the list of words. These are the existing interfaces in the program. Here is our program with the interfaces more clearly expressed:

var _get_words = function(txt) {
    return txt.replace(/\n/g, "").split(" ");
};

var _build_trie_from_list = function(words, trie) {
    for (var i = 0, l = words.length; i < l; i++) {
        var word = words[i], letters = word.split(""), cur = trie;
        for (var j = 0; j < letters.length; j++) {
            var letter = letters[j];
            if (!cur.hasOwnProperty(letter))
                cur[letter] = {};
            cur = cur[ letter ];
        }
        cur['$'] = true;
    }
};

// The 'public' interface
var build_trie = function(txt) { 
    var words = _get_words(txt), trie = {};
    _build_trie_from_list(words, trie);
    return trie;
};

Just by defining our interfaces, we can move _get_words to the functional style side of the boundary. Neither replace or split modifies the original string. And our public interface build_trie is functional style too, even though it interacts with some very imperative code. In fact, this is a fine stopping point in most cases. More code would get overwhelming, so let me overview a few other changes.

First, make all the interfaces functional style. This is trivial in this case, just have _build_trie_from_list return an object instead of mutating one.

Handling Bad input

Consider what happens if we call build_trie with an array of characters, build_trie(['a', ' ', 'a', 'b', 'c', ' ', 'f']). The caller assumed this would behave in a functional style, but instead it throws an exception when .replace is called on the array. This may be the intended behavior. Or we could do explicit type checks and make sure the inputs are as we expected. But I prefer duck typing.

Strings are just arrays of characters and arrays are just objects with a length property and non-negative integers as keys. So if we refactored and wrote new replace and split methods that operates on array-like objects of strings, they don't even have to be strings, our code could just do the right thing. (String.prototype.* will not work here, it converts the output to a string). Duck typing is a totally separate from functional programming, but the larger point is that bad input should always be considered.

Fundamental redesign

There are also more fundamental considerations. Assume that we want to build the trie in functional style as well. In the imperative code, the approach was to construct the trie one word at a time. A direct port would have us copy the entire trie every time we need to make an insertion to avoid mutating objects. Clearly that is not going to work. Instead, the trie could be constructed node by node, from the bottom up, so that once a node is completed, it never has to be touched again. Or another approach entirely may be better, a quick search shows many existing functional implementations of tries.

Hope the example clarified things a bit.

Overall, I find writing functional style code in Javascript is a worthwhile and fun endeavor. Javascript is a surprisingly capable functional language, albeit too verbose in its default state.

Good luck with your project.

A few personal projects written in functional style Javascript:

parse.js - Parser Combinators
Nu - Lazy streams
Atum - Javascript interpreter written in functional style Javascript.
Khepri - Prototype programming language I use for functional Javascript development. Implemented in functional style Javascript.

Rest – How is reactive logic programming different from functional programming

From the referenced wikipedia page cited by your link, It can be said that functional approach is orthogonal to being reactive. From the wikipedia article follows that reactive programming can be integrated in several programming paradigms (like procedural, logic, OO or functional).

My understanding is that reactive programming is based on the concept of dataflow, meaning that variable can be built from other variables and their value is constantly updated from its "dependencies", much like what happens in a electronic spreadsheet.

So reactive programming is mostly about data and how data changes.

The functional programming model is essentially based upon the definition of functions and the composition of those to build higher level operations.

The logic programming model is based on logical statements (usually in the form of assertions or equations) and the composition of those. The program executes by finding data that satisfies the proposed logic. This is similar to using a rule engine.

Both approaches can be used to create reactive programs, which will lead to programs built upon different reasoning approach to solving a problem. This reflects on the building blocks offered by the language as can be seen reading the OP link.