64
votes

I want to see all the different ways you can come up with, for a factorial subroutine, or program. The hope is that anyone can come here and see if they might want to learn a new language.

Ideas:

  • Procedural
  • Functional
  • Object Oriented
  • One liners
  • Obfuscated
  • Oddball
  • Bad Code
  • Polyglot

Basically I want to see an example, of different ways of writing an algorithm, and what they would look like in different languages.

Please limit it to one example per entry. I will allow you to have more than one example per answer, if you are trying to highlight a specific style, language, or just a well thought out idea that lends itself to being in one post.

The only real requirement is it must find the factorial of a given argument, in all languages represented.

Be Creative!

Recommended Guideline:

# Language Name: Optional Style type

   - Optional bullet points

    Code Goes Here

Other informational text goes here

I will ocasionally go along and edit any answer that does not have decent formatting.

1
  • Everybody who does factorials using recursion is in a state of sin! Only recursive Fibonacci is worse. :-)
    – stevenvh
    Sep 18, 2010 at 16:33

129 Answers 129

1
2 3 4 5
184
votes

Polyglot: 5 languages, all using bignums

So, I wrote a polyglot which works in the three languages I often write in, as well as one from my other answer to this question and one I just learned today. It's a standalone program, which reads a single line containing a nonnegative integer and prints a single line containing its factorial. Bignums are used in all languages, so the maximum computable factorial depends only on your computer's resources.

  • Perl: uses built-in bignum package. Run with perl FILENAME.
  • Haskell: uses built-in bignums. Run with runhugs FILENAME or your favorite compiler's equivalent.
  • C++: requires GMP for bignum support. To compile with g++, use g++ -lgmpxx -lgmp -x c++ FILENAME to link against the right libraries. After compiling, run ./a.out. Or use your favorite compiler's equivalent.
  • brainf*ck: I wrote some bignum support in this post. Using Muller's classic distribution, compile with bf < FILENAME > EXECUTABLE. Make the output executable and run it. Or use your favorite distribution.
  • Whitespace: uses built-in bignum support. Run with wspace FILENAME.

Edit: added Whitespace as a fifth language. Incidentally, do not wrap the code with <code> tags; it breaks the Whitespace. Also, the code looks much nicer in fixed-width.

