Introducing Mappy

During my nice little break last week I figured, why not? I'll make my toy programing language more real! The result is a functional programming language that is similar to Lisp, except maps (aka dictionaries, aka HashMaps, aka Hashes) are the core primitive, rather than lists.

You're probably thinking to yourself, "what's the point in yet another Lisp-like language?" Well, that's a great question! Mappy's really a breakable toy for my amusement (i.e. in its current state, Mappy's definitely not ready for production). That being said, here are some interesting design choices in the language

• I decided to go with maps rather than lists, because maps are more closely related to functions
• Keeping expressions simple and singular (a la Lisp) makes parsing and grammar rules trivial
• (Bias alert) Haskell is an amazing language in which to implement compilers
• I didn't want to implement if as a core primitive, so I had to choose between non-strictness and auto-closure function arguments (the latter won for simplicity reasons)
• Parsec and QuickCheck can really save you when you're trying to keep complex rules consistent (e.g. parsing)
• Github issues and milestones are an excellent way to break a problem into small chunks and really focus
• Implementing IO as a map has had constraining effects (no pun intended) that are similar to the IO monad

If you're interested in contributing, have a peek at the issues or feel free to play with it, see the README, and/or file some issues!

Trie in Haskell

Lately I've been playing around with Haskell. As an exercise, I decided to partially implement a Trie. I ignored the various implementations out there, including Data.Trie and the one linked on Wikipedia. Instead I focused on iterating on a Trie from scratch, and I found the results to be pretty interesting, so I'm sharing them here.

My real goal with this exercise was to implement "member", "insert" and a sorted "toList" and to do so somewhat generically. This interface turns out to be more similar to a Set than say a Map, because there aren't values associated with members. I used [a] to represent a member of the Trie a which, in retrospect, looks like a Monoid. Well, anyways, my first structure came out looking like

data Trie a =
  RootNode [TrieNode a]
  deriving Show

data TrieNode a =
  Leaf a
  | SpineEnd a [TrieNode a]
  | Spine a [TrieNode a]
  deriving Show

In this modeling, Leaf a indicated the end of a member at a leaf, SpineEnd a [TrieNode a] indicated an end on a spine, Spine a [TrieNode a] was a non-ending spine, and well RootNode [TrieNode a] indicated the root. At first glance, I really liked this model. After implementing the Trie, however, I found the structure less than desirable for a few reasons

• Since "edges" are a list, a fair amount of boilerplate traversal code was necessary to implement the operations
• Although at first I liked keeping RootNode separate, but later I realized it was inhibiting me from inserting the empty list
• Turns out that Leaf a is totally redundant with SpineEnd a []

I'm much more pleased with the second structure I came up with

import qualified Data.Map as M

type TrieEdges a = M.Map a (Trie a)

data Trie a =
  Node { edges :: TrieEdges a }
  | EndNode { edges :: TrieEdges a }
  deriving (Show, Eq)

empty :: Trie a
empty = Node M.empty

Not only does this design have fewer parts than the other, but it yielded a simpler implementation. Here's the code for insert

insert :: Ord a => [a] -> Trie a -> Trie a
insert [] n = EndNode $ edges n
insert vs (Node m) = Node $ insertBelow vs m
insert vs (EndNode m) = EndNode $ insertBelow vs m

insertBelow (v:vs) m = M.insert v (insert vs child) m
  where child = M.findWithDefault empty v m

I believe it's pretty straightforward. The only real tricks were safely creating edges where none existed (which is the main purpose of insertBelow) and ensuring that the node at the end of a member is an EndNode. The member function turned out even nicer

member :: Ord a => [a] -> Trie a -> Bool
member [] (EndNode _) = True
member [] (Node _) = False
member (v:vs) n = maybe False (member vs) . M.lookup v $ edges n

Getting an in-order toList was a little bit tricker but, thanks to the useful functions in Data.Map it was quite doable

