Umair’s blog

Thoughts about programming and technology

Applicative Laws for ((->) r) Type

This is Part-3 of my series on verifying Applicative laws for various Haskell types. Here are Part-1 Applicative Laws for Maybe Type and Part-2 Applicative Laws for [] Type


Haskell’s function type ((->) r) is an Applicative functor. Similar to the previous two posts in this series, in this post I will verify that the applicative laws hold for the ((->) r) type.

For reference, ((->) r) is made an instance of the Applicative class as:

1
2
3
4
5
6
7
8
9
10
instance Applicative ((->) r) where
    pure x = (\_ -> x)
    -- pure can also be written as:
    -- pure x = const x

    -- (<*>) :: f (a->b) -> f a -> f b
    -- (<*>) :: ((->) r (a->b)) -> ((->) r a) -> ((->) r b)
    -- (<*>) :: (r -> (a->b)) -> (r -> a) -> (r -> b)
    -- the entire lambda has type r -> b, which implies x :: r
    (<*>) f g = (\x -> f x (g x))

Applicative Laws for [] Type

This is Part-2 of my series on verifying Applicative laws for various Haskell types. Part-1 is Applicative Laws for Maybe Type.


Haskell’s list type [] is an Applicative functor. Similar to the previous post, this post will verify that the applicative laws hold for the [] type. For reference, [] is made an instance of the Applicative class as:

1
2
3
instance Applicative [] where
    pure x      = [x]
    (<*>) fs xs = [f x | f <- fs, x <- xs]

Applicative Laws for Maybe Type

Applicative functors come with a set of laws that apply for all Applicative instances. These laws are as follows:

  • Identity: pure id <*> v = v

  • Homomorphism: pure f <*> pure x = pure (f x)

  • Interchange: u <*> pure y = pure ($y) <*> u

  • Composition: pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

For more information about these laws, check out this Haskell wiki post.

Maybe is an Applicative functor, and this post will verify that the applicative laws hold for the Maybe instance.

Maybe as an Applicative Functor

Maybe type is made an instance of the Applicative type class as follows (link):

1
2
3
4
instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something

It took me a several attempts before I could parse this definition. I was particularly puzzled by the line (Just f) <*> something = fmap f something. To help me understand this better, I decided to build this definition back up from the very basics.

Pascal’s Triangle

One of the exercises in Structure and Implementation of Computer Programs deals with generating elements of the Pascal’s Triangle. The following pattern of numbers is called Pascal’s Triangle

1
2
3
4
5
6
7

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
...

The numbers at the edge of the triangle are 1, and each number inside is the sum of two numbers above it. The exercise asks us to find the elements of Pascal’s triangle by means of a recursive process.

Index Based List Operations Using folds in Haskell

When working with lists in Haskell, occasionally there’s a need to perform index based operations, such as adding an element at a particular index. Going by my experience, using foldl or foldr is not the first idea that comes to mind when indices are involved. However, there is a general pattern that can be applied when using folds for index-based list operations. For example, consider the case where we need to add an element at a particular index:

→ Talking About Money

Patrick McKenzie wrote an excellent post about compensation and salary transparency. The entire post is really informative, but for me, this passage is a true gem. Every word here is absolutely true:

Compensation negotiations are presently like a stock exchange where only your counterparty can see the ticker and order book. You’d never send an order to that exchange — it would be an invitation to be fleeced. “I happen to have a share of Google and want to sell it. What’s it go for?” “Oh, $200 or so.” “Really? That feels low.” “Alright, $205 then, but don’t be greedy.”

The spot price of Google when I write this is $535. Someone offering $205 for GOOG would shock the conscience. In the years since I wrote a post on salary negotiation for engineers I have received many letters suggesting folks have received and accepted employment offers much worse than that, relative to reasonably achievable market rates.

When you are done reading this post, go and read his post Salary Negotiation: Make More Money, Be More Valued. Really informative and useful.

Sublime Text & Haskell

There are several excellent posts about setting up the Haskell development environment. One of the best ones is Tony Lawrence’s Configuring Your Haskell Environment. I encourage you to take a look at his post first.

Tony’s post is more than a year old though, and it looks like a couple of things have changed since he wrote his post, especially with the latest version of Haskell and SublimeHaskell. I wasted a good chunk of time trying to get around those problems, so now writing this post in case others run into similar issues when setting up the SublimeHaskell plugin.

→ Why Racket? Why Lisp?

A slightly older (from Aug 2014), but nonetheless great post by Matthew Butterick where he enumerates the benefits of learning to program in Lisp (or one of its dialects). Several very smart folks have written about the awesomeness of Lisp, but this is the first post I have read that provides a list of concrete examples of said benefits:

I was hope­ful when I opened Pe­ter Seibel’s Prac­ti­cal Com­mon Lisp and saw that the in­tro­duc­tion was sub­ti­tled “Why Lisp?” Yes, tell me! Seibel echoes Gra­ham’s claim: “You’ll get more done, faster, us­ing [Lisp] than you would us­ing pretty much any other lan­guage.” OK, but how? Seibel won­ders whether “I like Lisp be­cause of some quirk in the way my brain is wired. It could even be ge­netic, since my dad has it too.” That’s not en­cour­ag­ing to those of us out­side your fam­ily. Ul­ti­mately, he sums up the ap­peal of Lisp by de­scrib­ing it as “the pro­gram­ma­ble pro­gram­ming lan­guage.” But I’ve never used a pro­gram­ma­ble pro­gram­ming lan­guage. Why should I start?

And by the way, when do I get the speed and power you keep promising?

In short—what’s in it for me, now?

Book - Hackers & Painters

A couple of days ago, I finished reading Paul Graham’s book of essays Hackers and Painters: Big Ideas from the Computer Age, and thoroughly enjoyed the book. I had already read a few of these essays on his website, yet I still enjoyed re-reading them. This book is tremendously intelligent, insightful and inspiring, and several of these essays (and many passages) are worth re-reading periodically.

Here are some of the essays that I particularly enjoyed: