algorithm - luz - palabras en diferentes idiomas

Algoritmos factoriales en diferentes idiomas

Question

Quiero ver todas las diferentes formas en que se te ocurre, una subrutina factorial o un programa. La esperanza es que cualquier persona pueda venir aquí y ver si es posible que desee aprender un nuevo idioma.

Ideas:

• Procesal
• Funcional
• Orientado a objetos
• One liners
• Ofuscado
• Bicho raro
• Código malo
• Polyglot

Básicamente, quiero ver un ejemplo, diferentes formas de escribir un algoritmo y cómo se verían en diferentes idiomas.

Por favor limítelo a un ejemplo por entrada. Le permitiré tener más de un ejemplo por respuesta, si está tratando de resaltar un estilo específico, un lenguaje o simplemente una idea bien pensada que se presta para estar en una publicación.

El único requisito real es que debe encontrar el factorial de un argumento dado, en todos los idiomas representados.

¡Ser creativo!

Directriz recomendada:

# Language Name: Optional Style type - Optional bullet points Code Goes Here Other informational text goes here

De vez en cuando voy a ir y edito cualquier respuesta que no tenga un formato decente.

Answer 1

BÁSICO: vieja escuela

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

Answer 2

Brainf * ck

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

Escrito por Michael Reitzenstein.

Answer 3

C #: LINQ

 public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}

Answer 4

C ++: metaprogramación de plantillas

Utiliza el clásico enum hack.

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

Uso.

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

Factorial se calcula completamente en tiempo de compilación en función del parámetro de plantilla n. Por lo tanto, factorial <4> :: result es una constante una vez que el compilador ha hecho su trabajo.

Answer 5

Erlang: cola recursiva

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

Answer 6

Espacio en blanco

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

Fue difícil mostrarlo aquí correctamente, pero ahora intenté copiarlo de la vista previa y funciona. Debes ingresar el número y presionar enter.

Answer 7

F #: Funcional

Directo:

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

Conseguir lujo:

let fact x = [1 .. x] |> List.fold_left ( * ) 1

Answer 8

Perl6

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

Apenas sé sobre Perl6. Pero supongo que este operador [*] es el mismo que el product de Haskell.

Este código se ejecuta en Pugs , y tal vez Parrot (no lo revisé).

Editar

Este código también funciona.

sub postfix:<!> ($n) { [*] 1..$n }
# This function(?) call like below ... It looks like mathematical notation.
say 10!;

Answer 9

Polyglot: 5 idiomas, todos usan bignums

Entonces, escribí un políglota que funciona en los tres idiomas en los que a menudo escribo, al igual que uno de mi otra respuesta a esta pregunta y que acabo de aprender hoy. Es un programa independiente, que lee una sola línea que contiene un entero no negativo e imprime una sola línea que contiene su factorial. Bignums se utilizan en todos los idiomas, por lo que el máximo factorial computable depende solo de los recursos de su computadora.

• Perl : usa el paquete bignum incorporado. Ejecutar con perl FILENAME .
• Haskell : usa bignums incorporados. Ejecute con runhugs FILENAME o el equivalente de su compilador favorito.
• C ++ : requiere GMP para soporte de bignum. Para compilar con g ++, use g++ -lgmpxx -lgmp -x c++ FILENAME para vincularlo con las bibliotecas correctas. Después de compilar, ejecute ./a.out . O use el equivalente de su compilador favorito.
• brainf * ck : escribí algo de apoyo bignum en esta publicación . Usando la distribución clásica de Muller , compila con bf < FILENAME > EXECUTABLE . Haga el resultado ejecutable y ejecútelo. O usa tu distribución favorita
• Espacio en blanco : usa soporte de bignum incorporado. Ejecutar con wspace FILENAME .

Editar: agregó espacios en blanco como un quinto idioma. Por cierto, no ajuste el código con las etiquetas <code> ; rompe el espacio en blanco. Además, el código se ve mucho mejor en ancho fijo.

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*/;}

Answer 10

Prólogo recursivo

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

Prólogo recursivo de la cola

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).

