Functional Programming - Randomize IEnumerable

.Net has IEnumerable to represent a sequence. Though it is not advertised as a functional helper, we can use IEnumerable to get really clean functional programming in .Net. It has so many methods to manipulate and select elements but it really lacks a mechanism to take random numbers from the sequence. Below is one which gives us somewhat random elements from the IEnumerable sequence.

---

public static IEnumerable<TResult> Randomize<TResult>(this IEnumerable<TResult> source)
{
            return source.
                Select((sourceItem, index) => new
                {
                    Item = sourceItem,
                    Id = Guid.NewGuid()
                }).
            OrderBy(t1 => t1.Id).Select(t1 => t1.Item);
}

---

How to use the above?

---

IEnumerable<int> input = new List<int>() { 1, 2, 3, 4 };
int randomElement = input.Randomize().FirstOrDefault();

---

As seen in the source the randomization is depended on the GUID generation. If the GUIDs are generated in increasing order the randomization will not work.

The advantage of this method is to randomize as lazy collection.

Nuget support

The above is available as nuget. Below is the URL.

https://www.nuget.org/packages/DotNet.Helpers

Functional Programming - Finding valleys

If we were from ASP.Net Web Forms world and tasted the ASP.Net MVC at least once, it is very difficult to go back. It is similar when we go from imperative world to functional programming world. This post is a continuation of Functional Programming series. The advantages of FP has already discussed in earlier posts. 

The problems are mainly taken from HackerRank and trying to solve using FP methods. The main intention is to understand how to solve problems functionally which otherwise considered as 'solvable only imperatively'.

The Problem

Input is a sequence of D and U characters. D means one step down down and U means up. A person named Gary is hiking from sea level and end at sea level. We need to find out how many valleys he covered. If he is in a deep valley and had a small hill and again went down, it is counted as one valley. Detailed description can be found in original link

https://www.hackerrank.com/challenges/counting-valleys/problem

Traditional solution

The traditional (FP was there for long, but not in main stream) ie if someone comes from imperative programming world, they get it as state machine problem. Yes there are states where Gary reaches after each step. The state has to be mutated based on the rules.

In functional programming, mutation is not an appreciated word. So lets see how can we do this without mutating the state.

Functional way

Language used is JavaScript

---

function countingValleys(n, s) {
  
  var res = s.split('').reduce((context, value,index,arr) => {
    //console.log(context)

    if(value === 'D') {
      if(context.s === 0 ) { return {v:context.v+=1,s:context.s-=1}}
      else return {v:context.v, s:context.s-=1}
    }

    if(value ==='U'){
      return {v:context.v,s:context.s+=1}
    }
    else {
      //console.log('error');

    }
  }, {
    v: 0,
    s: 0
  });
  return res.v
}

---

Here n means number of steps and s is the input character sequence. If we enter this into HackerRank browser based editor, with their auto generated wiring code, this returns the number of valleys covered.

How it runs

It uses the Fold concept of FP which is implemented in JavaScript using reduce() function. Initial state is given to the reduce function, when the function progress through each element, it create new states (context variable hold the state) from existing state with the modification required. Yes as per FP, mutation is evil not creation of object from another. Also notice that -= and += is not mutating the state, instead its a transformation when assigning value during creation.

The commented console.log lines will help to under the flow it allowed those to run.

Happy functional coding...

Functional Programming - Find hidden string in the input

This is continuation of my functional programming experiments in JavaScript. This problem is from HackerRank.

The problem

Input is a string and we have to find out whether the letters of word 'hackerrank' are present inside it in the right order. When we say order, there might be some other letters in between the letters of 'hackerrank' the the order should be maintained. More details can be found in the actual problem link. 

Traditional solution

If the guy is not from the computer science background, there is 99% chance that the solution will be based on loops where a lot of states might have stored temporarily. But it looks like a familiar situation of email validation where we are expecting chaaracters in specific order.

The RegExp way

Regular expressions are great. There is no doubt on that. Here goes the regular expression way.

