DEV Community: Angelo

Time and Space Complexity in 2 minutes

Angelo — Mon, 21 Dec 2020 13:21:10 +0000

Space Complexity: How much memory is used.
Time Complexity: How many operations are executed.

This is my interpretation time and space complexity applied to software development.

Time complexity

Constant Time O(1)

A Constant Time complexity operation would be simply running a statement, or a value lookup in an object.
Example:

arr.pop()
arr[1]
5 + 3
4 * 2

Logarithmic O(logn)

With each loop you cut your decrease you work in half, or by a fraction.
A good example of this would be a binary tree. With each step into the search we should be eliminating a fraction of the tree.
So our Time complexity is decreasing by a fraction each time.

Linear O(n)

Linear time complexity, looping through values of an array.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for(let i = 0; i <= array.length; i++){
 ...
}

An array has a start and end. The operation would run across the array. Resulting in a complexity of O(10), which is not complex at all.
In the above example, n represents the number of items in our array.

Quadratic O(n^2)

Quadratic time complexity, a loop, in a loop, in a loop.

for(...){
  for(...){
    for(...){
    }
  }
}

The above results in 0(n^3)

Exponential O(k^n)

Exponential time complexity refers to an algorithm whose growth doubles with each loop.

Space complexity

Space complexity deals with space an algorithm takes up in memory.
As a trade off to executing a Quadratic Time Complex algorithm, we could create a hash table which is stored in memory.
Now, with our hash table in memory, we can run a Constant or Linear time algorithm against the hash table.
As a trade off, we have increased the Space Complexity by keeping a hash table in memory and decreased the Time complexity or our algorithm.

Using Futures to handle complex asynchronous operations in javascript.

Angelo — Wed, 25 Sep 2019 03:18:08 +0000

To demonstrate Futures in javascript I will be referencing the Fluture library. A Fantasy Land compliant Monadic alternative to Promises.

Fluture offers a control structure similar to Promises.
Much like Promises, Futures represent the value arising from the success or failure of an asynchronous operation (I/O).

Getting a value from an end point using a promise is a fairly trivial operation.

It may look something like this.

import axios from "axios";

var getToDo = id => axios.get(`https://jsonplaceholder.typicode.com/todos/${id}`)

getToDo(1)
 .then(({data}) => data)
 .catch(e => e)

// { userId: 1, id: 1, title: 'delectus autautem', completed: false }

Getting a value out from an end point using a future is also fairly trivial. It looks like this.

import axios from "axios";
import { tryP } from "fluture";

var getToDo = id => 
 tryP(() => axios.get(`https://jsonplaceholder.typicode.com/todos/${id}`))

getToDo(1).fork(err => err, ({ data }) => data)

// { userId: 1, id: 1, title: 'delectus autautem', completed: false }

Something to note. To get the result of a Future, we must fork. The Left side of our fork will run if there is an error, similar to catch. The right side of our fork will contain our result, similar to then.

Futures allow us to chain and map their results into other futures or perform data manipulation on the results of a future before returning, as well as catching errors and managing those before actually forking.

Here is an example.

import { tryP, of, ap } from "fluture";
import axios from "axios";

const loginRequest = email => password =>
  tryP(() => 
   axios({
    url :`https://www.fake.com/login`, 
    data : { email, password }
   })
)

const userDetailsRequest = id =>
  tryP(() => axios.get(`https://www.fake.com/userDetails/${id}`))


const login = email => password => loginRequest(email)(password)
 .chain({ data }) =>  userDetailsRequest(data.id))
 .map(({ data }) => formatData(data))
 .mapRej(err => formatError(err))


login('faker@gmail.com')('admin123').fork(err => err, userDetails => userDetails)

Difference between `.chain` `.map` `.mapRej` and `.chainRej`

Chain: the result of a .chain must be a Future
Map: the result of a .map is not a future
MapRej: the result of a .mapRej is not a future and will only be triggered if a Future fails
ChainRej: the result of a .chainRej must be a future and will only be triggered if a Future fails

If a future fails/errors, it will "short circuit" .map and .chain will not be run, the flow will be directed to either . mapRej or .chainRej whichever is defined by the programmer.

Now to something a little more complex.

I was recently asked to write a program that fetched comments for a blog post. There was a request which returned the blog post and it included an array of id's. Each id represented a comment. Each comment required its own request.

