Prefix Operators in Haskell

I wanted to name this post something a little more catchy, like "McCarthy's Dream: Haskell as Lisp's M-Expressions" but I couldn't quite bring myself to do it. If s-expressions had greater support in Haskell, I would totally have gone for it, but alas, they don't.

However, there is still reason to celebrate: many Haskell operators do support prefix notation! This was a mind-blower to me, since I hadn't  heard about this until last night...

At the Data Day Texas conference this past Saturday, O'Reilly/StrataConf had a fantastic booth. Among the many cool give-aways they were doing, I obtained a coupon for a free ebook and another for 50% off. Upon returning home and having made my free book decision, I was vacillating between an OCaml book and the famous Haskell one. I've done a little Haskell in the past but have never touched OCaml, so I was pretty tempted.

However, something amazing happened next. I stumbled upon a page that was comparing OCaml and Haskell, which led to another page... where Haskell prefix notation was mentioned. I know many Haskellers who might read this would shrug, or say "yeah, we know", but this was quite a delightful little discovery for me :-)

I don't remember the first page I found, but since then, I've come across a couple more resources:

• http://www.haskell.org/haskellwiki/Infix_operator
• http://learninghaskell.wordpress.com/2009/07/23/haskell-prefix-and-infix-notations-for-functions/

That's pretty much it, though. (But please let me know if you know of or find any other resources!)

As such, I needed to do a lot more exploration. Initially, I was really excited and thought I'd be able to convert all Haskell forms to s-expressions (imports, lets, etc.), but I quickly found this was not the case. But the stuff that did work is pretty cool, and I saved it in a series of gists for your viewing pleasure :-)

Addition

The first test was pretty simple. Finding success, I thought I'd try something I do when using a Lisp/Scheme interpreter as a calculator. As you can see below, that didn't work (the full traceback is elided). Searching on Hoogλe got me to the answer I was looking for, though. Off to a good start:

More Operators

I checked some basic operators next, and a function. Everything's good so far:

Lists

Here are some basic list operations, including the ever-so-cool list difference operator, (\\). Also, I enjoyed the cons (:) so much that I made a t-shirt of it :-) (See the postscript below for more info.)

List Comprehensions

I'm not sure if one can do any more prefixing than this for list comprehensions:

Functions

Same thing for functions; nothing really exciting to see. (Btw, these examples were lifted from LYHGG.)

Lambdas

Things get a little more interesting with lambda expressions, especially when a closure is added for spice:

Function Composition

Using the compose operator in prefix notation is rather... bizarre :-) It looks much more natural as a series of compositions in a lambda. I also added a mostly-standard view of the compose operator for comparison:

Monads

I've saved the best for last, an example of the sort of thing I need when doing matrix operations in game code, graphics, etc. The first one is standard Haskell...

Wow. Such abstract. So brains. 

Note that to make the prefix version anywhere close to legible, I added whitepsace. (If you paste this in ghci, you'll see a bunch of prompts, and then the result. If you're running in the Sublime REPL, be sure to scroll to the right.)

And that pretty much wraps up what I did on Sunday afternoon :-)

Other Resources

• Travis Hartwell, Twisted hacker from back in the day, let me know about a great Haskell tutorial for Lispers.
• Here's a fun Lisper-oriented monad tutorial. Also, here's the best monad tutorial I've ever read.
• Liskell (ILC 2007 presentation; paper; 2009 update; source code)
• Lisk (Chris' lisk github repo seems to have disappeared, with the possible exception of an old fork)
• Husk Scheme (main page; github; Hackage)

Post Script

If you're in the San Antonio / Austin area (or SF; I'll be there in March) and want to go in on a t-shirt order, let me know :-) We need at least six for the smallest order (tri-blend Next Level; these are a bit pricey, but they feel GREAT). I'll collect payment before I make an order.

The Lambda Calculus: A Brief History

Over this past weekend I took a lovely journey into the heart of the lambda calculus, and it was quite amazing. My explorations were made within the context of LFE. Needless to say, this was a romp of pure delight. In fact, it was so much fun and helped to clarify for me so many nooks and crannies of something that I had simply not explored very thoroughly in the past, that I had to share :-)