---

function checkForhackerrank(input) {
  if(testForhackerrank(input)) {
    return 'YES';
  }
  else return 'NO';
}
function testForhackerrank(input){
  return /h(.)*a(.)*c(.)*k(.)*e(.)*r(.)*r(.)*a(.)*n(.)*k/g.test(input)
}

---

Works great for the word hackerrank. Lets generalize

Generalized version

Below goes the generalized version which can work for any pattern other than 'hackerrank'.

---

function testForhackerrank(input){
  return getFindPattern('hackerrank').test(input);
}
function getFindPattern(stringToSearch) {
  return getGlobalRegExp(stringToSearch.split('').map(a=> `(.)*${a}`).join(''));
}
function getGlobalRegExp(pattern){
  return new RegExp(pattern,'g');
}

---

This doesn't need anything special regarding functional paradigm as the magic is done by regular expression. Plnkr is here.

Enjoy coding.

Functional Programming - Finding unique characters in string

These are small code snippets created as part of learning functional JavaScript. As we know when we say functional programming, we have to create pure functions, avoiding assignment etc...It really require practice to write the functional way especially, if we started in imperative languages. This is first in the series where some algorithms are written using functional style.

1. Functional JavaScript - Finding unique characters in string.

The problem

The problem is simple. Have to find out unique chars in string. eg: Hello has to return Helo. 

Functional ways

The easy way is to loop through the characters and push items into another array, if it is not already present. Finally create string by joining array.

Below is slightly different version where the characters are filtered, if the index found in original string is different than current index.

function uniq(str) {
    return str.split('').filter(function(item, index, self) {
      return self.indexOf(item) == index;
    }).join('');
}

Runnable plnkr below. 

ConcurrentCounter - Reduce code with Functional programming

The fashion of functional programming

Now a days functional programming already made its come back and every language, companies and developers want to embrace functional programming. When we look at their works we can see it needs to travel more to reach the functional programming world. It was same for object oriented world as well. People used C++ but the code looked like C.

That is not the concern with this post. One of the reasons we here when people adopt FP is that it helps us to achieve things with less code. This is just a scenario where FP can reduce some amount of code.

Scenario - Thread safe manipulation of resources

We are in the world of threads. Knowingly or unknowingly we had to deal with threads. Some languages / technologies already has better ways to deal threading without developer write any explicit line. NodeJS can be an example. But for C# guys like me, has to write programs properly to make sure it works with threads. If all the tasks are ready to run in parallel,  there are no issues. But the reality is not that way. There will be so many critical sections we had to handle to achieve a good working software. We rely heavily on thread synchronization mechanisms to achieve the same. Whenever we deal with those, it is nightmare and there are so many chances to produce duplicate code. That is the place functional programming can help us.

Taking one situation. We have a counter inside a web service.That counter can be considered as a resource just like file or other resources. Counter variable is accessed by multiple service methods, some reads some writes. So the first way comes to our mind would be C# lock (VB.Net SyncLock) keyword. When we implement it there are chances that we may write lock statement in multiple places. Below is a mechanism to avoid that by using functional techniques of C#.
Please note that in real world no one should use this mechanism for integers as far as Interlocked class is there in .Net framework. This is just a sample for understanding purpose.

Wrap the lock statement in fuction and pass the actions into it

The technique here is simple as anyone might have guessed. Just have a wrapper around the lock and inside the locked section execute the real manipulation code which is passed into it as Action<T>. Lets see the code snippet below.

internal class ThreadSafeCounter
{
    private int internalValue;
    private object lockObject = new object();
    public int Value
    {
        get
        {
            return ExecuteWithLock(() => { return internalValue; });
        }
    }
    public ThreadSafeCounter(int initialValue)
    {
        this.internalValue = initialValue;
    }
    public void Increment()
    {
        ExecuteWithLock(() => { internalValue++; });
    }
    public void Decrement()
    {
        ExecuteWithLock(() => { internalValue--; });
    }
    public void Reset()
    {
        ExecuteWithLock(() => { internalValue=0; });
    }
    #region Helpers
    private void ExecuteWithLock(Action action)
    {
        lock (lockObject)
        {
            action();
        }
    }
    private int ExecuteWithLock(Func<int> fun)
    {
        int result = 0;
        ExecuteWithLock(() => result = fun());
        return result;
    }
    #endregion
}

