Faktorielle Algorithmen in verschiedenen Sprachen
https://stackoverflow.com/questions/23930
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich möchte alle verschiedenen Möglichkeiten sehen, die Sie für eine faktorielle Unterroutine oder ein faktorielles Programm entwickeln können.Die Hoffnung ist, dass jeder hierher kommen und sehen kann, ob er vielleicht eine neue Sprache lernen möchte.
Ideen:
- Verfahrenstechnisch
- Funktional
- Objektorientierte
- Einzeiler
- Verschleiert
- Merkwürdig
- Schlechter Code
- Polyglott
Grundsätzlich möchte ich ein Beispiel für verschiedene Arten des Schreibens eines Algorithmus sehen und wie diese in verschiedenen Sprachen aussehen würden.
Bitte beschränken Sie sich auf ein Beispiel pro Eintrag.Ich erlaube Ihnen, mehr als ein Beispiel pro Antwort anzugeben, wenn Sie versuchen, einen bestimmten Stil, eine bestimmte Sprache oder einfach nur eine gut durchdachte Idee hervorzuheben, die sich für einen Beitrag eignet.
Die einzige wirkliche Anforderung besteht darin, die Fakultät eines bestimmten Arguments in allen dargestellten Sprachen zu finden.
Seien Sie kreativ!
Empfohlene Richtlinie:
# Language Name: Optional Style type
- Optional bullet points
Code Goes Here
Other informational text goes here
Gelegentlich werde ich jede Antwort bearbeiten, die keine angemessene Formatierung aufweist.
Lösung
Polyglott:5 Sprachen, alle mit Bignums
Also habe ich eine Polyglotte geschrieben, die in den drei Sprachen funktioniert, in denen ich oft schreibe, sowie eine aus meiner anderen Antwort auf diese Frage und eine, die ich heute erst gelernt habe.Es handelt sich um ein eigenständiges Programm, das eine einzelne Zeile mit einer nichtnegativen Ganzzahl liest und eine einzelne Zeile mit ihrer Fakultät ausgibt.Bignums werden in allen Sprachen verwendet, daher hängt die maximal berechenbare Fakultät nur von den Ressourcen Ihres Computers ab.
- Perl:verwendet das integrierte Bignum-Paket.Lauf mit
perl FILENAME. - Haskell:verwendet integrierte Bignums.Lauf mit
runhugs FILENAMEoder das Äquivalent Ihres Lieblings-Compilers. - C++:erfordert GMP für Bignum-Unterstützung.Zum Kompilieren mit g++ verwenden Sie
g++ -lgmpxx -lgmp -x c++ FILENAMEum mit den richtigen Bibliotheken zu verlinken.Nach dem Kompilieren ausführen./a.out.Oder verwenden Sie das Äquivalent Ihres bevorzugten Compilers. - Brainf*ck:Ich habe ein paar Bignum-Support geschrieben dieser Beitrag.Benutzen Mullers klassische Distribution, kompilieren mit
bf < FILENAME > EXECUTABLE.Machen Sie die Ausgabe ausführbar und führen Sie sie aus.Oder nutzen Sie Ihre Lieblingsdistribution. - Leerzeichen:verwendet integrierte Bignum-Unterstützung.Lauf mit
wspace FILENAME.
Bearbeiten: Leerzeichen als fünfte Sprache hinzugefügt.Übrigens, tun Sie es nicht Wickeln Sie den Code mit ein <code> Stichworte;es durchbricht das Leerzeichen.Außerdem sieht der Code in fester Breite viel besser aus.
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*/;}
Andere Tipps
lolcode:
Entschuldigung, ich konnte nicht widerstehen 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
Dies ist einer der schnelleren Algorithmen 170!.Es scheitert unerklärlicherweise über 170 hinaus!, und es ist relativ langsam für kleine Fakultäten, aber für Fakultäten dazwischen 80 Und 170 Im Vergleich zu vielen Algorithmen ist es unglaublich schnell.
curl http://www.google.com/search?q=170!
Es gibt auch eine Online-Schnittstelle, Probieren Sie es jetzt aus!
Lassen Sie mich wissen, wenn Sie einen Fehler oder eine schnellere Implementierung für große Fakultäten finden.
BEARBEITEN:
Dieser Algorithmus ist etwas langsamer, liefert aber Ergebnisse über 170:
curl http://www58.wolframalpha.com/input/?i=171!
Es vereinfacht sie auch in verschiedene andere Darstellungen.
C++:Vorlagen-Metaprogrammierung
Verwendet den klassischen Enum-Hack.
template<unsigned int n>
struct factorial {
enum { result = n * factorial<n - 1>::result };
};
template<>
struct factorial<0> {
enum { result = 1 };
};
Verwendung.
const unsigned int x = factorial<4>::result;
Die Fakultät wird vollständig zur Kompilierungszeit basierend auf dem Vorlagenparameter n berechnet.Daher ist „factorial<4>::result“ eine Konstante, sobald der Compiler seine Arbeit erledigt hat.
Leerzeichen
. . . . . . . . . . . . . . . . . . . . . . . . . .
Es war schwierig, es hier richtig anzuzeigen, aber jetzt habe ich versucht, es aus der Vorschau zu kopieren, und es funktioniert.Sie müssen die Nummer eingeben und die Eingabetaste drücken.
Ich finde die folgenden Implementierungen einfach urkomisch:
Die Entwicklung eines Haskell-Programmierers
Entwicklung eines Python-Programmierers
Genießen!
C#-Suche:
Eigentlich gibt es nichts zu berechnen, schauen Sie einfach nach.Um es zu erweitern, fügen Sie der Tabelle weitere 8 Zahlen hinzu, und 64-Bit-Ganzzahlen sind an ihrer Grenze.Darüber hinaus ist eine BigNum-Klasse erforderlich.
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];
}
Faul K
Ihre rein funktionalen Programmieralbträume werden wahr!
Die einzige Esoterische Turing-vollständige Programmiersprache das hat:
- Eine rein funktionale Grundlage, ein Kern und Bibliotheken – tatsächlich ist hier die vollständige API: SKI
- NEIN Lambdas sogar!
- NEIN Zahlen oder Listen benötigt oder erlaubt
- Keine explizite Rekursion, aber dennoch ermöglicht Rekursion
- Eine einfache unendlicher Lazy Stream-basierter I/O-Mechanismus
Hier ist der Factorial-Code in seiner ganzen Pracht in Klammern:
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)
Merkmale:
- Keine Subtraktion oder Bedingungen
- Druckt alle Fakultäten (wenn Sie lange genug warten)
- Verwendet eine zweite Schicht kirchlicher Ziffern, um die N-te Fakultät in N umzuwandeln!Sternchen gefolgt von einem Zeilenumbruch
- Verwendet die Y-Kombinator für Rekursion
Falls Sie daran interessiert sind, es zu verstehen, finden Sie hier den Scheme-Quellcode, der durch den Lazier-Compiler ausgeführt werden kann:
(lazy-def '(fac input)
'((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
(* a n)))) 1 1))
(für geeignete Definitionen von Y, cons, 1, 10, 42, 1+ und *).
BEARBEITEN:
Lazy-K-Fakultät in Dezimalzahl
(10 KB Kauderwelsch sonst würde ich es einfügen).Beispielsweise an der Unix-Eingabeaufforderung:
$ echo "4" | ./lazy facdec.lazy
24
$ echo "5" | ./lazy facdec.lazy
120
Eher langsam für Zahlen über beispielsweise 5.
Der Code ist etwas aufgebläht, weil wir ihn einbinden müssen Bibliothekscode für alle unsere eigenen Grundelemente (Code geschrieben Dunstig, ein in Haskell geschriebener Lambda-Kalkül-Interpreter und LC-to-Lazy-K-Compiler).
XSLT 1.0
Die Eingabedatei, faktorielle.xml:
<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
20
</n>
Die XSLT-Datei, faktorielle.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>
Speichern Sie beide Dateien im selben Verzeichnis und öffnen Sie sie faktorielle.xml im IE.
Python:Funktional, einzeilig
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
NOTIZ:
- Es unterstützt große ganze Zahlen.Beispiel:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
- Es funktioniert nicht n < 0.
APL (seltsam/einzeilig):
×/⍳X
- ⍳X erweitert X in ein Array der ganzen Zahlen 1..X
- ×/ multipliziert jedes Element im Array
Oder mit dem integrierten Operator:
!X
Quelle: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
Perl6
sub factorial ($n) { [*] 1..$n }
Ich weiß kaum etwas über Perl6.Aber ich vermute das [*] Der Operator ist derselbe wie der von Haskell product.
Dieser Code läuft weiter Möpse, und vielleicht Papagei (Ich habe es nicht überprüft.)
Bearbeiten
Dieser Code funktioniert auch.
sub postfix:<!> ($n) { [*] 1..$n }
# This function(?) call like below ... It looks like mathematical notation.
say 10!;
x86-64-Montage:Verfahrenstechnisch
Sie können dies von C aus aufrufen (nur mit GCC unter Linux amd64 getestet).Die Baugruppe wurde mit Nasm zusammengebaut.
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
Rekursiv in Inform 7
(es erinnert an COBOL, weil es zum Schreiben von Textabenteuern dient;proportionale Schriftart ist gewollt):
Um zu entscheiden, welche Zahl die Fakultät von (n – eine Zahl) ist:
Wenn n Null ist, entscheiden Sie sich für Eins.
Andernfalls entscheiden Sie sich für die Fakultät von (n minus eins) mal n.
Wenn Sie diese Funktion („Phrase“) tatsächlich aus einem Spiel aufrufen möchten, müssen Sie eine Aktion und eine Grammatikregel definieren:
„Das Faktorialspiel“ [dies muss die erste Zeile der Quelle sein]
Es gibt ein Zimmer.[Es muss mindestens einen geben!]
Faktorisieren ist eine Aktion, die auf eine Zahl angewendet wird.
Verstehen Sie „Fakultät [eine Zahl]“ als Fakultät.
Faktorisierung durchführen:
Sei n die Fakultät der verstandenen Zahl;
Sagen Sie „Es ist [n]“.
C#:LINQ
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
Erlang:Schwanz rekursiv
fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).
fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
Haskell:
ones = 1 : ones
integers = head ones : zipWith (+) integers (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
Brainf*ck
+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]
Geschrieben von Michael Reitzenstein.
BASIC:alte Schule
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
Charge (NT):
@echo off
set n=%1
set result=1
for /l %%i in (%n%, -1, 1) do (
set /a result=result * %%i
)
echo %result%
Verwendung:C:>factorial.bat 15
F#:Funktional
Ganz einfach:
let rec fact x =
if x < 0 then failwith "Invalid value."
elif x = 0 then 1
else x * fact (x - 1)
Lust auf mehr:
let fact x = [1 .. x] |> List.fold_left ( * ) 1
Rekursiver Prolog
fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.
Schwanzrekursiver 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).
Ruby rekursiv
(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
Verwendung:
factorial[5]
=> 120
Planen
Hier ist eine einfache rekursive Definition:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
In Scheme verwenden tail-rekursive Funktionen konstanten Stapelspeicherplatz.Hier ist eine Version von „factorial“, die schwanzrekursiv ist:
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
Kuriose Beispiele?Wie wäre es mit der Gammafunktion?Seit, Gamma n = (n-1)!.
OCaml:Verwendung von 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)))
Erstsemester-Haskell-Programmierer
fac n = if n == 0
then 1
else n * fac (n-1)
Sophomore Haskell -Programmierer am MIT (Studienschema als Neuling)
fac = (\(n) ->
(if ((==) n 0)
then 1
else ((*) n (fac ((-) n 1)))))
Junior Haskell -Programmierer (Anfang Peano Player)
fac 0 = 1
fac (n+1) = (n+1) * fac n
Ein weiterer Junior-Haskell-Programmierer (Lesen Sie, dass N+K-Muster „ein ekelhafter Teil von Haskell“ [1] sind und sich den „Ban N+K-Mustern“ angeschlossen haben [2])
fac 0 = 1
fac n = n * fac (n-1)
Senior Haskell -Programmierer (gestimmt für Nixon Buchanan Bush - „Lehnt sich rechts“)
fac n = foldr (*) 1 [1..n]
Ein weiterer Senior -Haskell -Programmierer (gestimmt für McGovern Biafra Nader - „Leans links“)
fac n = foldl (*) 1 [1..n]
Ein weiterer Senior -Haskell -Programmierer (lehnte sich so weit rechts, er kam wieder nach links zurück!)
-- using foldr to simulate foldl
fac n = foldr (\x g n -> g (x*n)) id [1..n] 1
Memoisierung von Haskell -Programmierer (täglich Ginkgo Biloba)
facs = scanl (*) 1 [1..]
fac n = facs !! n
Sinnloser (ahem) „punktfreier“ Haskell-Programmierer (untersucht in Oxford)
fac = foldr (*) 1 . enumFromTo 1
Iterativer Haskell -Programmierer (ehemaliger Pascal -Programmierer)
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
Iterativer Ein-Liner-Haskell-Programmierer (ehemaliger APL und C-Programmierer)
fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))
Haskell -Programmierer akkumulieren (auf einen schnellen Höhepunkt aufbauen)
facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)
fac = facAcc 1
Fortsetzung von Haskell-Programmierer (Erhöhte Kaninchen in frühen Jahren, dann nach New Jersey gezogen)
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)
fac = facCps id
Boy Scout Haskell -Programmierer (mag es, Knoten zu binden;Immer „ehrfürchtig“, gehört er zur Kirche des am wenigsten festen Punktes [8])
y f = f (y f)
fac = y (\f n -> if (n==0) then 1 else n * f (n-1))
Kombinatorischer Haskell -Programmierer (meidet Variablen, wenn nicht die Verschleierung;Das ganze Schmoren ist nur eine Phase, auch wenn es selten hinderlich ist)
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)))
Listenkodierender Haskell-Programmierer (bevorzugt es, in Unary zu zählen)
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
Interpretiver Haskell -Programmierer (nie eine Sprache getroffen, die er nicht mochte)
-- 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)))
Statischer Haskell -Programmierer (er macht es mit Klasse, er hat diesen Fundep Jones!Nach Thomas Hallgrens „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
Der Absolvent Haskell Programmierer (Graduate Education neigt dazu, einen von kleinen Bedenken hinsichtlich der Effizienz von Hardware-basierten Ganzzahlen zu befreien)
-- 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 -Programmierer (beginnt immer mit der „einfachen Vogelfaltung“)
-- (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
Cartesianal in Haskell-Programmierer (bevorzugt das griechische Essen, vermeidet das würzige indische Sachen.inspiriert von Lex Augusteijns „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 -Programmierer (aß so viele Bananas, dass seine Augen ausgeschaltet sind, jetzt braucht er neue Objektive!)
-- 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-Programmierer (aus Uustalu, Vene und Pardos „Recursion Schemata From Comonaden“ [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
Professor (unterrichtet Haskell an Neulinge)
fac n = product [1..n]
D-Vorlagen:Funktional
template factorial(int n : 1)
{
const factorial = 1;
}
template factorial(int n)
{
const factorial =
n * factorial!(n-1);
}
oder
template factorial(int n)
{
static if(n == 1)
const factorial = 1;
else
const factorial =
n * factorial!(n-1);
}
So verwendet:
factorial!(5)
Java 1.6:rekursiv, auswendig gelernt (für nachfolgende Aufrufe)
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;
}
Power Shell
function factorial( [int] $n )
{
$result = 1;
if ( $n -gt 1 )
{
$result = $n * ( factorial ( $n - 1 ) )
}
$result
}
Hier ist ein Einzeiler:
$n..1 | % {$result = 1}{$result *= $_}{$result}
Bash:Rekursiv
In Bash und rekursiv, aber mit dem zusätzlichen Vorteil, dass jede Iteration in einem neuen Prozess behandelt wird.Es kann maximal !20 berechnen, bevor es zum Überlauf kommt. Sie können es aber trotzdem für große Zahlen ausführen, wenn Ihnen die Antwort egal ist und Sie möchten, dass Ihr System umfällt ;)
#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