toList :: Trie a -> [[a]]
toList = go []
  where
  go acc (Node m) = continue acc m
  go acc (EndNode m) = reverse acc:continue acc m

  continue acc = concatMap (\(v, n) -> go (v:acc) n) . M.toList

In conclusion, if you have any comments, improvements or tips to make this better let me know!

Object Oriented Clojure Example

Inspired by the message passing content in The Structure and Interpretation of Computer Programs (SICP), I decided to try my hand at object oriented-style programming in Clojure. Here's what I came up with, using the traditional bank account example

(defn make-account [initial-balance]
  (let [bal (ref initial-balance)
        withdraw (fn [amount]
                   (dosync (alter bal #(- % amount))))
        deposit (fn [amount]
                  (dosync (alter bal (partial + amount))))
        amount (fn []
                 (deref bal))
        reset (fn []
                (dosync (ref-set bal initial-balance)))]
    (fn [meth & args]
      (cond
        (= meth :withdraw) (withdraw (first args))
        (= meth :deposit) (deposit (first args))
        (= meth :amount) (amount)
        (= meth :reset) (reset)))))

Overall, it was a fun little bit of code to write! It has a constructor (make-account), a private variable with mutation (bal) and some messages it responds to (:withdraw, :deposit, :amount and :reset).

Here's an example of it being used

(def account (make-account 1000))
(println (account :amount))
; -> 1000

(account :withdraw 75)
(println (account :amount))
; -> 1925

(account :reset)
(println (account :amount))
; -> 1000

Functional Programming Aha! Moments

In the past couple of years, I've dedicated a fair amount of time to closet-functional-programming. Although I haven't gotten an opportunity to use a more purist functional programming language (e.g. not FrameWorkOfTheDay.JS) in my day-to-day day, industry work, I believe some of the values of functional programming have bled into my daily practice, for the better.

Industry aside, I want to share some of the "Aha! moments" I've had while learning about functional programming. These are moments where something just clicked for me; some part of me almost can't help but share them.

Lets Can Be Described by Anonymous Functions

Although "functional programming" is one of those things were if you ask five people for a definition you are likely to get six different definitions, one general consensus seems to hold: assignment should be reduced, minimally scoped or eliminated entirely in functional programming.

The let macro/expression/sugar is basically a means of reducing assignments into minimally scoped, (generally) non-mutative expressions with a set of bindings. Here's a contrived example of what this might look like in Clojure

Here we're saying, let's bind `x` to `35` then `y` to a value calculated from `x`, then we'll use `y` to calculate some result. This entire expression is just that, it's an expression. This `let` is evaluated as a whole, and the result is simply `42`.

So, here comes the first "Aha!" This same kind of scoped assignment can be done through applying anonymous functions! Here's what that looks like for the above example

Basically the pattern here is just, for each bound symbol (in this case `x` and `y`) nest and call an anonymous function, passing the bound value down (`35` and `(- x 14)`)! I found this discovery exceptionally cool because it further emphasized the power of these functional languages: something as simple as anonymous functions can be combined to form powerful abstractions. 

Monadic Bind Is Like Method Chaining

Monads, in general, have provided many an "Aha" for me. They're definitely one of those constructs where, once you get passed the initial "this is slightly out of my comfort zone" feeling, you are ready to embrace an overwhelming amount of power.`bind` (looks like `>>=`) is one of the crucial operations implementable by a monad, it has the following type signature

Ignoring currying and some other subtleties, if I'm thinking in an "object oriented mindset" I might reason about this as follows:

• `bind` is a function that take 2 arguments
• a generic wrapper around some type `a`
• a function which takes some `a` and returns some generic wrapper around type `b` (where `b` may be the same type as `a`)
• `bind` returns some generic wrapper around type `b`

To me, this sounds exactly like a single call that enables method chaining! Think a la calling `bind` to transform from monad to monad to monad... In my mind, `bind` is an enabling feature, that allows Haskell code to be elegant, expressive and powerful without lacking type safety (see `do` notation).

To visualize how this is kind of like method chaining, observe the following Ruby code

We can imagine these calls (with the exception of `count`) being like a type-not-so-safe version of Haskell's `bind` applied a couple of times (2 to be exact). Here are what the steps might look like

1. `m a` is a range of `Fixnum` (e.g. `Range Fixnum`)
2. `map` applies a block that takes the `Range Fixnum` and returns an `Array Fixnum`
3. `select`, with its block, takes an `Array Fixnum` and returns an `Array Fixnum`
4. Finally, `count` is simply applied to the `Array Fixnum`

Message Passing (OOP Style) Can Be Achieved via Closures

Disclaimer/Plug: this last "Aha" is shamelessly ripped off from The Structure and Interpretation of Computer Programs (SICP). I am over half way through this book, it is wonderful, please consider showing the authors your support by buying it.

The authors of SICP take the reader through a fantastic journey in which the powers of LISP and functional programming are clearly displayed through examples in the Scheme dialect. One piece of this journey that recently blew my mind was when the authors used closures to define a mutable bank account that responds to different messages. Here's the code (again shamelessly ripped)

What you're seeing here is basically a constructor that builds objects, given a beginning balance, that respond to the `'withdraw` and `'deposit` messages.

Frankly, I don't really know what I can say about this that the authors haven't already said (1) more articulately, (2) more clearly and (3) in a more inspirational manner.

In conclusion, these are just a few of the awesome concepts I've picked up in my pursuit of functional programming. If you have any thoughts on these, or my description of them, don't hesitate to comment.

OOP Setters Can be Used to Emulate Partial Application

Recently I was asked an awesome question that went something like

How would you do something like high-order functions and partial application in object-oriented programming?

For high-order function my mind immediately jumped to Guava's Function Interface. I said, "hmmmm, let's see, could have some method (maybe called partiallyApply) that took an argument and returned another Function." In retrospect, this may have been overly complex, and a much simpler implementation of Function may work just as well in this case: fluent setters.

Let's look at a contrived, dead-horse-esque example. A partial function that does addition on two arguments.

In Haskell, if I wanted to build such a function, and partially apply it to, let's say 5, I might do the following

add5 = (+) 5

add5 10 -- is 15

In Clojure, this might look like

(def add-5 (partial + 5))

(add-5 10) ; is 15

So, how would I do this using setters? Simple! Here's some Ruby code

class Adder
  def value(first)
    @first = first
    self
  end

  def to(second)
    @second = second
    self
  end

  def add
    @first + @second
  end
end

adder_of_5 = Adder.new.value(5)

adder_of_5.to(10).add # is 15

This code (obviously) has a lot more ceremony wrapped around it, but it does achieve some of the same benefits as partial application (e.g. laziness, partial parameter fulfillment). The point is, if this were Java code, I could easily implement Function and change add to invoke and have a partial function in an object-oriented system.

LISP Core in Less Than 100 Lines of Haskell

A couple of months ago, I built a LISP core engine in about 100 lines of Haskell code (of course, just for the fun of it). I thoroughly enjoyed the challenge, and with the help of techniques from the awesome Programming Languages MOOC I was taking, I felt ready to take it on. In conclusion, it was truly a fun project and I thought I'd share some things I learned along the way.

LISP's Core Primitives are Easily Implemented Recursively

In the simplest terms, the LISP core engine I built is simply a function that operates, with a specific environment (variable bindings) in mind, on the LISP syntax tree. Because of this I was able to implement primitives like label (aka define) simply with pattern matching and the cons (: in Haskell) operator!

To show how simple these primitives were to define, here's eq? (checks equality)

aux env (AList (Atom "eq?":a:b:_)) =
  if aux env a == aux env b then aTruthyValue else theFalseyValue

Note that aux is the name of the helper function called by the executor.

Haskell Code Can Be Very Elegant

There aren't many languages in which code as elegant as this can be written:

executeText env = execute env.parseMany.tokenize

In my opinion, it doesn't get much more straight forward than this. The dots may throw C-style programmers, but to a Haskell programmer they're pure gold.

Additionally refactoring in Haskell is extremely powerful. Consider the evolution of my bind function (takes names and values and adds them to an environment). It started as this:

bind [] [] env = env
bind (name:names) (value:values) env = bind names values ((name, value):env)

then was transformed to this:

bind names values = (++) $ zip names values

and ended up as:

bind names = (++) . zip names

In Haskell, it seems, there is a function for everything. Honestly, there's probably even one out there that can replace my bind function, I just haven't found it yet!

The Macro System is Pretty Cool

At the moment, the macro system in this LISP is pretty tight. Macros are written in Haskell code (I would like to eventually add support in the language) and are provided with (1) and "eval" which encapsulates the current environment and can run code and (2) a list of the arguments passed to the macro.

All registered macros are simply added to a list, and are thus loosely coupled to the actual core engine (but tightly coupled to the AST since they are essentially generating new portions of it).

Here's an example of how I defined if, in terms of the cond primitive:

structuralMacros = [(
  "if", \_ (p:a:b:_) -> AList [Atom "cond", p, a, Atom "1", b]),
  ...]

Parting Words

If you're interested in the full code, it's on github. Also the project has a REPL whose build step is at the bottom of "README.md."

What Is A Monad?

Being a hobbyist Haskell programmer, I have heard the term "monad" a lot. In my experience playing with Haskell I have used monads plenty of times, however, it was not until recently that I have come to a digestible understanding of what they really are.

Think Method Chaining

Some of the prominent phrases which I hear being used to describe monads are "they're ways to fake state" and "they are really just a form of method chaining." Although, in my (perhaps nieve) understanding of monads, both of these statements are true, the latter has been far more useful in helping me arrive at a useful understanding of "the m word." So I encourage anyone who may be struggling with the definition of a monad to do the same: think method chaining.

Method Chaining You Say?

Yes method chaining. In the object oriented world this may mean something like this:

someObject.someMethod(1)
          .otherMethod("Pizza")
          .finalMethod()

So, in OOP, the objects returned by each of these methods would encapsulate state. Now, in Haskell, there is not really a concept of state, things are what they are. The sequential mutilation of objects is not something Haskell supports naturally, so it uses the monad as a slick way to sort of "fake state."

What It Looks Like

Disclaimer: this is my current understand of Haskellian monads, and not the similar but slightly different, mathematically definition of monads

To build a monad, two main functions are necessary as well as a monadic type. First I'll discuss a monadic type.

Monadic Type

A monad's type can be whatever it needs to be. Perhaps one of the most famous ones in the Haskell world it the Maybe monad, which is defined simply as:

data Maybe a = Nothing | Just a

Maybe is one of the most beautiful aspects of Haskell. It is very similar to null or nil in other languages, but what makes it different is the fact that (as I understand it) in Haskell's pure, functional model, Maybe cannot go unhandled or pop up in unexpected places. In my mind, it is a kind of a neat and precise example of a monadic type.

The return Function

Another thing a monad needs is a return function whose signature looks like:

return :: a -> m a

return is simply a function whose purpose is to construct the monadic type. Pretty simple, eh? So for Maybe, this might be as simple as:

return n = Just n

The Bind Function

The other function needed by a monad, the function that truly brings out the magic, is the bind function which is usually denoted as (>>=) in the Haskell world. In the OOP example above, the bind function is kind of like the periods in between the different calls, but oh so much more magical. Bind's signature looks like:

(>>=) :: m a -> (a -> m b) -> m b

So, let's break this down.

The first thing that bind takes is a monadic type. So, this could be something as simple as Just 5 or whatever monadic type you are operating on. The second parameter is a function that takes the type boxed by the first parameter (the monadic type) and returns a monadic type boxing b (which could be the same type as a but by no means must be). In the end, bind returns another monadic type, as returned by the middle parameter.

All in all, this seems like a lot to swallow, and, uh, what does this have to do with method chaining or our return function?

Remember, bind is really one of those strange infix operators, so if I may make some simplifications, it kind of looks like:

a thing >>= function that returns another thing

In this simplification, "thing" is substituted for "monadic type" to make bind easier to swallow. The point is, all this whole mess does is return another monadic type! So, there's nothing keeping me from implementing another bind operator (or reusing the same one, if applicable) like such:

a thing >>= function that returns another thing >>= function that returns yet another thing ...

See what I mean about this being like the "period between" in that above OOP example? All bind really does is take some value (wrapped in a monad) and apply some function to it, and re-wrap the output!

return is pretty cool because a lot of the time it comes at the end of all the binding (wow, a return at the end? Sounds like some other paradigms out there). return is really the end game, the termination of the "chaining."

Parting Words

In conclusion, I hope I have shed some light on what can be a very difficult topic to understand. If you would like to learn more, the Haskell community has a great article on monads also there are some really awesome answers to the question of "what is a monad" on SO.

Determinant in Haskell

In linear algebra, the determinant is quite a useful operation that can be done on matrices. To further my understanding of Haskell, I decided to program a solver for systems of equations. One of the best ways to do this dynamically is through Cramer's Rule which needs to be able to calculate determinants. So, here's my recursive code for finding determinants:

determinant :: (Num a, Fractional a) => [[a]] -> a

determinant [[x]] = x
determinant mat =
 sum [(-1)^i*x*(determinant (getRest i mat)) | (i, x) <- zip [0..] (head mat)]

So, in this code, the base case is a 1x1 matrix. The getRest function simply returns the matrix without the head row (topmost) and without the \(i\)th column.

The code and tests are available on my github.

Creating a Sine Function in Haskell

Using Taylor Series derivation I found the following infinite sum expression for sin:
\[
  \sin \left(x \right) = \sum_{i = 1}^{\infty} \frac{x^{2 i - 1}}{\left( 2 i - 1 \right)!} \left( -1 \right)^{i - 1}
\]
The exact derivation is available as a PDF on github.

The translation of this sum into Haskell code was simple:

sin' :: (Num a, Fractional a) => a -> a
sin' x = sum [sinTerm x i | i <- [1..33]]


sinTerm :: (Num a, Fractional a) => a -> Integer -> a
sinTerm x i = (x^oddTerm / fromIntegral (factorial oddTerm))*(-1)^(i-1)
  where oddTerm = 2*i - 1

So, this code is pretty straight forward, if you wanted to get more accuracy on the results you could change "33" to be some greater value (33 says that we will sum up 33-1=32 terms of the taylor series).

Of course this code references factorial which is defined simply as:

factorial :: Integer -> Integer
factorial 1 = 1
factorial n = n * factorial (n-1)

As usual, code and tests are available on github.

Nieve Prime Finder in Haskell

To solve a cyber-dojo challenge (implement a function/method that returns the prime factors of a number) I decided to implement a somewhat nieve (but workable) isPrime function in Haskell. Here's the code:

-- Public type-definition
isPrime :: Integer -> Bool

-- Private type-definition
lookForPrimeFrom :: Integer -> Integer -> Bool

isPrime 2 = True
isPrime n
 | n < 2     = False
 | even n    = False
 | otherwise = lookForPrimeFrom n 5

lookForPrimeFrom n i
 | ceiling (sqrt (fromIntegral n))+1 < i   = True
 | (n `mod` i) == 0                        = False
 | otherwise                               = lookForPrimeFrom n (i+2)


This code (to me at least) seems very self-documenting. The more I'm playing around with Haskell, the more I'm enjoying it and seeing its strength as a functional language. I think if I were to map this algorithm into more mathematical notation it would look like:

\[
  \forall n \in \mathbb{N}
\]
\[
  p \left( n \right) = \left\{ \begin{array}{lr}
  0, & n = 1 \\
  1, & n = 2 \\
  0, & \text{$n$ is even} \\
  1, & \nexists m \in \left\{ x \in \mathbb{N} \, | \, 5 \leq x \leq{\sqrt{n}}, \text{$x$ is odd}  \right\}
  
\end{array} \right.
\]

As you can see, this is somewhat nieve; however, the Haskell code really is quite similar to the mathematical notation.

Haskell DSA: Quick Sort

Haskell continues to astound me! I have never implemented the quicksort as simply and, frankly, elegantly as this:

quickSort :: (Ord a) => [a] -> [a]

quickSort [] = []
quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
 where lesser = [e | e <- xs, e < x]
       greater = [e | e <- xs, e >= x]

Here's a quick, line-by-line for anyone who's interested.

• quickSort :: (Ord a) => [a] -> [a]
  The optional (gotta love that word in programming) function definition. It basically says that quickSort is a function that takes a list of objects, [a] and returns another list of a. Ord a means that a is ordinal, or, as far as we're concerned, sortable
• quickSort [] = []
  The first pattern we're trying to match -- if we're given an empty list, return an empty list!
• quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
  This line does a few cool things: (1) split up a passed list into a first element and remainder, then (2) return the lower ordered elements and the higher sorted on either sides of the first element!
• where less = [e | e <- xs, e < x]
      greater = [e | e <- xs, e >= x]
  This where clause uses list comprehensions to build and define the lists of lower and higher ordered values. Note that the higher values are also (if the case may be) equal to the head of the list (also know as the pivot).

Maybe, Just and Nothing (More Bragging on Haskell)

Man, this Haskell thing is pretty cool. One of (in my opinion) the most annoying things that a programming paradigm can do is consider unexpected behavior to be normal behavior. For instance, most list searches return -1 when the element you are looking for does not exist. Does returning -1 makes sense? No... Not really. Well, anyways, Haskell defeats this type of thing with the following line (this comes with the standard library):

data Maybe a = Nothing | Just a  

Basically all it means is, there's this data type called Maybe (remember, uppercase means constant) and when it is given a type it may just return it or it may return nothing!

This tool is one of the coolest things I have seen in Haskell, thus far. What is the power in this? You can make functions with expected behavior! For instance, consider this quick, binary search I built:

binarySearch :: Ord a => [a] -> a -> Int -> Int -> Maybe Int

binarySearch l e beg last
 | lookat == e = Just i
 | i == (length l)-1 || i == 0 = Nothing
 | lookat < e = (binarySearch l e i last)
 | lookat > e = (binarySearch l e beg i)
 where i = quot (beg+last) 2
       lookat = l !! i

The Maybe, Just and Nothing allow the function to be loose enough that the function can respond with ,"I couldn't find what you were looking for; I found nothing!" This seems to be a huge plus of Haskell. I don't know of many strongly-typed languages that allow this level of Dynamicity.

Functional Fibonaccis in Haskell

Lately, I've been learning my first functional programming language: Haskell. Thus far, it is truly awesome! Look at the following Fibonacci function (I know it's a dead-horse example):

nthFib :: (Integral a) => a -> a
nthFib 1 = 1
nthFib 2 = 1
nthFib n = nthFib (n-1) + nthFib (n-2) 

So, "What makes this simple Fibonacci example so awesome?" you may ask. Well, there are a few things I really like about it, but the main thing is that it actually looks like the mathematical definition for the Fibonacci Series! Also, that first line looks a lot like "nthFib: Z -> Z", you know, that good-old-mathy notation meaning, "nthFib is a function that maps an integer to an integer" (I know, I know, the first 'a' should be a natural number, I'm still getting there). But this is wicked stuff!