JavaScript infinite streams

This post was heavily inspired by this post: Infinite Data structures in Javascript  (author: Dimitris Papadimitriou)

After reading the article, I also wanted to have the bare minimum, and most simple implementation of a Stream - and surprisingly, it is very easy (in terms of code), but also, kinda complicated. Kind of the sweetspot I really like to learn about!

In this implementation, we add a filter method to the stream object, which takes a predicate function pred and returns a new stream object with only the elements that pass the predicate. If the current value passes the predicate, then the resulting stream will include the current value and the result of calling filter on the next property. Otherwise, the resulting stream will only include the result of calling filter on the next property. If there is no next property, then the emptyStream object is returned.

The resulting mappedStream is a stream of strings with the same structure as the original stream, but with each element converted to a string. The resulting filteredStream is a stream with only the elements that are greater than 1.

Why do we need Monads?

1. We want to program only using functions. (“functional programming” after all -FP).

2. Then, we have a first big problem. This is a program:

   f(x) = 2 * x

   g(x,y) = x / y

How can we say what is to be executed first? How can we form an ordered sequence of functions (i.e. a program) using no more than functions?

Solution: compose functions. If you want first g and then f, just write f(g(x,y)). OK, but …

3. More problems: some functions might fail (i.e. g(2,0), divide by 0). We have no “exceptions” in FP. How do we solve it?

Solution: Let’s allow functions to return two kind of things: instead of having g : Real,Real -> Real (function from two reals into a real), let’s allow g : Real,Real -> Real | Nothing (function from two reals into (real or nothing)).

4. But functions should (to be simpler) return only one thing.

Solution: let’s create a new type of data to be returned, a “boxing type” that encloses maybe a real or be simply nothing. Hence, we can have g : Real,Real -> Maybe Real. OK, but …

5. What happens now to f(g(x,y))? f is not ready to consume a Maybe Real. And, we don’t want to change every function we could connect with g to consume a Maybe Real.

Solution: let’s have a special function to “connect”/“compose”/“link” functions. That way, we can, behind the scenes, adapt the output of one function to feed the following one.

In our case: g >>= f (connect/compose g to f). We want >>= to get g's output, inspect it and, in case it is Nothing just don’t call f and return Nothing; or on the contrary, extract the boxed Real and feed f with it. (This algorithm is just the implementation of >>= for the Maybe type).

6. Many other problems arise which can be solved using this same pattern: 1. Use a “box” to codify/store different meanings/values, and have functions like g that return those “boxed values”. 2. Have composers/linkers g >>= f to help connecting g's output to f's input, so we don’t have to change f at all.

7. Remarkable problems that can be solved using this technique are:

   • having a global state that every function in the sequence of functions (“the program”) can share: solution StateMonad.

   • We don’t like “impure functions”: functions that yield different output for same input. Therefore, let’s mark those functions, making them to return a tagged/boxed value: IO monad.

PS: this answer can be found on SO at this link: https://stackoverflow.com/a/28135478 

Closures vs pureness

The other day I was looking at a nested map/reduce/filter constellation which had a bunch of nesting, therefore there were lot of closures. This colleague had an interesting question: "In PHP, usually we can tell the interpreter that a function is relying on something from outside of the function with the `use` keyword, so e.g. we could tell at one level of the nesting that a function not only relying on it's input, but something from the outside (closure). Is there a way to do this in JavaScript?".