char //# b=0+0{- |0*/; #>>>>,----------[>>>>,--------
#define	a/*#--]>>>>++<<<<<<<<[>++++++[<------>-]<-<<<
#Perl	><><><>	 <> <> <<]>>>>[[>>+<<-]>>[<<+>+>-]<->
#C++	--><><>	<><><><	> < > <	+<[>>>>+<<<-<[-]]>[-]
#Haskell >>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]
#Whitespace	>>>>[-[>+<-]+>>>>]<<<<[<<<<]<<<<[<<<<
#brainf*ck > < ]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>*/
exp; ;//;#+<<<<-]<<<<]>>>>+<<<<<<<[<<<<][.POLYGLOT^5.
#include <gmpxx.h>//]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>>
#define	eval int	main()//>+<<<-]>>>[<<<+>>+>->
#include <iostream>//<]<-[>>+<<[-]]<<[<<<<]>>>>[>[>>>
#define	print std::cout	<< // >	<+<-]>[<<+>+>-]<<[>>>
#define	z std::cin>>//<< +<<<-]>>>[<<<+>>+>-]<->+++++
#define c/*++++[-<[-[>>>>+<<<<-]]>>>>[<<<<+>>>>-]<<*/
#define	abs int $n //><	<]<[>>+<<<<[-]>>[<<+>>-]]>>]<
#define	uc mpz_class fact(int	$n){/*<<<[<<<<]<<<[<<
use bignum;sub#<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-]
z{$_[0+0]=readline(*STDIN);}sub fact{my($n)=shift;#>>
#[<<+>+>-]<->+<[>-<[-]]>[-<<-<<<<[>>+<<-]>>[<<+>+>+*/
uc;if($n==0){return 1;}return $n*fact($n-1);	}//;#
eval{abs;z($n);print fact($n);print("\n")/*2;};#-]<->
'+<[>-<[-]]>]<<[<<<<]<<<<-[>>+<<-]>>[<<+>+>-]+<[>-+++
-}--	<[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<<+>+>-++
fact 0	= 1 -- ><><><><	> <><><	]+<[>-<[-]]>]<<[<<+ +
fact	n=n*fact(n-1){-<<]>>>>[[>>+<<-]>>[<<+>+++>+-}
main=do{n<-readLn;print(fact n)}-- +>-]<->+<[>>>>+<<+
{-x<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-]
<--.<<<<]+written+by+++A+Rex+++2009+.';#+++x-}--x*/;}
6
  • 7
    The largest factorial computable in one second (not counting output) on my computer by the various languages in this implementation: C++ gets 45000!, Haskell gets 35000!, Whitespace gets 11000!, Perl gets 2000!, and brainf*ck gets 350!.
    – A. Rex
    Jan 14, 2009 at 5:16
  • 21
    After staring at this code for a few minutes, my eyes kept drifting unexplicably to the offensive? link....
    – AShelly
    Jan 30, 2009 at 23:29
  • [steven@emu:~]% g++ -lgmpxx -lgmp -x c++ -I/opt/local/include -o test test.cpp test.cpp:16:35: error: unterminated comment gcc version 4.2.1 (Apple Inc. build 5646) :( Oct 19, 2009 at 0:35
  • @Steven Schlansker: It's a bug in the Stack Overflow display code that I don't know how to get around. (The code is being cut off above.) If you look at the revision history, it'll display the code correctly.
    – A. Rex
    Oct 19, 2009 at 9:25
  • Hopefully got the spacing right, but that should have fixed the truncation issue.
    – random
    Oct 19, 2009 at 10:03
124
votes

lolcode:

sorry I couldn't resist xD

HAI
CAN HAS STDIO?
I HAS A VAR
I HAS A INT
I HAS A CHEEZBURGER
I HAS A FACTORIALNUM
IM IN YR LOOP
    UP VAR!!1
    TIEMZD INT!![CHEEZBURGER]
    UP FACTORIALNUM!!1
    IZ VAR BIGGER THAN FACTORIALNUM? GTFO
IM OUTTA YR LOOP
U SEEZ INT
KTHXBYE    
1
52
votes

This is one of the faster algorithms, up to 170!. It fails inexplicably beyond 170!, and it's relatively slow for small factorials, but for factorials between 80 and 170 it's blazingly fast compared to many algorithms.

curl http://www.google.com/search?q=170!

There's also an online interface, try it out now!

Let me know if you find a bug, or faster implementation for large factorials.


EDIT:

This algorithm is slightly slower, but gives results beyond 170:

curl http://www58.wolframalpha.com/input/?i=171!

It also simplifies them into various other representations.

8
  • 4
    Use MPFR (mpfr.org). It allows floats with exponents in the 2^(2^32) range, or so... Sep 16, 2008 at 22:11
  • 1
    I suspect that google's factorial algorithm has an limit to prevent inordinate amounts of processing time. Were I them, I'd simply use a table - and it could be that they felt the table needn't be any larger than 170 entries.
    – Adam Davis
    Feb 23, 2009 at 14:39
  • 5
    That's a thing Wolfram Alpha performs better at than Google does :) Jun 5, 2009 at 13:18
  • 2
    Google uses 1024bit numbers for internal representation. 171! is too big to fit in 1024 bits.
    – LiraNuna
    Feb 19, 2010 at 20:17
  • 1
    @Adam: Google is using double-precision floats and you're hitting their maximum value.
    – J D
    May 25, 2010 at 2:03
48
votes

C++: Template Metaprogramming

Uses the classic enum hack.

template<unsigned int n>
struct factorial {
    enum { result = n * factorial<n - 1>::result };
};

template<>
struct factorial<0> {
    enum { result = 1 };
};

Usage.

const unsigned int x = factorial<4>::result;

Factorial is calculated completely at compile time based on the template parameter n. Therefore, factorial<4>::result is a constant once the compiler has done its work.

7
  • The enum isn't needed if you just declare the result as a "static const int" field. I.e. "static const int result = n * factorial<n - 1>::result;". The "enum hack" is only needed for Visual Studio 6 C++ compiler, which didn't support templates properly.
    – pauldoo
    Sep 22, 2008 at 10:51
  • 1
    A caveat with this solution is that, the ANSI C++ standard only enforces compilers to execute this kind of compile-time functions up to a limit - I believe 20 - of recursion levels. After that, you're in uncharted territory, left to the mercy of compiler creators.
    – Joe Pineda
    Sep 27, 2008 at 0:25
  • 1
    I think factorial<20> is the largest factorial that can be represented by a signed 64-bit long, so that works out okay
    – Kip
    Oct 6, 2008 at 16:31
  • @Kip is correct, 20! is less than 2^64, but 21! is larger than 2^64.
    – Wedge
    Oct 14, 2008 at 21:18
  • pauldoo, but then you also have to define that static const integer. not doing so may end up in a compile error for some compiler (the standard allows compilers not to diagnose that violation - thus you often don't see it rejected) Jan 25, 2009 at 1:54
34
votes

Whitespace

   	.
 .
 	.
		.
  	.
   	.
			 .
 .
	 	 .
	  .
   	.
 .
  .
 			 .
		  			 .
 .
	.
.
  	 .
 .
.
	.
 	.
.
.
.

It was hard to get it to show here properly, but now I tried copying it from the preview and it works. You need to input the number and press enter.

1
  • 10
    Makes even advanced languages like Haskell look downright obvious. Feb 25, 2009 at 0:09
34
votes

I find the following implementations just hilarious:

The Evolution of a Haskell Programmer

Evolution of a Python programmer

Enjoy!

0
26
votes

C# Lookup:

Nothing to calculate really, just look it up. To extend it,add another 8 numbers to the table and 64 bit integers are at at their limit. Beyond that, a BigNum class is called for.

public static int Factorial(int f)
{ 
    if (f<0 || f>12)
    {
        throw new ArgumentException("Out of range for integer factorial");
    }
    int [] fact={1,1,2,6,24,120,720,5040,40320,362880,3628800,
                 39916800,479001600};
    return fact[f];
}
2
  • 2
    Bravo. Perhaps the fastest implementation here, and as valid as it could be with that type signature. Oct 27, 2008 at 7:56
  • 1
    i think, many implementations can be faster for values from 0 to 12 because .NET can start slowly Jan 24, 2010 at 6:43
26
votes

Lazy K

Your pure functional programming nightmares come true!

The only Esoteric Turing-complete Programming Language that has:

Here's the Factorial code in all its parenthetical glory:

K(SII(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))))))))K))))))(S(K(S(K(S(SI(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))(S(S(KS)K))(S(SII)I(S(S(KS)K)I))))))))K)))))))
 (S(S(KS)K)(K(S(S(KS)K)))))))))(K(S(K(S(S(KS)K)))K))))(SII))II)