The main functions to notice here are as below.

ExecuteWithLock(Action a)
ExecuteWithLock(Func)

The lock(){} is there only in one function named ExecuteWithLock() and all other functions those wants to execute critical section of code has to call ExecuteWithLock and pass the code as parameter. That code passing as parameter is obtained by the well known Action<T>. Hope there is no need of further explanation. 

C# Overloading Action & Func and why {} matters

Basics - Overloading

Let us start with basics of overloading. Will the below code compile?

class SomeClass
{
    void Execute()
    {
 
    }
    int Execute()
    {
        return 10;
    }
}

Certainly not. We know that overloading applies to the arguments. Return type is not considered.

Now look at below code. Will it compile?

internal class SomeClass
{
    void Execute(Action handler)
    {
    }
    int Execute(Func<int> worker)
    {
        return worker() ;
    }
}

Don't spend more time. It will compile. For sure. Will it work as expected? That is tricky question. As of our understanding, we are using strong typed languages to avoid many runtime type related issues. So that we can concentrate on our logical issues more.

Consider the below code and guess what happens

internal class SomeClass
{
    internal void Test()
    {
        this.Execute(() =>  Console.WriteLine("Hi"));
    }
    void Execute(Action handler)
    {
        Console.WriteLine("Inside Execute(Action)");
        handler();
    }
    int Execute(Func<int> worker)
    {
        Console.WriteLine("Inside Execute(Func)");
        return worker() ;
    }
}

SomeClass cls = new SomeClass();
cls.Test();

The output will be
Inside Execute(Action)
hi

The problem

If we call Execute as shown below which function will execute?

internal class SomeClass
{
    int num = 0;
    internal void Test()
    {
        this.Execute(() =>  num++);
    }
    void Execute(Action handler)
    {
        Console.WriteLine("Inside Execute(Action)");
        handler();
    }
    int Execute(Func<int> worker)
    {
        Console.WriteLine("Inside Execute(Func)");
        return worker() ;
    }
}

SomeClass cls = new SomeClass();
cls.Test();

The output will be 

Inside Execute(Func)

Why did this happen? Since the C# language support lambda expressions without explicit return value which is just there it assumed that the intention is to return the incremented value. Sometimes the original intention of developer might be just to increment the num variable. Some conflict happened between the developer and the language.

This is kind of OK scenario. Nothing breaks. Lets see little more complex scenario where it cause trouble.

internal class SomeClas
{
    int value = 0;
    internal void Test()
    {
        this.Execute(() => value++ );
    }
    void Execute(Action handler)
    {
        Console.WriteLine("Inside Execute(Action)");
        handler();
        CleanUp();
    }
 
    int Execute(Func<int> worker)
    {
        Console.WriteLine("Inside Execute(Func)");
        int result = 0;
        Execute(() => result = worker());
        return result;
 
    }
    private void CleanUp()
    {
        Console.WriteLine("CleanUp");
    }
}

The developer wants to do some cleanup after Execute. So he added the CleanUp() inside action and he wanted to avoid CleanUp() in all the other functions. Other functions pass action to so that the CleanUp() will be performed for all the Execute() calls. 

The expected output event with call to Execute(<Func>) is

Inside Execute(Func)

InsideExecute(Action)

Hi

But what happens here is infinite loop. Some clever language geeks might have foreseen thie infinite loop. But normal developer will not.

Fix - Use curly brackets / braces / {}

People think that putting {} is time waste and they avoid it where ever possible. But here it would have saved some time. See the fix below.

