SML - prime factorization, building list error

Question

I'm trying to write an SML function that will return a list of all the prime factors to a given number. This will end up being a helper function to another function later on.

Originally the bigNumber is the number that I need to find the prime factors for and I pass in 1 less than that number as the divisor. Here's an example on how I'd call it to find the prime factors for the number 100. getPrimeFactors 100 99;

I'm not too worried about if there are flaws with the algorithm right now, but if you spot any errors with it I'd be happy to listen.

My main problem is trying to pass the return values up the recursion chain as lists and then combining those lists as they meet up with other lists.

fun getPrimeFactors bigNumber divisor = 
    if divisor > 0 then 
        if (bigNumber mod divisor) = 0 then List.concat(getPrimeFactors (bigNumber div divisor) ((bigNumber div divisor) - 1), getPrimeFactors divisor (divisor - 1))
        else [getPrimeFactors bigNumber (divisor - 1)]
    else [bigNumber];

Running this gives me this error. C:.....\run.x86-win32.exe: Fatal error -- Uncaught exception Error with 0 raised at ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27

C:\.....\commonFactors.sml:3.39-3.160 Error: operator and operand don't agree [tycon mismatch]
    operator domain: 'Z list list
    operand:         'Y * 'Y
        in expression:
            List.concat
            ((getPrimeFactors (<exp> div <exp>)) (<exp> div <exp> - 1),
             (getPrimeFactors divisor) (divisor - 1))
[Finished in 0.4s with exit code 1]

Any help would be greatly appreciated!

Tayacan Tayacan · Accepted Answer · 2013-06-28T13:18:40

You're trying to call List.concat on a tuple. The type of List.concat is

fn : 'a list list -> 'a list

That is, it takes a list of lists, concatenates all of those together, and returns the result. That's your error.

If, instead of using List.concat, we use the @ operator, we get a different error (which may look slightly different on your system):

File "test.sml", line 7, characters 14-53:
!         else [getPrimeFactors bigNumber (divisor - 1)]
!               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
! Type clash: expression of type
!   'a list
! cannot have type
!   'a
! because of circularity

This error is because getPrimeFactors is supposed to return an int list, but here you're trying to stuff the result from getPrimeFactors into a list, thus getting int list list.

SML - prime factorization, building list error

2 Answers