Functors, Applicatives, and Monads

http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html


Today I found this really great page through the Computer Science Twitter. IT does a really good job of explaining functors, applicatives, and monads in Haskell. It's a good way to brush up on your functional programming! It's worth a read, and it's done primarily through pictures so if you're a visual learner like I am, you'll have a blast.

How to make a patch using git and apply it! C binary file.

As I was walking home from work today I got to thinking about patch files for some reason. Don't ask me, I just did. So I'm walking along, and thinking about how git has patch files as pretty simple things of add this in, take this out. Do that a bunch of times and poof. And I know what it looks like for source code. But then I also entertained the thought about executable files.

So without further a due:

First let's make a directory and hop into it.

Next, let's make our C file

Now compile the program...

Now comes the fun part. Make a new repository and commit it

Now let's make a change to the program

Now recompile the program and check out the status of our repository

We can see that we've modified everything (because we have) and that git is keeping track of our binary for us. So now how do we make a patch? Well, the easiest way to do it is to put these changes on another branch. This will let use some really easy to follow commands. So let's do that.

Next, I'll clear my console with clear and then create the patch. Because I'm alternating between a fullscreen guake terminal, and this blog post I get some weird spacing and the actual patch command to make a bazboz patch file from our current branch is about halfway down the screen.

Now, something you might notice is that since I've been using git add . I've not only added the binary file to the patch, but also the changes to the source code. If I was maintaining some type of non-open source project, or it was a configuration file that wasn't ignored for whatever reason, I would have only added the binary file to the patch. Not a big deal, but just something to take note of. To actually apply the patch file we've made, lets go ahead and switch to master

you might notice I'm already on master, that's just because I switched over in a separate terminal window and was testing the commands I was doing first, that way this little tutorial stays clean.  Once I've switched to the master branch I check to see if the patch is going to fail. Since no warnings or errors pop up from the check option from apply. We can go ahead now.

We could have applied the patch with git apply but if we use git am we sign off on the patch so that everyone who helps us maintain our code can point their fingers at us when something goes horribly wrong and our code is at fault. 

And that's all there is to it! Note that this is a pretty minimal example, and to be honest a patch really isn't necessary at all. If I were just grabbing a commit from another branch I would use git cherry-pick and select the hash of the commit I wanted to grab. But, if you were working on a project like, Drupal or some other large open source and you contributed to core modules and such, they'd probably want to take a patch to make it easy on them to integrate your changes. 

I didn't go into too much detail about anything I was doing I don't think, and if you want a more detailed explanation with a bit more time spent, I recommend This tutorial by Ariejan de Vroom

If you were emailed this patch file, you'd cd to your repository, checkout to your master branch (or whatever branch you want to apply the patch to) and then run the git am commands after dropping the patch file into the directory. Easy!

Easy Problem of Satisfiability

Problem:
  Given an expression consisting of AND,OR, and NOT gates, determine whether or not the output of the circuit can be made high. That is, the circuit has I inputs, N gates, and 1 final output.

Solution:
  I have one. This problem was described to me as the natural NP problem. Yet, it is extremely easy to solve in linear time at worst. Which confuses me. An NP problem should take sub-exponential or exponential or worse time to complete. Yet the algorithm I have come up with (I swear it's not in the margin of my notebook, actually takes up just a page) finds not only if the circuit is satisfiable but also implicitly gives back the neccesary input to cause the circuit to output low. Another caveat of my algorithm is that it can be used to find a way to cause a circuit to return low as well. It is very general, and the algorithm itself takes up only 150 lines of code or so. It's a beautiful recursive descent.

I'm meeting with my professor in a half hour to go over it with him. And after this, I will know if I have found a solution to the NP problem of Circuit satisfiability or if I missed the problem definition in some way and merely solved a problem similar, yet easier.

If all goes well, I'll post my algorithm later on today.

The Smart Desk

https://github.com/EJEHardenberg/SmartDesk

I've started a new project! Working on it with one of my friends who graduated last year, he's working on the Networking component and I'm working on the graphical component. It's a very promising idea in my head, and will get a lot of experience with system programming. I'm looking forward to it.

:)

EEG and Cairo

Using the outline in this video:
http://www.youtube.com/watch?v=ZmxmeRry2uY