internal class SomeClas
{
    int value = 0;
    internal void Test()
    {
        this.Execute(() => value++ );
    }
    void Execute(Action handler)
    {
        Console.WriteLine("Inside Execute(Action)");
        handler();
        CleanUp();
    }
 
    int Execute(Func<int> worker)
    {
        Console.WriteLine("Inside Execute(Func)");
        int result = 0;
        Execute(() => { result = worker(); });
        return result;
 
    }
    private void CleanUp()
    {
        Console.WriteLine("CleanUp");
    }
}

Just adding {} into lambda expressions helps us a lot. If Test() used {} it would have avoided one more function call and could have reached to Execute(Action) directly.

Moral of the story is don't hate braces. Omitting those is not going to save lot of time or decrease size of program.

Considering the API

But please be aware that if we are giving these Execute() methods as APIs there is no guarantee that our customers will use {} always. So we have to overload the functions properly.

What is side effect of a function in programming?

Introduction

This articles explains what is side effect of function and advantages of avoiding side effects

Background

We all work with object oriented programming for years and our normal thinking goes to desinging application as similar to real world as much as possible. We use object oriented design principles to achieve the same. Shoud we really make everything object with its own class level properties? We are trying to investigate is there any better way to write code which is maintainable

What is side effect of a function

When we write a function / method in the first place, what is our intention? It does a job. It may or may not accept parameters. Sometimes it returns a value. That is the effect of the function invocation.

But there might be situations, that a function may start doing things which are not controlled by that  function. Look at the below code. 

---

//
// ES6 code which has a function with side effect.
//
class Calculator {
  constructor() {
    this.op = "add";
  }
  calculate(n1, n2) {
    if (this.op === "add") {
      this.op = "sub";
      return n1 + n2;
    } else {
      this.op = "add";
      return n1 - n2;
    }
  }
}

---

Here what is the effect? As consumers we call the calculate() the effect we are expecting is the calculated value. But what is happening here?

We get the calculated value. But in the mean time its doing something else on class level variable which we as consumers, don't expect.

It makes our next call gives different output for the same input values. Those are considered as side effect of the function. Side effect will be seen, if we look from the consumer's view.

Below is the code to invoke the function 3 times with same input.

---

var calc = new Calculator();
alert(calc.calculate(20, 12));
alert(calc.calculate(20, 12));
alert(calc.calculate(20, 12));

---

Drawbacks on functions with side effect

The functions with side effects make it difficult to reason about code. What is reasoning about code? If we simulate the working of code, it is little difficult as we need to remember the state too along with the steps. This makes it difficult to achieve development speed and often cause bugs as it is difficult to think about all the possibilities.

This again brings constraint on calling order especially when there are multiple threads using same object to call the methods. When those kind of scenarios occur, it would be difficult to reproduce the bug at the developer end. Normally when developers encounter these types of thread issues, they simply put a lock around critical section. That simply brings us the effect of old single core processors. Our program will not be able to take advantage of multi cores if we just put locks in our code as it make the threads wait for each other. This may lead to deadlocks as well.

What else brings side effect to a function

Not only changing the global state is considered side effect. Whatever we are doing to the state of outside world is considered side effects. Consider the modified code.

---

// ES6 code which has a function with side effect. It doen't alter class level variable.
class MyCalculator {
  calculate(n1, n2, op) {
    var result;
    if (op === "add") {
      result = n1 + n2;
    } else {
      result = n1 - n2;
    }
    console.log("success");
    return result;
  }
}

---

This seems like side effect free. But if we look at the logging code, we can see its changing the outer world. So has side effect. If somebody has run the below code before invoking above method, only alternate calls will succeed.

---

// Redirect the console.log
var shouldSuccess = true;
console.realLog=console.log;
console.log = function(msg) {
  if (shouldSuccess) {
    shouldSuccess = !shouldSuccess;
    console.realLog(msg);
  } else {
    shouldSuccess = !shouldSuccess;
    throw "I am tired!!"
  }
};

---

In the real scenarios, there might be situations similar to this and that will cause the function fail inconsistently.