The work done over the past few days is on its way to becoming part of the documentation for LFE. However, this is also an excellent opportunity to share some clarity with a wider audience. As such, I will be writing a series of blog posts on λ-calculus from a very hands-on (almost practical!) perspective. There will be some overlap with the LFE documentation, but the medium is different and as such, the delivery will vary (sometimes considerably).

This series of posts will cover the following topics:

1. A Brief History
2. A Quick Primer for λ-Calculus
3. Reduction Explained
4. Church Numerals
5. Arithmetic
6. Logic
7. Pairs and Lists
8. Combinators

The point of these posts is not to expound upon that which has already been written about endlessly. Rather, the hope is to give a very clear demonstration of what the lambda calculus really is, and to do so with clear examples and concise prose. When the gentle reader is able see the lambda calculus in action, with lines of code that clearly show what is occurring, the mystery will disappear and an intuition for the subject matter will quite naturally begin to arise. This post is the first in the series; I hope you enjoy them as much as I did rediscovering λ-calculus :-)

Let us start at the beginning...

A Brief History

The roots of functional programming languages such as Lisp, ML, Erlang, Haskell and others, can be traced to the concept of recursion in general and λ-calculus in particular. In previous posts, I touched upon how we ended up with the lambda as a symbol for the anonymous function as well as how recursion came to be a going concern in modern mathematics and then computer science.

In both of those posts we saw Alonzo Church play a major role, but we didn't really spend time on what is quite probably considered his greatest contribution to computer science, if not mathematics itself: λ-calculus. Keep in mind that the Peano axioms made use of recursion, that Giuseppe Peano played a key role in Bertrand Russell’s development of the Principia, that Alonzo Church sought to make improvements on the Principia, and λ-calculus eventually arose from these efforts.

Invented in 1928, Alonzo didn't publish λ-calculus until 1932. When an inconsistency was discovered, he revised it in 1933 and republished. Furthermore, in this second paper, Church introduced a means of representing positive integers using lambda notation, now known as Church numerals. With Church and Turing both publishing papers on computability in 1936 (based respectively upon λ-calculus and the concept of Turing machines), they proposed solutions to the Entscheidungsproblem. Though Gödel preferred Turing's approach, Rosser suggested that they were equivalent definitions in 1939. A few years later, Kleene proposed the Church Thesis (1943) and then later formally demonstrated the equivalence between his teacher's and Turing's approaches giving the combination the name of the Church-Turing Thesis (1952, in his Introduction to Metamathematics). Within eight years, John McCarthy published his now-famous paper describing the work that he had started in 1958: "Recursive Functions of Symbolic Expressions and Their Computation by Machine". In this paper, McCarthy outlined his new programming language Lisp, citing Church's 77-page book  (1941, Calculi of Lambda Conversion), sending the world off in a whole new direction.

Since that time, there has been on-going research into λ-calculus. Indisputably, λ-calculus has had a tremendous impact on research into computability as well as the practical applications of programming languages. As programmers and software engineers, we feel its impact -- directly and indirectly -- on a regular, almost daily basis.

Functional Programming in Python

Over the past couple years or so I've toyed with functional programming, dabbling in Lisp, Scheme, Erlang, and most recently, Haskell. I've really enjoyed the little bit I've done and have broadened my experience and understanding in the process.

Curious as to what folks have done with Python and functional programming, I recently did a google search I should have run years ago and discovered some community classics. I'm posting them here, in the event that I might spare others such an error in oversight :-)

• Functional Programming in Python (2001)
• More Functional Programming in Python (2001)
• Even More Functional Programming in Python (2001)
• Functional programming in Python becomes lazy (2003)
• Functional Programming HOWTO (updated 2006)
• The functional module (updated 2007)

I've always enjoyed David's writing style, though I've never read his FP articles until now. They were quite enjoyable and have aged well, despite referencing older versions of Python. Andrew's HOWTO provides a wonderful, modern summary.

I make fairly regular use of itertools but have never used the operator module -- though I now look forward to some FP idiomatic Python playtime with it :-) I've never used functools, either.

Enjoy!