September 29, 2013

A Project Euler showdown

Ambrose Bonnaire-Sergeant’s core.typed library has been receiving a lot of attention lately. In fact, Ambrose has just raised a well-deserved \$20,000 to continue his work on the library.

I was doing Project Euler problems this weekend in Haskell for fun, and I thought it might be interesting to compare some solutions in typed clojure and Haskell. If you’ve not done Project Euler yet and don’t want spoilers, stop reading now.

Problem 1

Problem 1 requires you to compute the sum of the first 1000 integers divisible by 3 or 5. It’s a pretty straightforward problem. Here’s my (over-engineered) solution in Haskell:

``````divBy :: Int -> Int -> Bool
divBy x y = y `mod` x == 0

divBy3or5 :: Int -> Bool
divBy3or5 x = divBy 3 x || divBy 5 x

euler1 :: Int -> Int
euler1 n = sum \$ filter divBy3or5 (take n [0..])

main :: IO()
main =
putStrLn \$ show \$ euler1 1000
``````

And, after some stumbling, here’s a properly-annotated clojure version:

``````(ns euler.euler1
(:require [clojure.core.typed :refer [ann AnyInteger check-ns]])
(:import [clojure.lang ISeq]))

(ann ^:no-check clojure.core/mod [AnyInteger AnyInteger -> AnyInteger])

(ann div-by [AnyInteger AnyInteger -> Boolean])
(defn div-by [x y]
(== (mod y x) 0))

(ann div-by-3-or-5 [AnyInteger -> Boolean])
(defn div-by-3-or-5 [x]
(or (div-by 3 x) (div-by 5 x)))

(ann euler1 [AnyInteger -> AnyInteger])
(defn euler1 [n]
(reduce + (filter div-by-3-or-5 (range n))))

(ann -main [-> nil] )
(defn -main []
(prn (euler1 1000)))

(comment
(check-ns)
)
``````

You can see the pattern here, analogous to the Haskell code: an annotation, followed by an actual function definition.

It took me about 1 minute to port the actual code, and another 15 minutes to get the annotations all sorted out. A few gotchas I ran into on this, my first real foray into core.typed:

• `Integer` is less useful as a type than hoped. `AnyInteger` seems to be more permissive, and works more often. I’m sure there is a good reason for this.
• As seen at the top, it was necessary to annotate `mod`. It has the `no-check` flag on it, which is basically how you tell core.typed to just take your word on this one. That’s something you can’t do in Haskell, but I’m not sure whether or not that’s a good thing.
• At the bottom you see my `check-ns` call in a comment block. `check-ns` cannot be executed as part of loading the module, or problems occur. This way, I can eval check-ns in my editor to check types as I develop

To me, this code demonstrates two things: that Haskell, being the math-y language that it is, is much better at this sort of task; and that `core.typed` is all about pain now for gain later. You won’t get much in the short term annotating all your functions; any benefit will come later, when something changes elsewhere in your code and the type-checker notifies you.

Note that the Haskell solution could be even shorter; Haskell’s type engine is able to infer the types for all of the functions, so you can leave the signatures out:

``````divBy x y = y `mod` x == 0
divBy3or5 x = divBy 3 x || divBy 5 x
euler1 n = sum \$ filter divBy3or5 (take n [0..])

main :: IO()
main =
putStrLn \$ show \$ euler1 1000
``````

But then again,

``````(defn div-by [x y] (== 0 ))(mod y x)
(defn div-by-3-or-5 [x] (or (div-by 3 x) (div-by 5 x)))
(defn euler1 [n] (reduce + (filter div-by-3-or-5 (range n)))
``````

The difference being, of course, that Haskell retains all the type information and is still able to notify you about it when you screw up.

Problem 2

After all the messing around on Problem 1, I decided to do the next one just to see how it was writing `core.typed` code after a bit of practice.

Problem 2 requires us to compute the sum of all the even numbers in the fibonacci sequence less than some N (4,000,000 in this case).

``````fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

euler2 :: Int -> Int
euler2 n = sum \$ filter even \$ takeWhile (< n) fibs

main :: IO()
main =
putStrLn \$ show \$ euler2 4000000
``````

And in clojure:

``````(ns euler.euler2
(:require [clojure.core.typed :refer [ann AnyInteger check-ns fn>]])
(:import [clojure.lang ISeq]))

(ann fibs (ISeq AnyInteger))
(def fibs
(lazy-cat [0 1] (map + fibs (rest fibs))))

(ann euler2 [AnyInteger -> AnyInteger])
(defn euler2 [n]
(let [lt-n (fn> [m :- AnyInteger] (> n m))]
(reduce + (filter even? (take-while lt-n fibs)))))

(ann -main [-> nil])
(defn -main []
(prn (euler2 4000000)))

(comment
(check-ns)
)
``````

This was much easier to write, thanks to my already knowing about AnyInteger. I was happy to find an analogue to Haskell’s super-nifty fibonacci sequence using `lazy-cat`.

The only real deficiency in this clojure code compared to the Haskell, is that, lacking inference for unannotated anonymous functions, we must turn to the relatively verbose `fn>` syntax for the `take-while` call (which I pulled out into a `let` for readability). Happily, the return type can be inferred, so we don’t have to specify that.

It’s true that `core.typed`’s optional type sytem falls short of Haskell’s (which is truely no insult), but after getting used to I found it not so difficult to annotate my clojure. I’ll surely be using `core.typed` in the future; the extra verbosity and effort of annotating functions is a small price to pay to add type checking to my favorite language.

A few takeaways from the Hacker News discussion:

• Haskell can, and indeed must, annotate untyped functions accessed via its foreign function interface. No runtime type checking is performed, so this is very unsafe.
• Haskell does, indeed, have a `print` function.

And also, here’s a version in Typed Racket