n! in Scheme 
Author Message
 n! in Scheme

%  compthe4.tex 16-4-1996 (9h:6)

              +---------------------------------------+
              |       Philippe Esperet (France)       |

              +---------------------------------------+

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
ref :  n! in Scheme

   In an introduction to a small course on recursivity, I
should like to begin with a list of "recursive n!" in
different languages (from APL to TeX). I know Lisp (in fact
the French version "Le_Lisp", but not Scheme. Could
somebody translate for me the :

let rec fact=fun
| 0 -> 1
| n -> n*fact(n-1);;

or

int fact(int n)
{return n==0 ? 1 : n*fact(n-1);}

   Thank you if you can help.
   Best regards
--



Sat, 03 Oct 1998 03:00:00 GMT  
 n! in Scheme
: %  compthe4.tex 16-4-1996 (9h:6)
:
:               +---------------------------------------+
:               |       Philippe Esperet (France)       |

:               +---------------------------------------+
:
: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
: ref :  n! in Scheme
:
:    In an introduction to a small course on recursivity, I
: should like to begin with a list of "recursive n!" in
: different languages (from APL to TeX). I know Lisp (in fact
: the French version "Le_Lisp", but not Scheme. Could
: somebody translate for me the :
:
: let rec fact=fun
: | 0 -> 1
: | n -> n*fact(n-1);;
:
: or
:
: int fact(int n)
: {return n==0 ? 1 : n*fact(n-1);}
:
:    Thank you if you can help.
:    Best regards
: --
:  

Sure, it's easy enough.  It's just your second example in prefix notation,
with a bunch of parenthesis thrown in to reduce any ambiguity about which
forms arguements belong to:

(define (fact n)
   (if (= n 0) 1 (* n (fact (- n 1)))))

(fact 3) => 6

Or you can do it iteratively as well (using tail recursion):

;; Find the factorial iteratively, by storing the result in i.
;; Note to get the correct result, you must start i out as 1.
(define (fact-iter-aux n i)
   (if (= n 0) i (fact-iter (- n 1) (* i n))))

;; A more conventional wrapper for fact-iter-aux
(define (fact-iter n)
   (fact-iter-aux n 1))

(fact-iter-aux 4 1) => 24
(fact-iter 4) => 24

Some comments:  It's probably better to use (< n 2) as the test instead
of (= n 0), so the function doesn't infinite loop if a negative number
is passed in.  If you want to catch when negative numbers are passed in,
the best place would be in fact-iter, because then the test would only
happen once.

A form such as:
(define (foo x) (+ 2 x))
is shorthand for writing the form out:
(define foo
   (lambda (x) (+ 2 x)))

So what you are saying is that foo is a lambda form (function) that takes
one arguement and returns that arguement + 2.  Note that all functions
in scheme return one value, the last value to be evaluated.

  Michael



Sat, 03 Oct 1998 03:00:00 GMT  
 n! in Scheme

Quote:

> ref :  n! in Scheme

>    In an introduction to a small course on recursivity, I
> should like to begin with a list of "recursive n!" in
> different languages (from APL to TeX). I know Lisp (in fact
> the French version "Le_Lisp", but not Scheme. Could
> somebody translate for me the :

> let rec fact=fun
> | 0 -> 1
> | n -> n*fact(n-1);;

(define (fact n)
        (if (= n 0)
            1
            (* n (fact (- n 1)))))

Quote:
>    Thank you if you can help.

My pleasure.

--
Fredrik Rubensson

WWW: http://www.nada.kth.se/~prgp-fru/



Sat, 03 Oct 1998 03:00:00 GMT  
 n! in Scheme
While we're at it, following is a CPS (continuation passing style) version of
factorial:

(define (fact n)
  (fact-cps n (lambda (x) x)))

(define (fact-cps n k)
  (if (= n 0)
    (k 1)
    (fact-cps (- n 1) (lambda (v) (k (* n v))))))

--Greg

--
-----
Greg Sullivan,  17 Cullinane Hall            Phone:(617)373-8685(NU,office)
College of Computer Science,                       (617)373-5121(NU,fax)
Northeastern University
360 Huntington Avenue, Boston, MA 02115



Mon, 05 Oct 1998 03:00:00 GMT  
 n! in Scheme
Or, heck, this.  Please do not try (running) this at home!

(define !
  (lambda (n)
    ((lambda (n)
       ((n (lambda (x) (+ x 1))) 0))
      ((lambda (n)
         ((lambda (p)
            (p (lambda (x)
                 (lambda (y)
                   y))))
           ((n (lambda (p)
                 (((lambda (x)
                     (lambda (y)
                       (lambda (fun)
                         ((fun x) y))))
                    ((lambda (n)
                       (lambda (f)
                         (lambda (x)
                           (f ((n f) x)))))
                      ((lambda (p)
                         (p (lambda (x)
                              (lambda (y)
                                x)))) p)))
                   (((lambda (x)
                       (lambda (y)
                         ((y ((lambda (x)
                                (lambda (y)
                                  ((y (lambda (n)
                                        (lambda (f)
                                          (lambda (x)
                                            (f ((n f) x)))))) x))) x))
                           (lambda (f)
                             (lambda (x)
                               x)))))
                      ((lambda (p)
                         (p (lambda (x)
                              (lambda (y)
                                x)))) p))
                     ((lambda (p)
                        (p (lambda (x)
                             (lambda (y)
                               y)))) p)))))
             (((lambda (x)
                 (lambda (y)
                   (lambda (fun)
                     ((fun x) y))))
                ((lambda (n)
                   (lambda (f)
                     (lambda (x)
                       (f ((n f) x)))))
                  (lambda (f)
                    (lambda (x)
                      x))))
               ((lambda (n)
                  (lambda (f)
                    (lambda (x)
                      (f ((n f) x)))))
                 (lambda (f)
                   (lambda (x)
                     x)))))))
        (((lambda (i-n)
            (lambda (n)
              (i-n i-n n)))
           (lambda (loop n)
             (if (zero? n)
               (lambda (f)
                 (lambda (x)
                   x))
               ((lambda (n)
                  (lambda (f)
                    (lambda (x)
                      (f ((n f) x)))))
                 (loop loop (- n 1)))))) n)))))

'shriram



Fri, 09 Oct 1998 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Need comparison between Bigloo scheme, MIT-sheme,PLT-scheme

2. Scheme/Dylan incompatibilities (Dyllo as a Scheme library)

3. scheme/lisp syntax [Re: scheme]

4. scheme->c and other scheme derivative functionality

5. Scheme Interpreter in Scheme

6. Scheme in Scheme

7. Translations from Scheme to C++ as aid to teaching C++ after Scheme

8. Scheme project: SQL in Scheme, good idea?

9. PC-Scheme like Scheme for OS/2

10. Better Scheme in OS/2 than X-Scheme?

11. UNIX scheme vs MSDOS scheme

12. Writing a Scheme Interpreter in Scheme

 

 
Powered by phpBB® Forum Software