Answer 11

Python: Funcional, One-liner

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

NOTA:

• Admite números enteros grandes. Ejemplo:

print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915/
608941463976156518286253697920827223758251185210916864000000000000000000000000

• No funciona para n <0 .

Answer 12

rubí recursivo

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

uso:

factorial[5]
=> 120

Answer 13

x86-64 Ensamblaje: procedural

Puede llamar esto desde C (solo probado con GCC en linux amd64). Asamblea fue ensamblada con 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

Answer 14

APL (oddball / one-liner):

×/⍳X

1. ⍳X expande X en una matriz de enteros 1..X
2. × / multiplica cada elemento en la matriz

O con el operador incorporado:

!X

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

Answer 15

Lazy K

¡Tus pesadillas de programación funcional pura se hacen realidad!

El único Lenguaje de programación completo de Turing esotérico que tiene:

• Una base, núcleo y librerías puramente funcionales --- de hecho, aquí está la API completa: ESQUÍ
• ¡Ni siquiera lambdas !
• No se necesitan ni permiten numbers ni listas
• Sin recurrencia explícita, pero aún así, permite la recursión
• Un mecanismo simple de E / S basado en secuencias perezosas infinitas

Aquí está el código factorial en toda su gloria parentética:

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)

caracteristicas:

• Sin restas ni condicionales
• Imprime todos los factoriales (si esperas lo suficiente)
• Utiliza una segunda capa de números de la Iglesia para convertir el N factorial a N! asteriscos seguido de una nueva línea
• Utiliza el combinador Y para la recursión

En caso de que esté interesado en tratar de entenderlo, aquí está el código fuente del Esquema para ejecutar a través del compilador Lazier:

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

(para definiciones adecuadas de Y, contras, 1, 10, 42, 1+ y *).

EDITAR:

Lazy K Factorial en Decimal

( 10KB de galimatías o de lo contrario lo pegaría ). Por ejemplo, en el indicador de Unix:

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

Más bien lento para los números anteriores, digamos, 5.

El código está un poco hinchado porque tenemos que incluir el código de la biblioteca para todas nuestras primitivas (código escrito en Hazy , un intérprete de cálculo lambda y compilador LC-to-Lazy K escrito en Haskell).

Answer 16

D Templates: Functional

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

o

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

Used like this:

factorial!(5)

Answer 17

Bash: Recursive

En bash y recursivo, pero con la ventaja añadida de que trata cada iteración en un nuevo proceso. El máximo que puede calcular es 20 antes de desbordarse, pero aún así puede ejecutarlo en grandes cantidades si no le importa la respuesta y desea que su sistema se caiga;)

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

Answer 18

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;
}

Answer 19

Recursivamente en Inform 7

(le recuerda a COBOL porque es para escribir aventuras de texto; la fuente proporcional es deliberada):

Para decidir qué número es el factorial de (n - un número):
si n es cero, decide uno;
de lo contrario, decida el factorial de (n menos uno) veces n.

Si realmente quieres llamar a esta función ("frase") de un juego, necesitas definir una regla de acción y gramática:

"El juego factorial" [esta debe ser la primera línea de la fuente]

Hay una habitación [¡Tiene que haber al menos uno!]

La factorización es una acción que se aplica a un número.

Comprender "factorial [a number]" como factorialing.

Llevar a cabo la factorización:
Sea n el factorial del número entendido;
Diga "Es [n]".

Answer 20

XSLT 1.0

El archivo de entrada, factorial.xml :

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

El archivo XSLT, 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>

Guarde ambos archivos en el mismo directorio y abra factorial.xml en IE.

Answer 21

lolcode:

lo siento, no pude resistir 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

Answer 22

¿Ejemplos de Oddball? ¿Qué hay de usar la función gamma? Desde, Gamma n = (n-1)! .

OCaml: Usar 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)))

Answer 23

C # búsqueda:

Nada que calcular realmente, solo búscalo. Para ampliarlo, agregue otros 8 números a la tabla y los enteros de 64 bits están en su límite. Más allá de eso, se necesita una clase BigNum.

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];
}