And an arduino board from a friend, I plan to create a small program that will display the output of the eeg onto the screen.

As my recent kick is with C, I think I'll do that. My current plan is to create a couple different programs, one that handle the graphics and another that will handle getting information from the eeg. That way I can develop  one while I assemble the EEG. I think I'll be using Cairo Graphics or OpenGL not sure which yet, I've selected Cairo because it seems like its easy to work with from the examples I've seen. And then I'll have a memory mapped file, or named pipe between the two programs so that they can share data quickly and efficiently.

http://www.linuxquestions.org/questions/programming-9/mmap-tutorial-c-c-511265/

Hopefully this all works out nicely, and if I don't manage to assemble an EEG, then at least I've worked with graphics and memory mapped files. Which I think could become a key staple to learning some parrallel processing techniques.

Brain Fuck Interpreter. I made one

https://github.com/EJEHardenberg/BF_Interpret

So After a couple of days I've scrapped together my small amount of knowledge of C and created a BrainFuck interpreter.

It was pretty simple since all you're really doing is manipulating a Turing Machine. But creating the interactive bits was fun and a good thought exercise.

There are a few ways to run it once you've compiled it.

Just run it with no arguments:
Gets you the interpreter. Where you can type in all the BF commands you'd like, or comments as long as they don't include 'q' becuase 'q' is the quit key.

arguments of -f filename will read in a file and that file will be fed to the BF translator and outputted according to whatever program you decide.

arguments of anything else: will be taken as BF code and interpreted.

It's a pretty basic program, but it was a good exercise, and I'm going to refactor the code a bit. A friend of mine pointed out that the headers should be just declarations and not full blown source code.

KD Tree Range Bounded Algorithm

Searching a K-d Tree is simple enough, its just a basic binary search based off the axis you're splitting by on your nodes. Doing a nearest neighbor search is one of the most basic operations you can do on a K-d Tree and is typically what you use this type of tree for. But because of the geometric properties of the tree itself and how each node creates a splitting plane for the space, we can make an awesome algorithm that returns points in the tree that are within a specific region of space.

This is for a 2 dimensional tree and space, but could be extended to 3 easily, and probably up to k dimensions after having a headache for a while:

So First off we need to be able to define a Region in space. Because the K-d Tree splits on planes, essentially we're going to define a box in K space, so it makes sense to have our regions be square in some fashion. So here's the code to construct a region:


public class Region{

double xleft   =  -Float.MAX_VALUE;
double xright  =   Float.MAX_VALUE;
double ybottom =  -Float.MAX_VALUE;
double ytop    =   Float.MAX_VALUE;


//Creates a region containing the entire coordinate plane
public Region(){
}


//Creates a Region defined by the four locations of its sides
public Region(double left, double right, double top, double bottom){
//Assume we might mess up and not put them in the right order for lefts and rights
if(left < right){
xleft = left;
xright = right;
}else{
xleft = right;
xright = left;
}
if(bottom < top){
ybottom = bottom;
ytop = top;
}else{
ybottom = top;
ytop = bottom;
}
}

}

I've made some assumptions about not being able to tell my left from my right but the key point that we'll take advantage of in the algorithm later is that a Region's default is to be the entire coordinate space. Next we need to add some helping functions to alter the region

public Region setLeft(double left){
this.xleft = left;
return this;
}

public Region setRight(double right){
this.xright = right;
return this;
}

public Region setTop(double top){
this.ytop = top;
return this;
}

public Region setBottom(double bottom){
this.ybottom = bottom;
return this;
}


//Checks to see if this Region contains the point
public boolean fullyContains(Node node){
float y =node.getY();
float x = node.getX();
return ybottom <= y && y <= ytop && xleft <= x && x <= xright;
}

public boolean fullyContains(Region r){
return xleft <= r.xleft && r.xright <= xright && r.ytop <= ytop && ybottom <= r.ybottom;
}

public boolean intersects(Region r){
return !(xright < r.xleft) && !(r.xright < xleft) && !(r.ytop < ybottom) && !(ytop < r.ybottom);
}