Features:

  • No subtraction or conditionals
  • Prints all factorials (if you wait long enough)
  • Uses a second layer of Church numerals to convert the Nth factorial to N! asterisks followed by a newline
  • Uses the Y combinator for recursion

In case you are interested in trying to understand it, here is the Scheme source code to run through the Lazier compiler:

(lazy-def '(fac input)
   '((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
       (* a n)))) 1 1))

(for suitable definitions of Y, cons, 1, 10, 42, 1+, and *).

EDIT:

Lazy K Factorial in Decimal

(10KB of gibberish or else I would paste it). For example, at the Unix prompt:

    $ echo "4" | ./lazy facdec.lazy
    24
    $ echo "5" | ./lazy facdec.lazy
    120

Rather slow for numbers above, say, 5.

The code is sort of bloated because we have to include library code for all of our own primitives (code written in Hazy, a lambda calculus interpreter and LC-to-Lazy K compiler written in Haskell).

0
21
votes

XSLT 1.0

The input file, factorial.xml:

<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
  20
</n>

The XSLT file, factorial.xsl:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"                     
                xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:msxsl="urn:schemas-microsoft-com:xslt" >
  <xsl:output method="text"/>
  <!-- 0! = 1 -->
  <xsl:template match="text()[. = 0]">
    1
  </xsl:template>
  <!-- n! = (n-1)! * n-->
  <xsl:template match="text()[. > 0]">
    <xsl:variable name="x">
      <xsl:apply-templates select="msxsl:node-set( . - 1 )/text()"/>
    </xsl:variable>
    <xsl:value-of select="$x * ."/>
  </xsl:template>
  <!-- Calculate n! -->
  <xsl:template match="/n">
    <xsl:apply-templates select="text()"/>
  </xsl:template>
</xsl:stylesheet>

Save both files in the same directory and open factorial.xml in IE.

0
19
votes

Python: Functional, One-liner

factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)

NOTE:

  • It supports big integers. Example:

print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000

  • It does not work for n < 0.
2
  • 2
    operator.mul would be much faster than lambda x,y: x*y.
    – spiv
    Oct 20, 2008 at 10:05
  • 4
    @spiv: x*y is 1.10-1.6 times slower then mul. math.factorial is faster then both. And memoized factorial is faster then math.factorial, etc. The question is not about performance.
    – jfs
    Oct 22, 2008 at 16:52