So imagine having to make 100 requests to get back 100 comments.

(Parallel)[https://github.com/fluture-js/Fluture/tree/11.x#parallel]

Fluture has an api called parallel

Parallel allows us to make multiple async requests at once, have them resolve in no particular order, and returns us the results once all requests have completed.

Here is what this would look like.

import { tryP, parallel } from "fluture";
import axios from "axios";

// Our Future
const getCommentRequest = comment_id =>
  tryP(() => axios.get(`https://www.fake-comments.com/id/${comment_id}`))
  .map(({ data }) => data);

// comments is an array of ID's
const getComments = comments => 
 parallel(Infinity, comments.map(getCommentRequest))

// Infinity will allow any number of requests to be fired simultaneously, returning us the results once all requests have completed.

// The result here will be an array containing the response from each request.
getComments.fork(err => err, comments => comments)

Replacing Infinity with a number. Say 10, would fetch 10 comments at a time, resolving once all comments in the array had been retrieved.

In the next Example, imagine a case where may must fetch some data which is only useful to us if some initial request(s) succeeds.

(AP)[https://github.com/fluture-js/Fluture/tree/11.x#ap]

Applies the function contained in the left-hand Future to the value contained in the right-hand Future. If one of the Futures rejects the resulting Future will also be rejected.

Lets say we need to fetch a users account. If the account is found, we can then attempt to fetch their friends. If we find their friends, we can attempt to fetch their friend's photos. If any of these requests fail, them the whole flow short circuits, and we would fall in left side of our fork where we can handle the error.

import { tryP, of, ap } from "fluture";
import axios from "axios";

// Our Futures
const retrieveUserAccount = id =>
  tryP(() => axios.get(`https://www.fake.com/user/${id}`))

const retrieveUserFriends = id =>
  tryP(() => axios.get(`https://www.fake.com/friends/${id}`))

const retrieveUserFriendsPhotos = id =>
  tryP(() => axios.get(`https://www.fake.com/friendsPhotos/${id}`))

const retrieveUserInformation = id =>
  of(account => 
      friends => 
       friendsPhotos => {account, friends, friendsPhotos}) //All results returned
    .ap(retrieveUserFriendsPhotos(id)) // 3rd
    .ap(retrieveUserFriends(id)) // 2nd
    .ap(retrieveUserAccount(id)) // Fired 1st

retrieveUserInformation.fork(err => err, results => results)

Futures allow us to nicely compose our asynchronous operations.

(More information on Flutures)[https://github.com/fluture-js/Fluture/tree/11.x]

Thanks for reading!

Conditional rendering in React with catamorphisms.

Angelo — Sat, 04 May 2019 21:15:20 +0000

Do you ever look at your React components and think to yourself, there has got to be a better way to handle these conditions inside my components.

When I was first introduced to functional programming. One of the "rules" imposed was to never use if / else / else if.

This presented a huge issue for me. How can I manage this. Also, how can I manage this in my React Components?

Lets first look at an example of what I am talking about.
Below is an example of checking a variable and then returning the correct component.

The same result can also be achieved using a switch statement.


import React from 'react'
import Doberman from './Doberman'
import Chihuahua from './Chihuahua'
import BullDog from './BullDog'

const Dog = breed => {

    if(breed === 'Doberman') {
        return <Doberman />
    } else if (breed === 'Chihuahua')
        return <Chihuahua />
    } else {
        return <BullDog />
    }

}

So, whats wrong with this?

In my opinion, its ugly.

It is not safe. breed can come back as undefined or better yet some other breed of dog.

Also, in this example we are adding logic to our UI components, which is challenging to test.

So lets talk about how Catamorphisms can helps us manage these conditions in a different way.

Catamorphism

Taken from Wikipedia
In functional programming, catamorphisms provide generalizations of folds of lists to arbitrary algebraic data types

For those new to functional programming, fold can also be referred to as reduce or aggregate.

Say our application needed to determine the breed of dog, and then render the corresponding component to its user. In order to implement a catamorphism we would need to identify all the breeds of dog we would expect.

Here is an example of our list, that will support a catamorphism.


import daggy from 'daggy'

const DogBreed = daggy.taggedSum('DogBreed', {
    Doberman : [],
    Chihuahua : [],
    BullDog : [],
    Unknown : []
})

Check out daggy here

Our application would need to have an initial state defined. Inside our initial state we would assign our dog breed. Lets have a look...


const INITIAL_STATE = {
    dog : {
        breed : DogBreed.Unknown
    }
}

Since our application has not yet loaded, and we do not know what our dog breed is, we create an Unknown breed.

At some point in our applications lifecycle we would set our dog's breed.

Lets have a look at this example of setting our dog's breed using this super cool FP library Pratica.


import { Ok, Err } from 'pratica'
import daggy from 'daggy'

const DogBreed = daggy.taggedSum('DogBreed', {
    Doberman : [],
    Chihuahua : [],
    BullDog : [],
    Unknown : []
})


// DogBreed.is 
// A useful built in type check when using daggy.
const isValidBreed = breed => DogBreed.is(breed) ? Ok(breed) : Err()

// Safe function with no side effects. 
export const getBreed = dog => Ok(dog)
    .chain(dog => Ok(dog.breed))
    .map(breed => breed === 'Doberman' ? DogBreed.Doberman : breed)
    .map(breed => breed === 'Chihuahua' ? DogBreed.Chihuahua : breed)
    .map(breed => breed === 'BullDog' ? DogBreed.BullDog : breed)
    .chain(isValidBreed)
    .cata({
        Ok: breed => breed,
        Err: () => DogBreed.Unknown
    })

Let me take a second to talk about what is going on here.
Im using the Ok monad to check our dog object.

We pass our dog into our Ok monad
Next step, we chain chain allows us to unwrap our Ok Monad.
a. Then set another Ok monad to check for dog.breed.
b. If dog.breed is undefined our Ok monad will return Err and will pass straight to our cata.Err where we set DogBreed.Unknown.
We then pass the into a map. Map accepts the output of ourchain, our OK Monad.
a. Map takes an OK monad unwraps it and checks it and then and wraps it back into ourOk monad
b. We map over every possible breed type.
c. If we find a match we set our breed.
d. If not we return type to our next map.
Our last check, .chain(isValidBreed).
a. Why do we need this? If the breed is not one we are expecting, we need to handle that case and defer to Err() which will default to DogBreed.Unknown
b. We chain the result of our above maps into a function isValidBreed
c. isValidBreed does a check on the breed. If it is of type DogBreed, we return an Ok monad with the breed. If not, we return Err()

Great.

Here, we show calling our safe getBreed functions that implements pratica.


// a contrived example of updating our state...
const dog = { breed: 'Chihuahua' }

const state = {
    dog : {
        breed : getBreed(dog) // DogBreed.Chihuahua
    }
}

We are now ready to see this in action.
Lets remember the goal is using an alternative to if / else in our react components.

We will be passing breed to our Dog component. breed is now an instance of our daggy DogBreed. Meaning we can apply a catamorphism (cata) to it. The cata will resolve to its current type.


import React from 'react'
import Doberman from './Doberman'
import Chihuahua from './Chihuahua'
import BullDog from './BullDog'

// Lets remember here that breed is the result of `getBreed(dog)` which is a List we can apply a catamorphism on.
const Dog = breed => breed.cata({
    Doberman  : () => <Doberman />,
    Chihuahua : () => <Chihuahua />,
    BullDog   : () => <BullDog />,
    Unknown   : () => <div>{'Unknown breed'}</div>,
})

Daggy also supports the passing of parameters, which can also be quite interesting. Check out daggy here.

Partial Lenses in Javascript

Angelo — Sat, 04 May 2019 03:26:01 +0000

Retrieved from partial.lenses
Lenses are basically an abstraction for simultaneously specifying operations to update and query immutable data structures. Lenses are highly composable and can be efficient. A partial lens can view optional data, insert new data, update existing data and remove existing data and can, for example, provide defaults and maintain required data structure parts.

Dealing with large nested data sets in javascript can be cumbersome.

Getting and Setting some deep nested data in a clean efficient and immutable way is possible using Lenses. With a single line of code we can safely get, update or set a deeply nested item, creating a new JSON object with the changes.

The objective of this write up is to show some examples using Lenses VS vanilla JS.
This is the data set that we will be working with.

const user = {
 name: 'Roger',
 phone: {
   cell: '212-334-1212'
 },
 address: {
   street: '123 First Ave',
   zip: '90210'
 },
 car: {
   daily: [
     {
       make: 'Jeep',
       year: 2013
     },
     {
       make: 'Mazda',
       year: 2018
     }
   ],
   weekend: [
     {
       make: 'Corvette',
       year: 1993
     }
   ]
 }
}

Lets see how we can pull out some data from this data set.
This example will show both Vanilla js and Lenses.
Although both of these examples seem pretty clean, the Vanilla example is susceptible to runtime errors. With the Vanilla example, if any element is not found we will get a runtime error.

In this particular example though, both instances will return Jeep.

Get

import * as L from 'partial.lenses'

L.get(['car', 'daily', 0, 'make'], user) // Jeep

user.car.daily[0].make // Jeep

But what happens if we try to access a record or field that does not exist.

L.get(['car', 'daily', 3, 'make'], user) // undefined

user.car.daily[3].make // Cannot read property 'make' of undefined

Our Vanilla example will trigger a runtime error. In order to achieve the same level of safety we are getting with lenses we need to write something a little more robust.

See below.

// GROSS
if(user && user.car && user.car.daily && user.car.daily.length > 2) {
   return user.car.daily[3].make
} else {
   return undefined
}

Pretty impressive so far?

Compared to the imperative code that checks each field as we drill down, I'd say we get a pretty big net gain with when using Lenses. It's simply cleaner and much easier to reason about.

Defaults

Defaults provide us to set a default value for an element that is missing.

L.get(['phone', 'home', L.defaults('Number not found')], user) // Number not found

If the value is not missing, L.defaults will be ignored. Pretty sweet.

Set

Alright, let's set some data.
Say we want to set a new car in our weekend drivers array.

L.set(['car', 'weekend', L.appendTo], {make: 'Ford', year: 1979}, user)
// Returns the entire User object with the new car record

Notice the L.appendTo. I'd say this speaks for itself. In short this will retain any existing records found in car.weekend and simply append our new record.

Something that you may find interesting.

Say that our object did not have a car and weekend element. Our above Lense would create and set car.weekend as well as adding the new car record to the weekend array. What?!?!

That's right folks. You gotta try it to believe it.

I should point out that we are really just scratching the surface. When I first came across Lenses I had difficulty understanding how so few people, at least in my circles had not even heard of them.

I'd like to add one more example! Lets checkout collect

Collect

Collect safely traverses an array.

L.collect(['car', 'daily', L.elems, 'make'], user) // [ 'Jeep', 'Mazda' ]

In this case we drill down to car.daily.
L.elems represents our traversal over elements.
And finally make is the element we are looking for.

As the name suggests, collect collects results and returns them to us in an array.

If any of the elements in our collect do not exist, we will simply get back an empty array.

How about that ?

You gotta check out Partial Lenses

Maybe. Functional programming in Javascript with React.

Angelo — Mon, 29 Apr 2019 02:42:22 +0000

Before I get into the main point of this article, which is to showcase the amazing Maybe monad. I would like cover a high level functional programming concept, composition. Composition is at the root of functional programming.

#Composition
const compose = f => g => x => f(g(x))

Composition allows us to compose functions together.

// Add 10%
const addFederalTax = x => x * 1.1
// Add 15%
const addStateTax = x => x * 1.15

// Traditional
// const addTaxes = price => compose(addStateTax)(addFederalTax)(price)

// Point Free
const addTaxes = compose(addStateTax)(addFederalTax)

// Lets add State and Federal taxes to 5 Dollars
addTaxes(5.00) // 6.32

Another cool concept being used above is point free style.

Great.

We will use the Maybe Monad in traversing some data, and then outputting safe to use data.

My love for McDonald's has inspired me to create a data set that represents a slice of some McDonald's restaurant's breakfast menu.

const restaurant = { 
    name: 'McDonalds',
    location: 'Kansas City',
    menu : {
    breakfast : [
            {name: 'Pancakes', options: ['Bacon', 'Sausage']},
            {name: 'McMuffin', options: ['Egg', 'Cheese', 'Sausage', 'Ham', 'Bacon']},
            {name: 'Coffee', sizes: ['Small', 'Medium', 'Large', 'X-Large'], options: ['Milk', 'Creme', 'Sugar']},
        ]
    }
}

Maybes are great when working with data structures that are not reliable.
For example in our breakfast items example above, Coffee is the only option that includes sizes. Checking for sizes in Pancakes or Muffins would cause a runtime error. Not to mention that some locations may not even offer breakfast!

First, we want to make sure that breakfast is offered.

Before we get into the functional stuff.
Let's look at the imperative way, or more conventional style of checking if breakfast is offered.

function hasBreakfastMenu (restaurant){
    if(restaurant.menu && restaurant.menu.breakfast){
        return restaurant.menu.breakfast
    } else {
        // Do Something
        console.log('Not found')
    }
}

const breakfastMenuItems = hasBreakfastMenu(restaurant)

Now, we will do the same in a functional style.

To achieve this we will use get from the Pratica library. The Pratica get function returns a Monad. Monads are safe, and protect against runtime errors.

// breakfastMenu.js
import { Maybe, get } from 'pratica'

const hasBreakfastMenu = get(['menu', 'breakfast'])

hasBreakfastMenu(restaurant).cata({
    Just: breakfastMenuItems => breakfastMenuItems,
    Nothing: () => console.log('Not found'),
})

Great. Pretty simple? Right?

Check out the code below.

// breakfastMenu.js
import { Maybe, get } from 'pratica'

const hasBreakfastMenu = get(['menu', 'breakfast'])

/**
 *  hasSizes & hasOptions return us a Monad. 
 *  In this exampe we will see how Moands can be implemented in our UI.
 *  Using Monads will free us from using if / else statements in our UI Components.
 * */

const hasSizes = sizes => Maybe(sizes).chain(sizes => get(['sizes'])(sizes)) // Returns a Monad
const hasOptions = options => Maybe(options).chain(options => get(['options'])(options)) // Returns a Monad

const safeBreakfastMenuItems = breakfastMenuItems => breakfastMenuItems.map(
    items => items.map(item => ({
            ...item,
            sizes: hasSizes(item), // Returns a Monad
            options: hasOptions(item) // Returns a Monad
        })
    )
)
// Entry point
export const breakfastMenuItems = compose(safeBreakfastMenuItems)(hasBreakfastMenu)

Lets break this up into 3 sections.

First, let's focus on export const breakfastMenuItems. This is our entry point function that implements a compose and some neat point free syntax. We are composing 2 functions that return us a safe data set that we can use in a UI component. As you can see, there is no if or else, no mutability and no variable assignment.

Secondly hasBreakfastMenu uses get to check for the presense of menu.breakfast. Get returns us a Maybe Monad. If menu or breakfast are not found the result will be Maybe.Nothing. The rest of the code execution will not fire.

Finally, safeBreakfastMenuItems the purpose of this code is to check for 2 fields sizes and options, which may be null or undefined. We wrap the fields in a Maybe so we can check the results in a safe way without any unexpected side-effects.

Now, I will show how we can use the output of the above code in a React UI Component.

import { React } from 'react'
import Options from './Options'
import Sizes from './Sizes'
import { breakfastMenuItems } from './breakfastMenu'
import restaurant from './restaurant' // Restaurant object data found above.

 /**
 *  This is not necessarily how I would go about calling this function...
 *  It probably belongs in a reducer. But I think it is important to show how we get the result.
 * */

const breakfastMenu = breakfastMenuItems(restaurant)

const MenuItem = ({ item }) => 
<div>
    <h1>item.name</h1>

    // Here we avoid using `if else`, instead we unwrap our Monad
    {item.options.cata({
        Just: options => <Options options={optons}/>,
        Nothing: () => false
    })}

    // Here we avoid using `if else`, instead we unwrap our Monad
    {item.sizes.cata({
        Just: sizes => <Sizes sizes={sizes}/>,
        Nothing: () => false
    })}

</div>

const MenuItems = ({ breakfastMenu }) => breakfastMenu.cata({
    Just : items =>  items.map(item => <MenuItem item={item}/>),
    Nothing : () => <div>No breakfast menu offered</div>,
})

const App = () => <div> <MenuItems breakfastMenu={breakfastMenu} /> </div>

So what are some take aways that I would like to pass on here.

Composition
No use of if / else.
No imperative code.
Monads Monads Monads.

Check out Pratica! It's neat!