Now it's important that the setLeft,Right,Top, and Bottom sections return a Region, we'll see why in a bit. But the more interesting part of this code is the intersects function. To see if two Regions intersect, you could do an 8 part boolean expression checking all the possible combinations of the two Regions intersecting. OR you can be clever about it. The expression to see if two Regions don't intersect is far easier than the larger expression we just talked about. You just check if it's right side is strictly less than the other regions is the left side. You do this for all 4 sides and then you negate the expression. By deMorgans laws your OR's become not ands and pow. Your intersects function is quick, efficient and done. Now lets get to the actual algorithm:

private ArrayList<Node> boundedSearch(Region sRegion,ArrayList<Node> results,int depth,Region bRegion){

int axis = depth % coordinates.length;

if(this.isLeaf()){

if(sRegion.fullyContains(this)){

results.add(this);

}

}else{

//Subtree we need to redefine our bounding region bRegion

if(axis == 0){

//We are splitting on the x axis

if(sRegion.fullyContains(bRegion)){

//We are in the region so we report ourselves

results.add(this);

}else{

if(sRegion.fullyContains(this)){

results.add(this);

}

}

if(sRegion.intersects(bRegion)){

if(this.left != null){

//Search down the left with our splitting line as a bound on the right

return this.left.innerBoundedSearch(sRegion,results,depth+1,bRegion.setRight(this.getCoordinate(axis)));

}else{

//Null link return results

return results;

}

}

if(sRegion.intersects(bRegion)){

if(this.right != null){

//Search down the left with a splitting line as a bound on the left

return this.right.innerBoundedSearch(sRegion,results,depth+1,bRegion.setLeft(this.getCoordinate(axis)));

}

}

}else{

//We are splitting on the y  axis

if(sRegion.fullyContains(bRegion)){

//We are in the region so we report ourselves

results.add(this);

}else{

if(sRegion.fullyContains(this)){

results.add(this);

}

}

if(sRegion.intersects(bRegion)){

if(this.left != null){

//Search down the left with our splitting line as a bound on the right

return this.left.innerBoundedSearch(sRegion,results,depth+1,bRegion.setTop(this.getCoordinate(axis)));

}else{

//Null link return results

return results;

}

}

if(sRegion.intersects(bRegion)){

if(this.right != null){

//Search down the left with a splitting line as a bound on the left

return this.right.innerBoundedSearch(sRegion,results,depth+1,bRegion.setBottom(this.getCoordinate(axis)));

}

}

}

}

return results;

}

Alright, (one day I'll figure out how to display code nicer on these blog posts.) Let me describe how the algorithm works. The basic idea is that as you recurse down the tree, the splitting planes of the node you're visiting becomes a sides of a bounded region. This bounded region begins as the entire coordinate axis, then becomes half of that, then half of that, and etc etc. So each time you're creating a smaller and smaller space in which nodes can exist. Once this bounded region is contained within the search region, then we can report that entire sub tree as being contained. If we reach a leaf node, its a simple check to see if it is contained within the tree. 

I find that thinking of this geometrically is much easier than staring at just the code and trying to understand what it does. There is some work you have to do after the results is returned. You do need to collect all the leaves in the subtrees and add them to the results. 

public  ArrayList<Node> collectTree(ArrayList<Node> results){

//Traverse the tree and put all children in there

if(this.left!= null){

results = this.left.collectTree(results);

}

if(this.right!=null){

results = this.right.collectTree(results);

}

if(!results.contains(this)){

results.add(this);

}

return results;

}

Once you've collected these lists for each node you do need to add all together. But why write an arraylist merging function when you can do it all at once with a flatten. Observe:


private static ArrayList<Node> flatten(ArrayList<Node> nodes){
//Flatten each nodes subtree out.
ArrayList<Node> temp = new ArrayList<Node>();
for(Node node : nodes){
temp = node.collectTree(temp);
}
return temp;
}

Once you have this, its easy to collect the results of your search and report all of them in one list to a client. There is one important thing I'd like to mention though, in the collectTree function, notice the containment check at the end. This ensures no duplicate nodes are added to the list. If you didn't have this, you would report the subtree of any subtree returned by the search at least twice. Or precisely, the leaves would be reported for whatever depth they were away from the subtree that was reported.


The project I've used this in is located at:
Tree Class
Region