18
votes

APL (oddball/one-liner):

×/⍳X
  1. ⍳X expands X into an array of the integers 1..X
  2. ×/ multiplies every element in the array

Or with the built-in operator:

!X

Source: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt

15
votes

Perl6

sub factorial ($n) { [*] 1..$n }

I hardly know about Perl6. But I guess this [*] operator is same as Haskell's product.

This code runs on Pugs, and maybe Parrot (I didn't check it.)

Edit

This code also works.

sub postfix:<!> ($n) { [*] 1..$n }

# This function(?) call like below ... It looks like mathematical notation.
say 10!;
8
  • This has got to be the shortest one I have seen. Oct 19, 2008 at 3:24
  • Ok I guess there is one that is shorter, but who uses APL anyway. stackoverflow.com/questions/23930/… Oct 19, 2008 at 3:31
  • multi postfix<!>($n){[*]1..$n} Oct 19, 2008 at 3:40
  • Do you want to say multi sub postfix:<!> ($n) { [*] 1..$n }, Brad? It works on pugs. 10! is evaluated as 3628800. It's COOL! but pugs said *** No such subroutine: "&COOL".
    – nonowarn
    Oct 19, 2008 at 13:29
  • I just quickly posted a comment. The main point of the comment is TIMTOWTDI. Oct 26, 2008 at 23:41
14
votes

x86-64 Assembly: Procedural

You can call this from C (only tested with GCC on linux amd64). Assembly was assembled with nasm.

section .text
    global factorial
; factorial in x86-64 - n is passed in via RDI register
; takes a 64-bit unsigned integer
; returns a 64-bit unsigned integer in RAX register
; C declaration in GCC:
;   extern unsigned long long factorial(unsigned long long n);
factorial:
    enter 0,0
    ; n is placed in rdi by caller
    mov rax, 1 ; factorial = 1
    mov rcx, 2 ; i = 2
loopstart:
    cmp rcx, rdi
    ja loopend
    mul rcx ; factorial *= i
    inc rcx
    jmp loopstart
loopend:
    leave
    ret
0
13
votes

Recursively in Inform 7

(it reminds you of COBOL because it's for writing text adventures; proportional font is deliberate):

To decide what number is the factorial of (n - a number):
    if n is zero, decide on one;
    otherwise decide on the factorial of (n minus one) times n.

If you want to actually call this function ("phrase") from a game you need to define an action and grammar rule:

"The factorial game" [this must be the first line of the source]

There is a room. [there has to be at least one!]

Factorialing is an action applying to a number.

Understand "factorial [a number]" as factorialing.

Carry out factorialing:
    Let n be the factorial of the number understood;
    Say "It's [n]".

0
12
votes

C#: LINQ

    public static int factorial(int n)
    {
        return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
    }
2
  • public static long factorial(int n){}
    – Chris S
    Oct 14, 2008 at 15:18
  • 4
    public static long factorial(byte n){} Nov 22, 2008 at 8:17
12
votes

Erlang: tail recursive

fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).

fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
1
  • One-liner for the sake of it: > Fact = fun(N) when N > 0 -> lists:foldl(fun(X,Y)->X*Y end, 1, lists:seq(1,N)) end. Nov 13, 2008 at 18:57
12
votes

Haskell:

ones = 1 : ones
integers   = head ones     : zipWith (+) integers   (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
3
  • I think you are missing a parentheses, but the ( after the 3: is unnecessary. Sep 29, 2008 at 17:34
  • Your factorial is [1, 2, 3, 6, 18, 108, ...] instead of true factorial [1, 2, 6, 24, 120, 720, ...].
    – jfs
    Oct 19, 2008 at 13:33
  • factorials = 1 : (scanl1 (*) . scanl1 (+) . repeat $ 1) Jan 24, 2010 at 6:07
11
votes

Brainf*ck

+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]

Written by Michael Reitzenstein.

2
  • From blitzbasic.com/Community/posts.php?topic=36823. The output is placed in memory slot #2.
    – TonJ
    Sep 22, 2008 at 10:37
  • Note: as a result, on the standard implementation, this can only compute up to 5!. (Memory cells are usually one byte.) See post #432010 for a solution.
    – A. Rex
    Jan 13, 2009 at 17:13
10
votes

BASIC: old school

10 HOME
20 INPUT N
30 LET ANS = 1
40 FOR I = 1 TO N
50   ANS = ANS * I
60 NEXT I
70 PRINT ANS
0
9
votes

Batch (NT):

@echo off

set n=%1
set result=1

for /l %%i in (%n%, -1, 1) do (
    set /a result=result * %%i
)

echo %result%

Usage: C:>factorial.bat 15

5
  • Note that you need to have the registry patch to enable variable updates within loops! Sep 22, 2008 at 4:19
  • Just out of curiosity, what patch is that? I certainly haven't ever modified my registry so I could do something like this. Sep 22, 2008 at 8:36
  • Works on my computer (Windows XP SP3) without any patches. Nov 14, 2008 at 11:21
  • @Jeff: See cmd /? and set /? for info about delayed variable expansion. If it's disabled by default, you need to either tweak the registry, launch cmd with the /v:on switch or just put put setlocal enabledelayedexpansion at the beginning of your batch file.
    – Helen
    Jul 17, 2009 at 9:31
  • @JeffHillman: here's a recursive version to match the other entries. Feb 14, 2012 at 21:57
9
votes

F#: Functional

Straight forward:

let rec fact x = 
    if   x < 0 then failwith "Invalid value."
    elif x = 0 then 1
    else x * fact (x - 1)

Getting fancy:

let fact x = [1 .. x] |> List.fold_left ( * ) 1
2
  • You can also get fancier with unfold: let factorial n = (1,1) |> Seq.unfold (fun (n,p) -> let p' = n*p in Some (p',(n+1,p'))) |> Seq.nth (n-1)
    – namin
    Nov 14, 2008 at 6:55
  • @namim: or for something less overkill, "let fact x = [2 .. x] |> List.scan_left ( * ) 1"
    – Juliet
    Dec 30, 2008 at 14:35
8
votes

Recursive Prolog

fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.

Tail Recursive Prolog

fac(0,N,N).
fac(X,N,T) :- A is N * X, X1 is X - 1, fac(X1,A,T).
fac(N,T) :- fac(N,1,T).
0
8
votes

ruby recursive

(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
    

usage:

factorial[5]
 => 120
1
  • 1
    I would write that as (f=Hash.new{|h,k|h[k]=k*h[k-1]})[1]=1 or otherwise the calculated values are not stored
    – martinus
    Jan 29, 2009 at 22:52
7
votes

Scheme

Here is a simple recursive definition:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

In Scheme tail-recursive functions use constant stack space. Here is a version of factorial that is tail-recursive:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))
7
votes

Oddball examples? What about using the gamma function! Since, Gamma n = (n-1)!.

OCaml: Using Gamma

let rec gamma z =
    let pi = 4.0 *. atan 1.0 in
    if z < 0.5 then
        pi /. ((sin (pi*.z)) *. (gamma (1.0 -. z)))
    else
        let consts = [| 0.99999999999980993; 676.5203681218851; -1259.1392167224028;
                        771.32342877765313; -176.61502916214059; 12.507343278686905;
                 -0.13857109526572012; 9.9843695780195716e-6; 1.5056327351493116e-7;
                     |] 
        in
        let z = z -. 1.0 in
        let results = Array.fold_right 
                          (fun x y -> x +. y)
                          (Array.mapi 
                              (fun i x -> if i = 0 then x else x /. (z+.(float i)))
                              consts
                          )
                          0.0
        in
        let x = z +. (float (Array.length consts)) -. 1.5 in
        let final = (sqrt (2.0*.pi)) *. 
                    (x ** (z+.0.5)) *.
                    (exp (-.x)) *. result
        in
        final

let factorial_gamma n = int_of_float (gamma (float (n+1)))
7
votes

Freshman Haskell programmer

fac n = if n == 0 
           then 1
           else n * fac (n-1)

Sophomore Haskell programmer, at MIT (studied Scheme as a freshman)

fac = (\(n) ->
        (if ((==) n 0)
            then 1
            else ((*) n (fac ((-) n 1)))))

Junior Haskell programmer (beginning Peano player)

fac  0    =  1
fac (n+1) = (n+1) * fac n

Another junior Haskell programmer (read that n+k patterns are “a disgusting part of Haskell” [1] and joined the “Ban n+k patterns”-movement [2])

fac 0 = 1
fac n = n * fac (n-1)

Senior Haskell programmer (voted for Nixon Buchanan Bush — “leans right”)

fac n = foldr (*) 1 [1..n]

Another senior Haskell programmer (voted for McGovern Biafra Nader — “leans left”)

fac n = foldl (*) 1 [1..n]

Yet another senior Haskell programmer (leaned so far right he came back left again!)

-- using foldr to simulate foldl

fac n = foldr (\x g n -> g (x*n)) id [1..n] 1

Memoizing Haskell programmer (takes Ginkgo Biloba daily)

facs = scanl (*) 1 [1..]

fac n = facs !! n

Pointless (ahem) “Points-free” Haskell programmer (studied at Oxford)

fac = foldr (*) 1 . enumFromTo 1

Iterative Haskell programmer (former Pascal programmer)

fac n = result (for init next done)
        where init = (0,1)
              next   (i,m) = (i+1, m * (i+1))
              done   (i,_) = i==n
              result (_,m) = m

for i n d = until d n i

Iterative one-liner Haskell programmer (former APL and C programmer)

fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))

Accumulating Haskell programmer (building up to a quick climax)

facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)

