# Porting Haskell list comprehensions to Standard ML

Out of curiosity, I'm porting the Haskell exercises of Programming in Haskell by Graham Hutton to Standard ML. At the beginning everything seemed pretty similar until I reached list comprehensions:

A triple (x,y,z) of positive integers is called pythagorean if x2 + y2 = z2. Using a list comprehension, define a function pyths ∷ Int → [(Int,Int,Int)] that maps an integer n to all such triples with components in [1..n].

The Haskell version is pretty simple:

pyths ∷ Int → [(Int, Int, Int)]
pyths n = [(x, y, z) |
x ← [1..n],
y ← [1..n],
z ← [1..n],
x^2 + y^2 == z^2]


My Standard ML attempt, not so much:

(* No list comprehensions in SML so we need a helper function *)
val generateIntsUpTo = fn n =>
let val rec helper = fn current => fn xs =>
if current <= n
(* then current :: helper (current + 1) xs *)
then helper (current + 1) (current :: xs)
else xs
in
rev (helper 1 [])
end

(* Now we can find the pyths *)
val pyths = fn n =>
let
val numbers = generateIntsUpTo n
in
foldr (fn (x, acc) =>
foldr (fn (y, acc) =>
foldr (fn (z, acc) =>
if x * x + y * y = z * z
then (x, y, z) :: acc
else acc
) acc numbers
) acc numbers
) [] numbers
end


The first thing that I don't like is the call to rev at the end of generateIntsUpTo but I did it to accomplish a tail recursive function. Commented out is the line that lets me avoid the reversion of the list but then it's not tail recursive.

Besides that, there's the three nested foldr calls. I have been thinking of writing my own recursive functions, but I wanted to do this with the minimum amount of custom code.

Feedback:

• The Haskell pyths is not very efficient, and it contains duplicate answers.

• fun instead of val/val rec is syntactic sugar for function declarations.

• Instead of generateIntsUpTo n, use List.tabulate (n, fn i => i+1).

• Using rev to achieve a tail-recursive function can be a good choice. Neither SML/NJ's or Moscow ML's List.tabulate is tail-recursive, though. If you're worrying about performance here, consider the fact that you don't actually need to store these numbers in lists -- this is purely a convenience so that you can use list comprehensions to iterate their combinations.

Pythagorean triples in Standard ML

I wanted to do it using the minimum amount of custom code.

To achieve the same efficiency as the Haskell pyths and use the minimum amount of custom code, here is one version that uses List.filter, List.concat and List.tabulate:

fun isPythTriple (x, y, z) = x*x + y*y = z*z
fun tab1 n f = List.tabulate (n, fn i => f (i+1))
fun pyths n =
List.filter isPythTriple (
List.concat (tab1 n (fn x =>
List.concat (tab1 n (fn y =>
tab1 n (fn z => (x,y,z)))))))


This takes several seconds for pyths 10; there really is not reason to generate O(n³) list elements when the solution subset is so sparse.

I have been thinking on write my own recursive functions

Writing your own helper functions is really not something that should be avoided. Generally, using library functions is good, but Standard ML's library is somewhat limited. For example, List.tabulate can't iterate a range of numbers without generating the list in memory. And as you're hinting at, the multiple nested foldrs does not make the code particularly readable.

You could for example combine List.tabulate and List.filter to reduce memory consumption:

fun tabfilter (from, to, f) =
if from > to then [] else
case f from of
SOME value => value :: tabfilter (from+1, to, f)
| NONE       =>          tabfilter (from+1, to, f)

fun isPythTriple (x, y, z) = x*x + y*y = z*z

fun pyths n =
List.concat (tabfilter (1, n, fn x =>
SOME (List.concat (tabfilter (1, n, fn y =>
SOME (tabfilter (1, n, fn z => Option.filter isPythTriple (x, y, z))))))))


This runs orders of magnitude faster. Still, it is a little convoluted.

A plain recursive version:

fun isPythTriple (x, y, z) = x*x + y*y = z*z
fun pyths n =
let fun loop (0, _, _) = []
| loop (x, 0, _) = loop (x-1, n, n)
| loop (x, y, 0) = loop (x, y-1, n)
| loop (t as (x, y, z)) =
if isPythTriple t then t :: loop (x,y,z-1) else loop (x,y,z-1)
in rev (loop (n, n, n)) end


And a tail-recursive variant of the same:

fun isPythTriple x y z = x*x + y*y = z*z
fun pyths n =
let fun loop 0 _ _ res = res
| loop x 0 _ res = loop (x-1) n n res
| loop x y 0 res = loop x (y-1) n res
| loop x y z res =
let val res' = if isPythTriple x y z
then (x,y,z) :: res
else res
in loop x y (z-1) res'
end
in loop n n n [] end