Answer 24

Encuentro las siguientes implementaciones simplemente hilarantes:

La evolución de un programador Haskell

Evolución de un programador de Python

¡Disfrutar!

Answer 25

Este es uno de los algoritmos más rápidos, ¡hasta 170! . ¡ fails inexplicablemente más allá de 170 !, y es relativamente lento para pequeños factoriales, pero para factoriales entre 80 y 170! es sorprendentemente rápido en comparación con muchos algoritmos.

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

También hay una interfaz en línea, ¡ pruébalo ahora!

Avíseme si encuentra un error o una implementación más rápida para factoriales grandes.

EDITAR:

Este algoritmo es un poco más lento, pero da resultados más allá de 170:

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

También los simplifica en varias otras representaciones.

Answer 26

Haskell:

ones = 1 : ones
integers = head ones : zipWith (+) integers (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)

Answer 27

Lote (NT):

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

Uso: C:> factorial.bat 15

Answer 28

Potencia Shell

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}

Answer 29

Programador Haskell de primer año

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

Programador Sophomore Haskell, en el MIT (estudió Scheme en su primer año)

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

Programador Junior Haskell (jugador principiante de Peano)

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

Otro programador Haskell junior (léase que los patrones n + k son "una parte repugnante de Haskell" [1] y se unió a los "patrones Ban n + k" -movimiento [2])

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

Programador Senior Haskell (votó a favor de Nixon Buchanan Bush - "se inclina a la derecha")

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

Otro programador senior de Haskell (votó por McGovern Biafra Nader - "se inclina hacia la izquierda")

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

Sin embargo, otro programador senior de Haskell (se inclinó tan a la derecha que regresó a la izquierda otra vez).

-- using foldr to simulate foldl
fac n = foldr (/x g n -> g (x*n)) id [1..n] 1

Memorando al programador Haskell (toma Ginkgo Biloba diariamente)

facs = scanl (*) 1 [1..]
fac n = facs !! n

Programador de Haskell sin puntos (ejem) "sin puntos" (estudiado en Oxford)

fac = foldr (*) 1 . enumFromTo 1

Programador Iterative Haskell (antiguo programador Pascal)

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

Programador iterativo Haskell de una sola línea (antiguo programador APL y C)

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

Acumulando programador Haskell (construyendo hasta un clímax rápido)

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

Programador Haskell de pases de continuación (se crió CONEJOS en los primeros años, luego se mudó a Nueva Jersey)

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

Programador de Boy Scout Haskell (le gusta atar nudos, siempre "reverente", pertenece a la Iglesia del Mínimo Punto Fijo [8])

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

Programador Haskell combinatorio (evita las variables, si no la ofuscación, todo este currying es solo una fase, aunque rara vez lo dificulta)

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)))

Programador Haskell que codifica la lista (prefiere contar en unario)

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

Programador interpretativo de Haskell (nunca "conoció un idioma" que no le gustaba)

-- 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)))

Programador de Haskell estático (lo hace con clase, tiene esa diversión Jones! Después de "Diversión con dependencias funcionales" de Thomas Hallgren [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

Programador Haskell graduado principiante (la educación de posgrado tiende a liberar a uno de las preocupaciones mezquinas, por ejemplo, la eficiencia de los enteros basados ​​en hardware)

-- 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

Programador Hasamell origamista (siempre comienza con el "doblez básico de Aves")

-- (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

Programador Haskell inclinado cartesianamente (prefiere la comida griega, evita las cosas picantes de la India, inspirada en Lex Augusteijn "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)

Doctor en Filosofía. El programador Haskell (se comió tantos plátanos que se le salieron los ojos, ¡ahora necesita lentes nuevos!)

-- 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

Programador posdoctoral de Haskell (de Uustalu, Vene y Pardo, "Esquemas de recursión de 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]

Answer 30

Esquema

Aquí hay una definición recursiva simple:

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

En Scheme, las funciones recursivas de cola usan el espacio de pila constante. Aquí hay una versión de factorial que es recursiva de la cola:

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