fac = facAcc 1

Continuation-passing Haskell programmer (raised RABBITS in early years, then moved to New Jersey)

facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)

fac = facCps id

Boy Scout Haskell programmer (likes tying knots; always “reverent,” he belongs to the Church of the Least Fixed-Point [8])

y f = f (y f)

fac = y (\f n -> if (n==0) then 1 else n * f (n-1))

Combinatory Haskell programmer (eschews variables, if not obfuscation; all this currying’s just a phase, though it seldom hinders)

s f g x = f x (g x)

k x y   = x

b f g x = f (g x)

c f g x = f x g

y f     = f (y f)

cond p f g x = if p x then f x else g x

fac  = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))

List-encoding Haskell programmer (prefers to count in unary)

arb = ()    -- "undefined" is also a good RHS, as is "arb" :)

listenc n = replicate n arb
listprj f = length . f . listenc

listprod xs ys = [ i (x,y) | x<-xs, y<-ys ]
                 where i _ = arb

facl []         = listenc  1
facl n@(_:pred) = listprod n (facl pred)

fac = listprj facl

Interpretive Haskell programmer (never “met a language” he didn't like)

-- a dynamically-typed term language

data Term = Occ Var
          | Use Prim
          | Lit Integer
          | App Term Term
          | Abs Var  Term
          | Rec Var  Term

type Var  = String
type Prim = String


-- a domain of values, including functions

data Value = Num  Integer
           | Bool Bool
           | Fun (Value -> Value)

instance Show Value where
  show (Num  n) = show n
  show (Bool b) = show b
  show (Fun  _) = ""

prjFun (Fun f) = f
prjFun  _      = error "bad function value"

prjNum (Num n) = n
prjNum  _      = error "bad numeric value"

prjBool (Bool b) = b
prjBool  _       = error "bad boolean value"

binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j)))))