Let me show this on an example. (this is a simplified version what you can find at http://reactivex.io/learnrx/ .

Now, are these nested functions pure? No, not really. I couldn't simply unit test them because they need context outside of their closure.

This made me thinking, how could we still achieve pureness?

As anyone, I first tried to Google it (khm DuckDuckGo? Sorry, I'm still not detached from the search giant..). I found this SO thread. The solution seems easy and elegant, how could I not think of that before?

So let's try to refactor our code:

So here you can see that videoBoxartMapper receives 2 arguments, so we can exlicitly depend on the context coming in from the outer function. We could easily achieve that by simply return that function and passing the video argument to it. Tada!

In summary, I think doing these crazy nestings can be harmful from a readability perspective, but as you can see, even this can be refactored in a pure fashion, so yay, we can easily test them, but one needs to have this mindset from day 0 when implementing deeply nested closures.

A bit of lambda calculus

Lately I have been messing around with functional programming. I find it extremely pure and scalable.
But I wanted to get back to the core of it and suddenly I found myself in the deep forests of lambda calculus. This article is going to cover what I learned the past few weeks. Let's jump in!

Lamba syntax only has

• variables: x
• lambda abstractions: λx.x
• applications: (t s)

And that's it. Boom.

You have everything at this point. You have a Turing-complete language.
And that's (the simplicity) one of the most remarkable about this system.
Unlike other languages it has one primitive element which is the function. No Integers, Numbers, Strings, Characters, Booleans, etc.. Only functions.
But with this simple concept you are able to create any real-world general-purpose programs. (That's Turing-completeness in a nutshell in a very informal way.)
At this point you are going to ask: how can I implement primitive types such as booleans or numbers with functions? - And that's a very good question.

Church encoding

Don't be afraid of this term, it won't hurt.

Church encoding only means to be able to represent data and operators in the lambda calculus.

From another perspective: the guy (Alonzo Church, who had a major impact on modern logic and computation technology) who invented the lambda calculus was not a lunatic when he decided to create the core rules of the language but instead he wanted to create a general language for an investigation where he wanted to determine the foundations of mathematics. So he knew this language should support e.g. addition on two numbers. And - come closer, let me whisper something - it can.
To understand this we have to go a bit abstract.

You are thinking right now: "how could we possibly get the primitive 1 out of only function expressions?". The answer is: we won't.
We are going to go abstract. We are going to call a certain expression 1.
 And with this abstraction we can create a rule set where e.g. addition is going to make sense, so e.g. 1 + 1 = 2. Elementary school flashback, isn't it?
But first, let's look at the most basic primitive element of any programming language: The Booleans. (As I wrote it down it feels like an 80's TV show.)
Think about booleans as a choice.
Let's create a higher-order function where if something is true it is going to return the "first" argument of the function and it returns the second if it's false.
true := (λx.(λy x))
false := (λx.(λy y))
It makes more sense if we define the basic logical operators as well:
and := (λp.(λq. p q) p)
or := (λp.(λq. p p) q)
Let's try a simple operation: (and true false):
(λp.(λq. p q) p) (λx.(λy x)) (λx.(λy y)) := true false true := (λx.(λy x)) false true := false := (λx.(λy y))
BOOM. true AND false = false. Magic.
What is really important here is the result is a function expression as well.

OK. Now we can do some simple logic operations. How about numbers? Addition? Multiplication? ..?
We can do that too! But remember, we only have functions as building blocks, and with these we are going to mimic numbers with functions (or function compositions).
Let's pretend that character "1" is not a number but just a character. Which is the case by the way in lambda calculus since we don't have any other primitive data types than functions.
With this let's define numbers as functions.
The key concept will be the following: if a function is going to compose that function n-times we are going to look at that function as a representation of the number n.
E.g.: f(f(f(x))) /or λf. λx.  f f f x / means it's the number 3. And λf. λx. x means it's the number 0.
0 := (λf. λx. x)
1 := (λf. λx. f x)
2 := (λf. λx. f f x)
3 := (λf. λx. f f f x)

...

n := (λf. λx. f ⁿ x)

With this abstraction now we can think about numbers as function expressions.
As we discussed in the previous example at the logical operations let's create  a simple operation on numbers: increment. This is the good ol' fashioned i++; statement. Let's call it succ (as successor).
succ := (λn. λf. λx. f (n f x))
Let's succ 0 for the sake of simplicity:
succ 0 := (λn. λf. λx. f (n f x))(λf. λx. x)
Basically what this means is call f on a function w-hich already called n-times f. f ⁿ⁺¹. Easy.
succ 0 := (λn. λf. λx. f (n f x)) (λf. λx. x) = (λf. λx. f ( (λf_. λx_. x_) f x ) ) = (λf. λx. f ( (λf_. f_) x ) ) = (λf. λx. f x)
And the result is 1! That's it!
You can imagine now and belive me there is a way to "simulate" all the mathematical operations such as addition, multiplication, exponentiation, etc.. If you're interested, you can find out more here.

This "thinking about natural numbers as they were functions" concept is called Church numerals. I skipped this term on purpose: I didn't want to scare you with formal mathematical words. But that's it, now you know what Church encoding and Church numerals are. Congratulations!

Fun fact the system above only works on natural numbers since if we would go under 0 it would just give us 0. But obviously we can create a system where minus numbers are also included in this game, but I'm not going to cover that topic in this very article. :)

Here is a very good lambda calculator if you would like to play around with lambda expressions: http://www.cburch.com/lambda/

In summary: I find it extremely interesting and fascinating that we can think about data, operations and almost anything else as composition and representation of functions. Nothing else is needed, just plain, simple functions.

Happy Functional Holidays!