Sunday, January 12, 2014

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:
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:

Prelude> ((+) 1 2)
3
Prelude> ((+) 1 2 3 4 5 6)
<interactive>:3:2:
No instance for (Num (a0 -> a1 -> a2 -> a3 -> t0))
arising from a use of `+'
Possible fix:
add an instance declaration for (Num (a0 -> a1 -> a2 -> a3 -> t0))
In the expression: ((+) 1 2 3 4 5 6)
In an equation for `it': it = ((+) 1 2 3 4 5 6)
...
Prelude> ((+) `foldl` 0) [1..6]
21
Prelude> ((sum) [1..6])
21
view raw 01-simple.hs hosted with ❤ by GitHub

More Operators

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

Prelude> ((==) 1 1)
True
Prelude> ((==) 1 2)
False
Prelude> ((/=) 1 1)
False
Prelude> ((/=) 1 2)
True
Prelude> ((&&) True False)
False
Prelude> ((&&) True True)
True
Prelude> ((||) True False)
True
Prelude> ((succ) 1)
2

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.)

Prelude> ((++) [1,2] [3,4])
[1,2,3,4]
Prelude> ((:) 1 [2,3])
[1,2,3]
Prelude> ((head) [1,2,3,4])
1
Prelude> ((tail) [1,2,3,4])
[2,3,4]
Prelude> import Data.List
Prelude Data.List> ((\\) [1,2,3,4] [1,4])
[2,3]
Prelude Data.List>
view raw 03-lists.hs hosted with ❤ by GitHub

List Comprehensions

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

Prelude> [((*) x 2) | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]
Prelude> [((*) x y) | x <- [2,5,10], y <- [8,10,11], ((>) ((*) x y) 50)]
[55,80,100,110]
view raw 04-list-comp.hs hosted with ❤ by GitHub

Functions

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

Prelude> doubleMe x = ((+) x x)
Prelude> ((doubleMe) 21)
42
Prelude> doubleUs x y = ((+) ((doubleMe) x) ((doubleMe) y))
Prelude> ((doubleUs) 5 20)
50
Prelude> doubleSmallNumber x = (if ((>) x 100) then x else ((*) x 2))
Prelude> ((doubleSmallNumber) 100)
200
Prelude>
view raw 05-funcs.hs hosted with ❤ by GitHub

Lambdas

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

Prelude> (\ x -> ((+) x 1)) 4
5
Prelude> (\ x y -> ((+) x y)) 3 5
8
Prelude> f x = (\ y -> ((+) x y))
Prelude> (f 10) 25
35
view raw 06-lambdas.hs hosted with ❤ by GitHub

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:

Prelude> import Data.List
Prelude Data.List> values = [1,2,2,3,4,5,99,66,6,7,8,8,9]
Prelude Data.List> (\ x -> (reverse (sort (nub (filter odd x))))) values
[99,9,7,5,3,1]
Prelude Data.List> ((.) ((.) ((.) reverse sort) nub) (filter odd)) values
[99,9,7,5,3,1]
Prelude Data.List> (reverse . sort . nub . (filter odd)) values
[99,9,7,5,3,1]
Prelude Data.List>
view raw 07-comp.hs hosted with ❤ by GitHub

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...

Prelude> [1, 2, 3] >>= \x -> [x + 1, x - 1] >>= \y -> return (y * x)
[2,0,6,2,12,6]
Prelude> ((>>=)
[1, 2, 3]
(\ x ->
(>>=)
[((+) x 1), ((-) x 1)]
(\ y -> return ((*) y x))))
[2,0,6,2,12,6]
view raw 08-monads.hs hosted with ❤ by GitHub

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

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.