-- environments mapping variables to values

type Env = [(Var, Value)]

getval x env =  case lookup x env of
                  Just v  -> v
                  Nothing -> error ("no value for " ++ x)


-- an environment-based evaluation function

eval env (Occ x) = getval x env
eval env (Use c) = getval c prims
eval env (Lit k) = Num k
eval env (App m n) = prjFun (eval env m) (eval env n)
eval env (Abs x m) = Fun  (\v -> eval ((x,v) : env) m)
eval env (Rec x m) = f where f = eval ((x,f) : env) m


-- a (fixed) "environment" of language primitives

times = binOp Num  (*)

minus = binOp Num  (-)
equal = binOp Bool (==)
cond  = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y)))

prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ]


-- a term representing factorial and a "wrapper" for evaluation

facTerm = Rec "f" (Abs "n" 
              (App (App (App (Use "if")
                   (App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1))
                   (App (App (Use "*")  (Occ "n"))
                        (App (Occ "f")  
                             (App (App (Use "-") (Occ "n")) (Lit 1))))))

fac n = prjNum (eval [] (App facTerm (Lit n)))

Static Haskell programmer (he does it with class, he’s got that fundep Jones! After Thomas Hallgren’s “Fun with Functional Dependencies” [7])

-- static Peano constructors and numerals

data Zero
data Succ n

type One   = Succ Zero
type Two   = Succ One
type Three = Succ Two
type Four  = Succ Three


-- dynamic representatives for static Peanos

zero  = undefined :: Zero
one   = undefined :: One
two   = undefined :: Two
three = undefined :: Three
four  = undefined :: Four


-- addition, a la Prolog

class Add a b c | a b -> c where
  add :: a -> b -> c

instance              Add  Zero    b  b
instance Add a b c => Add (Succ a) b (Succ c)


-- multiplication, a la Prolog

class Mul a b c | a b -> c where
  mul :: a -> b -> c

instance                           Mul  Zero    b Zero
instance (Mul a b c, Add b c d) => Mul (Succ a) b d


-- factorial, a la Prolog

class Fac a b | a -> b where
  fac :: a -> b

instance                                Fac  Zero    One
instance (Fac n k, Mul (Succ n) k m) => Fac (Succ n) m

-- try, for "instance" (sorry):
-- 
--     :t fac four

Beginning graduate Haskell programmer (graduate education tends to liberate one from petty concerns about, e.g., the efficiency of hardware-based integers)

-- the natural numbers, a la Peano

data Nat = Zero | Succ Nat


-- iteration and some applications

iter z s  Zero    = z
iter z s (Succ n) = s (iter z s n)

plus n = iter n     Succ
mult n = iter Zero (plus n)


-- primitive recursion

primrec z s  Zero    = z
primrec z s (Succ n) = s n (primrec z s n)


-- two versions of factorial

fac  = snd . iter (one, one) (\(a,b) -> (Succ a, mult a b))
fac' = primrec one (mult . Succ)


-- for convenience and testing (try e.g. "fac five")

int = iter 0 (1+)

instance Show Nat where
  show = show . int

(zero : one : two : three : four : five : _) = iterate Succ Zero

Origamist Haskell programmer (always starts out with the “basic Bird fold”)

-- (curried, list) fold and an application

fold c n []     = n
fold c n (x:xs) = c x (fold c n xs)

prod = fold (*) 1


-- (curried, boolean-based, list) unfold and an application

unfold p f g x = 
  if p x 
     then [] 
     else f x : unfold p f g (g x)

downfrom = unfold (==0) id pred


-- hylomorphisms, as-is or "unfolded" (ouch! sorry ...)

refold  c n p f g   = fold c n . unfold p f g

refold' c n p f g x = 
  if p x 
     then n 
     else c (f x) (refold' c n p f g (g x))


-- several versions of factorial, all (extensionally) equivalent

fac   = prod . downfrom
fac'  = refold  (*) 1 (==0) id pred
fac'' = refold' (*) 1 (==0) id pred

Cartesianally-inclined Haskell programmer (prefers Greek food, avoids the spicy Indian stuff; inspired by Lex Augusteijn’s “Sorting Morphisms” [3])

-- (product-based, list) catamorphisms and an application

cata (n,c) []     = n
cata (n,c) (x:xs) = c (x, cata (n,c) xs)

mult = uncurry (*)
prod = cata (1, mult)


-- (co-product-based, list) anamorphisms and an application

ana f = either (const []) (cons . pair (id, ana f)) . f

cons = uncurry (:)

downfrom = ana uncount

uncount 0 = Left  ()
uncount n = Right (n, n-1)


-- two variations on list hylomorphisms

hylo  f  g    = cata g . ana f

hylo' f (n,c) = either (const n) (c . pair (id, hylo' f (c,n))) . f

