Gfrktyl

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 so I could accomplish a tail recursive function. Commented out is the line that let's me avoid the reversion of the list but then it's not tail recursive.

Besides that the three nested foldr calls. I have been thinking on write my own recursive functions but I wanted to do it using 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 (that generates the triples backwards):

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 loop (n, n, n) end