The Beginning and End.

Applicative Functors

Today at Hacker School, I was studying functors and applicative functors in Haskell. Functors are structures that “can be mapped over” [1]. So, applicative functors are functors that allow functions to be applied within a functor. Functor-ception.

This concept proved to be a pretty difficult one for me to grasp today. I wrangled with it for several hours, reading and re-reading Learn You a Haskell’s explanation for them before I broke down and asked for help on the Haskell Zuplip thread. (Now I know that I should ask for help if I can’t figure something out in 15 minutes on my own.)

The particular problem I was sweating over was writing an Applicative instance for a Parser:

1
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

I was eventually able to come up with this:

1
2
3
4
5
6
7
8
instance Applicative Parser where
    pure x = Parser $ \s -> Just (x, s)
    p <*> q = Parser $ \s ->
            case (runParser p s) of
                Nothing -> Nothing
                Just (f, s') -> case (runParser q s') of
                    Nothing -> Nothing
                    Just (x, s'') -> Just (f x, s'')

Applicative instances have a pure method and a <*> method. Pure is simple enough. It has a type declaration of pure :: a -> f a. Basically, it takes a value of any type, and returns that value wrapped in an applicative functor. Where I had trouble was implementing <*>. <*> has a type declaration of f (a -> b) -> f a -> f b. Basically, it is like fmap, but it takes a functor with a function in it, and another functor. The function from the first functor is sort of mapped over the value in the second functor.

Chen, Hacker School W ‘13, was a saint and guided me in grasping the intuition behind writing this applicative instance. P and q are both functors here. P, however, is the functor that holds a function within it. In order to apply this function to the second functor, he was able to explain to me that I needed to “unwrap” the each functor and pass each state on to the subsequent action. In this case, that would be to call runParser on the functor p and the first state s, which would return a type of Maybe ((a->b), String). This is where the cases come in. The result of runparser p s could either be Nothing or Just (f, s'), where f is of type declaration (a->b) and s' is the second state. In the case of Nothing, we return Nothing because there is nothing to pass on to the second functor. On the other hand, we again run runParser to “unwrap” the second functor. Just as before, in the case of Nothing, we return Nothing. Otherwise, we get Just (x, s''), where x is of type a and s'' is the third state. With this, we can now apply f on x to go from something of type a to type b, and return the third state s'', resulting in Just (f x, s'').

Whew. I definitely learned a ton doing this. I hope my explaination made sense!

Resources
[1] Haskell/Applicative Functors

Hacker School Week 1

"HS Logo"

This past week was my first week at Hacker School, and I am finally getting around to setting up a blog!

I really haven’t had much success with blogging in the past, so I am wondering how this is going to go, but I will try my best to write something everyday. The posts from my fellow batchmates have been very exciting to read, and have been a motivating factor for me to finally get Octopress set up.

Because I had already been working on a course on Haskell that I found online before Hacker School started, that was mainly what I focused on during my first week. The course is broken up into 12 lectures, with corresponding homework assignments. The amazing thing is, I was able to work through about one week’s worth of material per day. It’s incredible what can happen when you are learning for the sake of learning, with no worries that generally come from a work or school setting. If you had told me one year ago that I would be geeking out over Haskell, I would have laughed in your face. I would have thought that it was too academic, too hard of a language for someone like myself to learn. What I am finding though, is that once I commited myself to learning Haskell, once I was comfortable with the idea that I too was capable of learning Haskell, I started to have fun with the assignments.

The most recent assignment I worked on was with using the rose tree data structure from the Data.Tree library. Based on a tree of employees, where employees are given a name and a “fun” score, I was given the task of maximizing the fun score for a party and returning its optimized guest list. The caveat is that if an employee’s direct superior were also in attendance of the party, that employee wouldn’t be able to have any fun, lowering their fun score to 0.

I think my road block for this assignment was implementing a fold function for the tree data type (to which I could pass a function that found the max fun score at each subtree later). I wasn’t sure what the type signature for the fold should have been, which took up the most of my time. Once I got this function worked out, I was able to work through the rest of the assignment.

I wrote the fold as such:

1
2
treeFold :: (a -> [b] -> b) -> Tree a -> b
treeFold f tree = f (rootLabel tree) (map (treeFold f) (subForest tree))

where tree is defined as

1
2
3
 data Tree a = Node {
    rootLabel :: a, -- label value
    subForest :: [Tree a] -- zero or more child trees

The rootLabel of the tree returns the element at that Node and then we map treeFold f to the subtrees of the Node, recursively calling treeFold f on the subtrees. These are then passed as parameters to the function f.


Something else that I did last week was playing with Arduinos and Addressable LEDs (each pixel is individually programmable!). I bought an Arduino UNO a few years ago, and never had really done anything with it. Dana, a batchmate with lots of hardware experience, brought some addressable LEDs in for some of the Hacker Schoolers to play with.

The cool thing was that Adafruit already had a library called Adafruit NeoPixels we could use, so we were able to just hook up the LEDs to the Arduino and we immediately saw a light show.

"HS Logo"

We played around with making the LEDs blink, which we achieved by Mod-ing the number of LEDs, and then changing the RGB value to (0, 0, 0). It definitely distilled the fear of hardware many of us had once we understood how easy it was to get started with it with all of the resources online. I am totally obsessed with Adafruit now!

My hardware project that I would like to accomplish this summer is a temperature sensor that based on the serial output changes the colors of the addressable LEDs. If warm, the LEDs light up yellow/orange, if cool, a green color, etc.

I am loving Hacker School thus far. Well, love is a bit of an understatement.