pair (f,g) (x,y) = (f x, g y)


-- several versions of factorial, all (extensionally) equivalent

fac   = prod . downfrom
fac'  = hylo  uncount (1, mult)
fac'' = hylo' uncount (1, mult)

Ph.D. Haskell programmer (ate so many bananas that his eyes bugged out, now he needs new lenses!)

-- explicit type recursion based on functors

newtype Mu f = Mu (f (Mu f))  deriving Show

in      x  = Mu x
out (Mu x) = x


-- cata- and ana-morphisms, now for *arbitrary* (regular) base functors

cata phi = phi . fmap (cata phi) . out
ana  psi = in  . fmap (ana  psi) . psi


-- base functor and data type for natural numbers,
-- using a curried elimination operator

data N b = Zero | Succ b  deriving Show

instance Functor N where
  fmap f = nelim Zero (Succ . f)

nelim z s  Zero    = z
nelim z s (Succ n) = s n

type Nat = Mu N


-- conversion to internal numbers, conveniences and applications

int = cata (nelim 0 (1+))

instance Show Nat where
  show = show . int

zero = in   Zero
suck = in . Succ       -- pardon my "French" (Prelude conflict)

plus n = cata (nelim n     suck   )
mult n = cata (nelim zero (plus n))


-- base functor and data type for lists

data L a b = Nil | Cons a b  deriving Show

instance Functor (L a) where
  fmap f = lelim Nil (\a b -> Cons a (f b))

lelim n c  Nil       = n
lelim n c (Cons a b) = c a b

type List a = Mu (L a)


