Clojure's core.typed vs Haskell
A Project Euler showdown
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 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:
Integeris less useful as a type than hoped.
AnyIntegerseems 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-checkflag 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-nscall in a comment block.
check-nscannot 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.
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
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
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
And also, here’s a version in Typed Racket