Jump to content
  • Advertisement
Sign in to follow this  
TheUnbeliever

Scheme critique?

This topic is 4231 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was playing around in Scheme yesterday, between exams, and decided it might be an interesting task to write a little function to factor numbers -- and then realised it would be easy to implement a prime? predicate in terms of this; and a prime factorisation (EDIT: As in list the prime factors -- not like 2*3*5 or something) function in terms of the previous two (not an efficient algorithm, but quite simple to do). Can any Schemers comment on how I could improve the code (without drastically changing the algorithm -- I'm aware of primality tests which are much, much, much faster).
(define (factor n)
  (define (recFactor i factors)
    (cond ((> i
              n)
           factors)
          ((= (remainder n
                         i)
              0)
           (recFactor (+ i
                         1)
                      (append factors
                              (list i))))
          (else
           (recFactor (+ i
                         1)
                      factors))))
  (recFactor 2
             '(1)))

(define (prime? n)
  (= (length (factor n))
     2))

(define (primeFactor n)
  (define (recPrimeFactor factors primefactors)
    (cond ((= (length factors)
              0)
           primefactors)
          ((prime? (car factors))
           (recPrimeFactor (cdr factors)
                           (append primefactors
                                   (list (car factors)))))
          (else
           (recPrimeFactor (cdr factors)
                           primefactors))))
  (recPrimeFactor (factor n)
                  '()))

[Edited by - TheUnbeliever on May 16, 2007 2:54:34 PM]

Share this post


Link to post
Share on other sites
Advertisement
I haven't used Scheme since university and don't really know the language idioms, but I can offer some suggestions from general programming experience:

- Since we will make the recursive call - with the same first parameter - in 2 of the three cases, factor it out: make the call as long as i <= n, and do a separate cond to determine the second parameter.

- Instead of creating a list from an element in order to append two lists, I think just using cons is more natural. Of course, because that will put an element at the head of a list instead of the tail, we'll need to reverse it at the end, if we care... except that we can get around that by simply checking the 'i' values in reverse order ;)


(define (factor n)
(define (recFactor i factors)
(cond ((< i 1) factors)
(else
(recFactor (- i 1)
(cond ((= (remainder n i) 0)
(cons i factors))
(else factors))))))
(recFactor 2 '(n))
)



for the primeFactor function, similar advice would apply.

Except that I'm sure there's got to be some sort of library function that does that sort of thing (return the list of all elements in a list satisfying a predicate) - like 'filter' or something. If you're clever, you should be able to figure out how to apply it for (factor n) as well :)

Share this post


Link to post
Share on other sites
Quote:

- Instead of creating a list from an element in order to append two lists, I think just using cons is more natural. Of course, because that will put an element at the head of a list instead of the tail, we'll need to reverse it at the end, if we care... except that we can get around that by simply checking the 'i' values in reverse order ;)


Not only is it more natural, cons is a constant-time operation, while append is not. So very definitely. :)

On another algorithmic note, you only need to check up to the square root of n; no factors smaller than the root of n naturally means n is prime.

If you feel like playing around more, you might try the inverse approach; generate a list of primes (a lazy list, which is instructive and easy to do in scheme) and write your factor method in terms of that.

On a stylistic note, splitting the parameters to a function into separate lines should only be done when it increases readability. Splitting (+ i 1) down the i for example makes your code look pretty un-scheme-like and hard to read.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous P
On another algorithmic note, you only need to check up to the square root of n; no factors smaller than the root of n naturally means n is prime.


Well yes; but he wanted first to list all factors of the number (which may in fact be as large as n/2) and is then reusing that functionality for the primality testing.

Quote:
If you feel like playing around more, you might try the inverse approach; generate a list of primes (a lazy list, which is instructive and easy to do in scheme) and write your factor method in terms of that.


I agree that this would be instructive :)

Quote:
On a stylistic note, splitting the parameters to a function into separate lines should only be done when it increases readability. Splitting (+ i 1) down the i for example makes your code look pretty un-scheme-like and hard to read.


Also agreed.

On readability: It seems to be idiomatic for this family of languages to bunch up all the closing parentheses, instead of following the common practice from ALGOL-syntax languages of lining up closing braces with the lines where they were opened. I know that modern editors do lots of helpful things to help you match brackets as you type, but don't Schemers find it harder to *read* the code this way (and figure out what "scope" - er, level of the syntax tree - is being returned to)?

Share this post


Link to post
Share on other sites
Reading your first two points, Zahlman, I gave that a try and came up with

(define (factor n)
(define (recFactor i factors)
(if (< i
1)
factors
(recFactor (- i
1)
(if (= (remainder n
i)
0)
(cons i
factors)
factors))))
(recFactor n '()))


Which I'm glad to see is very similar to what you've got. Now, the suggestion of a 'filter' function is interesting. As far as I can tell, there isn't a standard Scheme library function which does that exactly (although there is an SRFI 'fold' function -- but my MIT Scheme implementation doesn't seem to support any of the SRFIs). On the other hand, it's easy enough to write it.

(define (filter predicate? list)
(cond ((null? list) '())
((predicate? (car list))
(cons (car list) (filter predicate? (cdr list))))
(else
(filter predicate? (cdr list)))))

(define (naturalsTo n)
(define (recNaturalsBefore i naturals)
(if (< i 1)
naturals
(recNaturalsBefore (- i 1) (cons i naturals))))
(recNaturalsBefore n '()))

(define (factor n)
(define (factor? i)
(= (remainder n i) 0))
(filter factor?
(append (naturalsTo (ceiling (/ n 2)))
(list n))))

(define (prime? n)
(= (length (factor n))
2))

(define (primeFactor n)
(filter prime? (factor n)))




... But that still has the slightly-ugly (append ... (list n)) thing.

I'll have a go at the lazy list of primes, it could be quite interesting (use delay and force for the (sort of) lazy evaluation?). I'm getting more and more fond of Scheme, it has to be said.

[Edited by - TheUnbeliever on May 17, 2007 4:13:44 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!