-- conversion to internal lists, conveniences and applications

list = cata (lelim [] (:))

instance Show a => Show (List a) where
  show = show . list

prod = cata (lelim (suck zero) mult)

upto = ana (nelim Nil (diag (Cons . suck)) . out)

diag f x = f x x

fac = prod . upto

Post-doc Haskell programmer (from Uustalu, Vene and Pardo’s “Recursion Schemes from Comonads” [4])

-- explicit type recursion with functors and catamorphisms

newtype Mu f = In (f (Mu f))

unIn (In x) = x

cata phi = phi . fmap (cata phi) . unIn


-- base functor and data type for natural numbers,
-- using locally-defined "eliminators"

data N c = Z | S c

instance Functor N where
  fmap g  Z    = Z
  fmap g (S x) = S (g x)

type Nat = Mu N

zero   = In  Z
suck n = In (S n)

add m = cata phi where
  phi  Z    = m
  phi (S f) = suck f

mult m = cata phi where
  phi  Z    = zero
  phi (S f) = add m f


-- explicit products and their functorial action

data Prod e c = Pair c e

outl (Pair x y) = x
outr (Pair x y) = y

fork f g x = Pair (f x) (g x)

instance Functor (Prod e) where
  fmap g = fork (g . outl) outr


-- comonads, the categorical "opposite" of monads

class Functor n => Comonad n where
  extr :: n a -> a
  dupl :: n a -> n (n a)

instance Comonad (Prod e) where
  extr = outl
  dupl = fork id outr


-- generalized catamorphisms, zygomorphisms and paramorphisms

gcata :: (Functor f, Comonad n) =>
           (forall a. f (n a) -> n (f a))
             -> (f (n c) -> c) -> Mu f -> c

gcata dist phi = extr . cata (fmap phi . dist . fmap dupl)

zygo chi = gcata (fork (fmap outl) (chi . fmap outr))

para :: Functor f => (f (Prod (Mu f) c) -> c) -> Mu f -> c
para = zygo In


-- factorial, the *hard* way!

fac = para phi where
  phi  Z             = suck zero
  phi (S (Pair f n)) = mult f (suck n)


-- for convenience and testing

int = cata phi where
  phi  Z    = 0
  phi (S f) = 1 + f

instance Show (Mu N) where
  show = show . int

Tenured professor (teaching Haskell to freshmen)

fac n = product [1..n]
1
  • 1
    Wow! I have no idea what he's talking about, but I'm sure if I understood it it would be really funny. Nov 16, 2009 at 16:46
7
votes

D Templates: Functional

template factorial(int n : 1)
{
  const factorial = 1;
}

template factorial(int n)
{
  const factorial =
     n * factorial!(n-1);
}

or

template factorial(int n)
{
  static if(n == 1)
    const factorial = 1;
  else 
    const factorial =
       n * factorial!(n-1);
}

Used like this:

factorial!(5)
2
  • In the second example remove the " : 1 " Jan 30, 2009 at 11:48
  • Thanks. Another example where the type is chosen on template instantiation: template factorial(T, T n) { static if(n == 1) const factorial = 1; else const factorial = n * factorial!(T,n-1); } factorial!(int,5)); Jan 31, 2009 at 10:26
6
votes

Java 1.6: recursive, memoized (for subsequent calls)

private static Map<BigInteger, BigInteger> _results = new HashMap()

public static BigInteger factorial(BigInteger n){
    if (0 >= n.compareTo(BigInteger.ONE))
       return BigInteger.ONE.max(n);
    if (_results.containsKey(n))
       return _results.get(n);
    BigInteger result = factorial(n.subtract(BigInteger.ONE)).multiply(n);
    _results.put(n, result);
    return result;
}
1
  • Nice. And you can seed the memo-map to get the performance of the C# lookup approach. Nov 16, 2008 at 1:26
6
votes

PowerShell

function factorial( [int] $n ) 
{ 
    $result = 1; 

    if ( $n -gt 1 ) 
    { 
        $result = $n * ( factorial ( $n - 1 ) ) 
    } 

    $result 
}

Here's a one-liner:

$n..1 | % {$result = 1}{$result *= $_}{$result}
6
votes

Bash: Recursive

In bash and recursive, but with the added advantage that it deals with each iteration in a new process. The max it can calculate is !20 before overflowing, but you can still run it for big numbers if you don't care about the answer and want your system to fall over ;)

#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
1
2 3 4 5

Not the answer you're looking for? Browse other questions tagged or ask your own question.