Can we write everything without side effects

The world is stateful. Its not possible to write every method in production code to be side effect free. But we should try to minimize the side effect as much as possible. Especially when we are writing sequential algorithms, transformations etc...Also we can we immutable objects to avoid risks.

Points of Interest

There are concepts like pure functions, idem potent functions which are related to side effects. The function programming concept too trying to solve the side effects to an extent.

What if there are no looping constructs in your language?

Being a professional software engineer, we cannot say that we are done we cannot program without looping control flow. Developers who started their career in machine or assembly language don't get scared of this. Similarly who understood and practiced machine and assembly language in college in. They will simply use 'go to' along with if statement and get the things done.

Forgot to tell in the question 'go to' is banned as always.So how can we tackle it without goto.

Lets come to code. Here we are going to see the scenario in 2 famous languages C# and Javascript. Below is the code to display numbers 1,2,3...10 in descending order which is written using loops.

---

Javascript	C#
function LoopWithWhileKeyword(loopCount) {     while (loopCount > 0) {         logLine(loopCount);         loopCount -= 1;     } }	void LoopWithWhileKeyword(int loopCount) {     while (loopCount > 0)     {         logLine(loopCount);         loopCount -= 1;     } }

This is straight forward. The code to call these functions is omitted to get focus, Now lets think how we can avoid this loop.

What is happening here

If we step back and think we can see there are mainly 2 code blocks. 

• One block determines the continuation of execution.
• Second is the actual code to execute multiple times.

Some idea might have triggered in everybody's brain who had done some programming. Nothing but extracting those separate blocks to functions.

We can use 'if' statement to decide whether to continue execution or not based on the return value if we move the condition logic to function. Then how do we execute the repeatable code block again without go to?

Execute the same function again. All of us has tried this in college when dealing with Fibonacci series. If we call a function from inside same function we can simulate loops. Yes recursion!!!

Lets see the code below which is rewritten with recursion.

Javascript	C#
function LoopWithoutWhileKeyword(loopCount) {     WhileLoop(function () {         return loopCount > 0     },     function () {         logLine(loopCount);         loopCount -= 1;     }); } function WhileLoop(condition, action) {     if (condition()) {         action();         WhileLoop(condition, action);     } }	void LoopWithoutWhileKeyword(int loopCount) {     WhileLoop(         () => loopCount > 0,         () =>     {         logLine(loopCount);         loopCount -= 1;     }); } void WhileLoop(Func<bool> condition, Action action) {     if (condition())     {         action();         WhileLoop(condition, action);     } }

Good. Isn't it? For those who gets headache on seeing recursion please read the explanation.

Here the WhileLoop function accepts 2 functions. It checks whether I should continue or not. Similar to the evaluation inside the while loop condition check. If the result of condition check is true, it calls the action method which has the code  needs to be executed multiple times.

Then it calls the WhileLoop function again to repeat the cycle. Since the action function has the code to reduce the loop count, it will end when the loopCount becomes 0.

Higher Order Function

We learned a jargon in programming called Higher Order Function. Any function which accepts another function or returns a function can be called as higher order function. Thinking that its this simple refer wiki

Most of us might be thinking, why we learned the loops if functions can do the job of loops. Why there are many ways to do same thing in computer science?

Tail call optimization

Normally developers has a tendency to use new things learned in their day job because of excitement. They might have heard it or saw one demo which touched the good parts of the concept / feature / technology.

Before anybody apply this technique in your production app understand and test it properly. Let's test this code by given 100,000 to the function.

In C# your will encounter 

An unhandled exception of type 'System.StackOverflowException' occurred in mscorlib.dll

In browser, you will get 

Uncaught RangeError: Maximum call stack size exceeded

In my machine I got javascript error when the recursion reaches 17911 and c# 4.0 failed after 12202 iterations.

Don't think that this issue will occur always. There are technologies and languages in which this issue will never occur. If we we are getting this, that tells us that our run-time or compiler does not do tail call optimization. Google for what is tail call optimization.