Quick thoughts on starting Functional Programming (in Racket)

Having been “functionally curious” for a while now, I’ve started with Racket, a language in the scheme family which is a type of Lisp. Yes. Racket rhymes with bracket.

My first foray into functional programming was with Haskell. When I started with Learn You a Haskell for Great Good I was initially excited, but then I got a little confused and this was enough of a barrier that I stopped.

When I came back to trying Functional Programming (almost a year later) I made two changes. I picked a different language (Racket) and I decided that, instead of my usual method of jumping into the deep end by starting a real life project with the language, I would patiently step through the Project Euler problems in that language. The combination of the three seems to be working.

Racket

DrRacket is a very awesome learning tool. It’s what the IPython notebook and the IPython interactive console aspire to be and more. I don’t use the pop-out hints (on the right hand corner) but I make extensive use of searching the documentation for a standard library description, for graphical description of function usages (DrRacket draws arrows from a function definition to its uses!) and for locating errors.

Screen Shot 2015-08-25 at 11.25.49 AM

Here’s a nice use case for this. I copied over a function intending to modify it and make a different version of it (this is part of some learning code, so I like to keep older versions of algorithms around for comparison). By hovering over the older definition and noting the long arrow that goes down into the new (pasted) code I can see that I haven’t changed the function name in one place yet:

Screen Shot 2015-11-05 at 8.54.56 AM

The documentation is very good, though I haven’t run into a user community (Edit: The folks on the mailing list are very kind and helpful!). Perhaps I should wander down to Northeastern U. I started with the tutorial in the guide, but after settling on Project Euler, I abandoned the tutorial and now make extensive but non-linear use of the guide and reference (which is, incidentally, included with the distribution, so I don’t need an internet connection) and stack-overflow.

In terms of syntax, Racket is a bit annoying. It’s fairly easy for me to write, but I don’t like to read it. The polish prefix notation is annoying but strangely addictive. I definitely prefer infix, but there is a perverse pleasure in getting fluent in prefix. The real problem is with the brackets. Perhaps I’ve just not learned how to format things and need to look at other people’s Racket code, but my code is unreadable.

Project Euler

Project Euler seems just the ticket for me getting started with Functional Programming. The problems are paced and are a nice mixture of mathematical theory and code. For each problem I find myself scribbling on paper, thinking a bit and then coding. I really like this. Solving problems in order of difficulty helps me from getting stuck in one place for too long.

Functional Programming

I have to admit learning a new paradigm is a lot more fun than just learning a new language. After a lifetime of coding imperatively it’s a nice challenge to deny myself the easy pleasures of loops and variable assignments (though that takes it a bit far if done strictly). I’m sure there is a lot more to FP, but that is what I’ve picked up doing the first few Euler Project problems.

Using list comprehensions in Python (which are implicitly map and/or filter) has made the concept of map and reduce very easy to grasp. (As an aside, I really like Python’s syntax for list/dictionary comprehensions which I find to be concise and readable.)

In a way map and reduce are easy. Map carries no state anyway and so is a really trivial “mapping” from the loop form

for i in N:
  l[i] = f(m[i])

simply becomes

l = map(f, m)

Reduce is slightly more interesting because it has an accumulator but it almost seems a like a cheat to me because reduce is a function that actually bundles an interesting functional concept (recursion) inside and lets you get away without thinking about it.

Pattern matching

The first pattern matching I was exposed to was Haskell’s and I fell in love with that. The notation is so close to how you would write down functions on a piece of paper that it seems the only natural way to do it (I’m sad to say that Racket’s pattern matching syntax is kind of cumbersome especially when you want to match conditions. I started using “if” statements as they are more succinct and then I discovered cond, which leads to pretty neat code)

Recursions instead of loops

Though racket has loop-like constructs, I’ve stayed away from them and tried to write everything as recursions. It was a little challenging at first but became more and more natural. It felt a little awkward because when I write Python, in the back of my mind is this voice that keeps saying <ghostly quiver in voice> “Function call overhead” and I usually end up making somewhat meaty functions. In Racket, because I’m doing things like recursion I end up abstracting computations into functions just to make code look neater and more atomic.

Testing

I’m really happy that Racket has a very easy to use and fully featured unit test system. It encourages me to include the tests right underneath an important function and I just run the file to execute the tests

Get it right the first time

I’ve now written a bunch of short scripts in Racket, mostly solving Euler problems, but some also to follow along Tim Roughgarden’s Algorithms course on coursera. One of the things that has startled me a bit is how often I get my Racket code right the first time. One big caveat is that I’m usually doing simple things, but it still startles me. I’ll be writing this dense looking code in this new language, I’ll write out the tests and then run and it’ll all pass. I think a large part of this is because I’m doing pure algoirthms – I’m not having to mess with real data which has a thousand edge cases that clutter up the code, and part of it has to do with me breaking up each task into atomic parts and coding and testing each part separately.

When writing in Racket I often feel I’m writing machine code again. I’m down in the weeds doing one small task at a time. This way, Python is more expressive, I feel I can do pretty complex things with a single list comprehension, for example. But functional code can be pretty cool and compact to look at when I get it right.

;; Given two sorted lists l1 and l2, merge them into a sorted list l3
(define (merge l1 l2)
  (cond
    [(= 0 (length l1)) l2]
    [(= 0 (length l2)) l1]
    [(< (first l1) (first l2)) (cons (first l1) (merge (rest l1) l2))]
    [else (cons (first l2) (merge l1 (rest l2)))]))

(test-case "merge"
           (check-equal? (merge `(1 2 3) `(4 5 6)) `(1 2 3 4 5 6))
           (check-equal? (merge `(1 3 5) `(2 4 6)) `(1 2 3 4 5 6))
           (check-equal? (merge `(2 4 6) `(1 3 5 7)) `(1 2 3 4 5 6 7))
           (check-equal? (merge `(2 4 6) `(2 4 6)) `(2 2 4 4 6 6))
           )

(define (merge-sort l)
  (cond
    [(< (length l) 2) l]
    [else (let-values ([(l1 l2) (split-at l (quotient (length l) 2))])
            (merge (merge-sort l1) (merge-sort l2)))]))

(test-case "merge-sort"
           (check-equal? (merge-sort `(6 5 4 3 2 1)) `(1 2 3 4 5 6))
           (check-equal? (merge-sort `(5 4 3 2 1)) `(1 2 3 4 5))
           (check-equal? (merge-sort `()) `())
           (check-equal? (merge-sort `(2)) `(2))
           (check-equal? (merge-sort `(6 1 4 3 2 5)) `(1 2 3 4 5 6))           
           )
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s