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

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

 Page 1 of 1 [ 5 post ]

Relevant Pages