Dec 28 2007
I think my brain just exploded
Haskell is making a real strong bid to wrestle the coveted title of “Brian’s Favorite Language” away from the current title holder (Ocaml, in case you haven’t guessed).
The thing that just happened was that I wanted to find some pythogorean triples- you know, groups of three numbers x, y, and z such that x2 + y2 = z2. So, without really knowing the language in any sort of deep way, and without thinking about it too much, I wrote the quick program:
f :: Int -> [ (Int, Int, Int) ]
f n = [ (x, y, z) |
x <- [ 1 .. n ],
y <- [ x+1 .. n ],
z <- [ y+1 .. n ],
(x * x) + (y * y) == (z * z) ]
You basically don’t even need to know a lick of Haskell to figure out what it does- anyone who’s gotten far enough in math to have encountered sets would probably guess correctly. Well, they might use the term “set” instead of “list”. The fact that it’s returning pythagorean triplets would be blatantly obvious. OK, so it’s an O(N3) algorithm, and you could probably do it in O(N2). When calling it with small numbers, who cares? I can find out that f 20 is [(3,4,5),(5,12,13),(6,8,10),(8,15,17),(9,12,15),(12,16,20)] so fast that I don’t see the computer pause, and that’s the answer I was looking for. And it’s hard to beat this code for succinctness and clarity.
Popularity: 41% [?]
List comprehensions are cool eh! They are available as well for ocaml as a Camlp4 extension (the
[ a .. b ]notation is not available however, so one has to definerange):# #directory “+camlp4″;;
# #load “camlp4o.cma”;;
Camlp4 Parsing version 3.10.0
# #load “Camlp4Parsers/Camlp4ListComprehension.cmo”;;
# let rec range a b = if a > b then [] else a :: range (a+1) b;;
val range : int -> int -> int list =
# let f n = [ (x,y,z) |
x <- range 1 n;
y <- range (x+1) n;
z (int * int * int) list =
# f 20;;
- : (int * int * int) list =
[(3, 4, 5); (5, 12, 13); (6, 8, 10); (8, 15, 17); (9, 12, 15); (12, 16, 20)]
The code of
fdid not quite appear es expected, let me try again:let f n = [ (x,y,z) |
x <- range 1 n;
y <- range (x+1) n;
z <- range (y+1) n;
x * x + y * y = z * z ]
This is the kind of programming that I loved back in my Mathematica days…
[...] this post, which demonstrates the power of Haskell’s list [...]
I like both Haskell and OCaml, but I have to say that it is unavoidable, for me, to think of Haskell as the more beautiful. The syntax, for starters, is far saner.
I think haskell is definately a nicer language than ocaml. Doing stuff in ocaml often involves some rather ugly looking code, while haskell always seems to offer a consistent and elegant way to do anything. Just little things like completely removing the distinction between an operator and a function. In ocaml you can use an operator as a function, but you can’t use a function as an operator. Haskell lets you go both ways. And of course . and $ let you do away with the excessive parens that ocaml code requires. I also find doing imperative code in haskell much nicer than ocaml’s semicolon hell.
Of course, ocaml has a much better implimentation than haskell does. GHC is the best you get with haskell (pretty much your only option really considering how many extensions and stuff are GHC only) and it can take a really long time to compile code at times. Ocaml has a fantastic implimentation, bytecode and native compilers that are very fast, lex and yacc, debugger, profiler, proper interactive mode, its all there. But GHCi is a lot better now than it was, and there’s on-going work to make ghc have fewer corner cases that make it grind to a halt. If alex, happy, hat and haddock became offical tools that came with GHC so you didn’t have to worry about 4 seperate possible version mismatches it would certainly make things nicer too.
Funny, I just did this today for Project Euler (I’d already solved the problem using smarter methods than this, but I was curious as to how to do this with list comprehensions). While it was too slow for that problem, it’s great how a one-liner like this can do so much.
In passing, let me mention that the monadic version which looks quite similar too (even more so with the
donotation not shown here):let f n =
range 1 n >>= (fun x ->
range (x+1) n >>= (fun y ->
range (y+1) n >>= (fun z ->
if x * x + y * y = z * z then return(x,y,z) else [] )))
(the
>>=andreturnare the standard monadic operators on lists — see http://enfranchisedmind.com/blog/2007/08/06/a-monad-tutorial-for-ocaml/).Here’s a slight tweak of your haskell code to generate ALL of the pythagorean triples, in order of hypotenuse length:
pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [(a, b, c) | c <- [1..], b <- [1..c-1], a take 5 pythagoreanTriples
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17)]
Here is a slight tweak of your haskell code to make it generate ALL of the pythagorean triples, in order of hypotenuse length:
pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [(a, b, c) | c <- [1..], b <- [1..c-1], a <- [1..b-1], a^2 + b^2 == c^2]
Prelude> take 5 pythagoreanTriples
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17)]
Hmm… unfortunately i am not good at math, but i hear more praise about haskell than ocaml. The question still remains however, aren’t both bad choice for people who are bad in math stuff?
Oh man - spoilers for Problem 9 of Project Euler or what. (-: I’m working on that one at the moment, but using Erlang.
Programming is a bad choice for people who are bad in math stuff, IMHO.
Spruce Moose: actually, I’m not working on Project Euler. This was something different.
Replying to the original post, you can do the same thing in Scala:
def f(n:Int) = for(x <- 1 to n; y <- (x+1) to n; z <- (y+1) to n; if x*x + y*y == z*z) yield (x,y,z);
The Scala compiler infers the return type of the function, Seq[(Int,Int,Int)], and compiles the code into statically-typed JVM bytecodes.
for parselmouths:
filter(lambda (x, y, z): x*x + y*y == z*z, [(a, b, c) for a in range (1, n+1) for b in range (a, n+1) for c in range(b, n+1)])
obviously, the haskell and python versions are idea-wise isomorphic.
and here’s a kind of O(n^2) version . the range for the multiplying factor (mu) is off the top of my head, and is there to take the output from the p-q stuff (eg (3,4,5)) and get the derived triplets (eg (6,8,10) and (12,16,20)). i say “kind of” O(n^2) because the generation of unique triplets is O(n^2) at minimum, and multiplying each of the integers in the triplet to get all the derived triplets is an additional operation. i don’t have the upper bound for the multiplying factor, though if it can be proved that such a bound exists and is independent of n, the algorithm would become strictly — as opposed to “kind of” — O(n^2)
filter(lambda (a, b, c): max(a, b, c) <= n, [(p*q*mu, ((p**2 - q**2)/2)*mu, ((p**2 + q**2)/2)*mu) for q in range(1,n,2) for p in range(q+2,n,2) for mu in range(1, 5)])