الخوارزميات العاملية بلغات مختلفة

StackOverflow https://stackoverflow.com/questions/23930

  •  09-06-2019
  •  | 
  •  

سؤال

أريد أن أرى جميع الطرق المختلفة التي يمكنك التوصل إليها، من أجل روتين فرعي عاملي، أو برنامج.الأمل هو أن يتمكن أي شخص من القدوم إلى هنا ومعرفة ما إذا كان يرغب في تعلم لغة جديدة.

الأفكار:

  • إجرائية
  • وظيفي
  • وجوه المنحى
  • بطانات واحدة
  • غامض
  • غريب الأطوار
  • رمز سيء
  • متعدد اللغات

أريد في الأساس أن أرى مثالاً لطرق مختلفة لكتابة خوارزمية، وكيف ستبدو في اللغات المختلفة.

يرجى قصره على مثال واحد لكل إدخال.سأسمح لك بالحصول على أكثر من مثال واحد لكل إجابة، إذا كنت تحاول تسليط الضوء على أسلوب أو لغة معينة أو مجرد فكرة مدروسة تتناسب مع وجودها في منشور واحد.

الشرط الحقيقي الوحيد هو أنه يجب العثور على مضروب وسيطة معينة، في جميع اللغات الممثلة.

كن مبدعا!

المبدأ التوجيهي الموصى به:

# Language Name: Optional Style type

   - Optional bullet points

    Code Goes Here

Other informational text goes here

سأقوم أحيانًا بتحرير أي إجابة لا تحتوي على تنسيق لائق.

هل كانت مفيدة؟

المحلول

متعدد اللغات:5 لغات، جميعها تستخدم لغة Bignums

لذلك، كتبت لغة متعددة اللغات تعمل باللغات الثلاث التي أكتب بها غالبًا، بالإضافة إلى واحدة من إجابتي الأخرى على هذا السؤال وواحدة تعلمتها للتو اليوم.إنه برنامج مستقل يقرأ سطرًا واحدًا يحتوي على عدد صحيح غير سالب ويطبع سطرًا واحدًا يحتوي على مضروبه.يتم استخدام Bignums في جميع اللغات، وبالتالي فإن الحد الأقصى للمضروب القابل للحساب يعتمد فقط على موارد جهاز الكمبيوتر الخاص بك.

  • بيرل:يستخدم حزمة Bignum المضمنة.إركض مع perl FILENAME.
  • هاسكل:يستخدم bignums المدمج.إركض مع runhugs FILENAME أو ما يعادل المترجم المفضل لديك.
  • سي ++:يتطلب GMP لدعم bignum.للتجميع باستخدام g++، استخدم g++ -lgmpxx -lgmp -x c++ FILENAME للربط ضد المكتبات الصحيحة.بعد التجميع، قم بتشغيل ./a.out.أو استخدم ما يعادل المترجم المفضل لديك.
  • Brainf*ck:لقد كتبت بعض الدعم الكبير في هذا المشنور.استخدام توزيع مولر الكلاسيكي, ، جمع مع bf < FILENAME > EXECUTABLE.اجعل الإخراج قابلاً للتنفيذ وقم بتشغيله.أو استخدم التوزيعة المفضلة لديك.
  • مسافة بيضاء:يستخدم دعم Bignum المدمج.إركض مع wspace FILENAME.

يحرر: تمت إضافة مسافة بيضاء كلغة خامسة.بالمناسبة، افعل لا لف الكود ب <code> العلامات؛يكسر المسافة البيضاء.أيضًا، يبدو الرمز أجمل بكثير في العرض الثابت.

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

نصائح أخرى

رمز لول:

آسف لم أتمكن من مقاومة الانجاز

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

هذه واحدة من أسرع الخوارزميات، حتى 170!.هو - هي فشل لسبب غير مفهوم يتجاوز 170!، وهو بطيء نسبيًا بالنسبة للمضروبات الصغيرة، ولكن بالنسبة للمضروبات الواقعة بين 80 و 170 إنه سريع للغاية مقارنة بالعديد من الخوارزميات.

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

هناك أيضًا واجهة عبر الإنترنت، جربه الآن!

اسمحوا لي أن أعرف إذا وجدت خطأ، أو تنفيذ أسرع للمضروبات الكبيرة.

يحرر:

هذه الخوارزمية أبطأ قليلاً، ولكنها تعطي نتائج تتجاوز 170:

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

كما أنه يبسطها إلى تمثيلات أخرى مختلفة.

ج++:البرمجة الفوقية للقالب

يستخدم اختراق التعداد الكلاسيكي.

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

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

الاستخدام.

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

يتم حساب العامل بالكامل في وقت الترجمة بناءً على معلمة القالب n.لذلك، يكون العامل<4>::result ثابتًا بمجرد انتهاء المترجم من عمله.

مسافة بيضاء

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

كان من الصعب عرضه هنا بشكل صحيح، ولكنني حاولت الآن نسخه من المعاينة وقد نجح الأمر.تحتاج إلى إدخال الرقم والضغط على زر الإدخال.

أجد التطبيقات التالية مضحكة للغاية:

تطور مبرمج هاسكل

تطور مبرمج بايثون

يتمتع!

بحث C#:

لا يوجد شيء لحسابه حقًا، فقط ابحث عنه.لتوسيعه، أضف 8 أرقام أخرى إلى الجدول وستكون الأعداد الصحيحة 64 بت عند الحد الأقصى.علاوة على ذلك، هناك حاجة إلى فئة 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];
}

كسول ك

أصبحت كوابيس البرمجة الوظيفية الخالصة حقيقة!

الوحيد لغة برمجة تورينج كاملة التي لديها:

  • أساس ونواة ومكتبات وظيفية بحتة --- في الواقع، إليك واجهة برمجة التطبيقات الكاملة: إس كي آي
  • لا لامدا حتى!
  • لا أعداد أو القوائم المطلوبة أو المسموح بها
  • لا يوجد تكرار واضح ولكن حتى الآن، يسمح العودية
  • بسيط تيار كسول لانهائيآلية الإدخال/الإخراج المستندة إلى

إليك رمز العامل بكل مجده بين قوسين:

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)

سمات:

  • لا الطرح أو الشرطية
  • طباعة جميع العوامل (إذا انتظرت لفترة كافية)
  • يستخدم طبقة ثانية من أرقام الكنيسة لتحويل العامل N إلى N!العلامات النجمية تليها السطر الجديد
  • يستخدم Y الموحد للعودية

إذا كنت مهتمًا بمحاولة فهمه، فإليك الكود المصدري للمخطط الذي سيتم تشغيله من خلال برنامج التحويل البرمجي 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))

(للحصول على تعريفات مناسبة لـ Y، وcons، و1، و10، و42، و1+، و*).

يحرر:

عامل Lazy K في النظام العشري

(10KB من رطانة وإلا سألصقه).على سبيل المثال، في موجه Unix:

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

بطيئة إلى حد ما بالنسبة للأرقام أعلاه، على سبيل المثال، 5.

الكود منتفخ نوعًا ما لأنه يتعين علينا تضمينه رمز المكتبة لجميع البدائيين لدينا (الكود مكتوب في ضبابي, ، مترجم حساب التفاضل والتكامل لامدا ومترجم LC-to-Lazy K مكتوب بلغة هاسكل).

XSLT 1.0

ملف الإدخال، Factorial.xml:

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

ملف 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>

احفظ كلا الملفين في نفس الدليل وافتحهما Factorial.xml في آي إي.

بايثون:وظيفية، بطانة واحدة

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

ملحوظة:

  • وهو يدعم الأعداد الصحيحة الكبيرة.مثال:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
  • لا يعمل من أجل ن <0.

الألغام المضادة للأفراد (غريب الأطوار / بطانة واحدة):

×/⍳X
  1. ⍳X يوسع X إلى مصفوفة من الأعداد الصحيحة 1..X
  2. ×/ يضاعف كل عنصر في المصفوفة

أو مع المشغل المدمج:

!X

مصدر: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt

بيرل6

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

بالكاد أعرف عن Perl6.ولكن أعتقد هذا [*] المشغل هو نفس مشغل هاسكل product.

يعمل هذا الرمز على الصلصال, ، و ربما ببغاء (لم أتحقق من ذلك.)

يحرر

يعمل هذا الرمز أيضا.

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

# This function(?) call like below ... It looks like mathematical notation.
say 10!;

التجميع x86-64:إجرائية

يمكنك استدعاء هذا من C (تم اختباره فقط مع مجلس التعاون الخليجي على Linux amd64).تم تجميع الجمعية مع 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

بشكل متكرر في إعلام 7

(يذكرك بـ COBOL لأنه مخصص لكتابة المغامرات النصية؛الخط النسبي متعمد):

لتحديد الرقم الذي يمثل مضروب (n - رقم):
إذا كانت n تساوي صفرًا، فاختر واحدًا؛
بخلاف ذلك، حدد مضروب (n ناقص واحد) في n.

إذا كنت تريد بالفعل استدعاء هذه الوظيفة ("العبارة") من لعبة ما، فأنت بحاجة إلى تحديد إجراء وقاعدة نحوية:

"لعبة المضروب" [يجب أن يكون هذا هو السطر الأول من المصدر]

هناك غرفة.[يجب أن يكون هناك واحد على الأقل!]

التخصيم هو إجراء ينطبق على رقم.

افهم "مضروب [رقم]" على أنه تحليل.

إجراء عملية التخصيم:
دع n يكون مضروب الرقم المفهوم؛
قل "إنها [ن]".

ج#:لينك

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

إيرلانج:الذيل العودي

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

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

هاسكل:

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

Brainf * المسيخ

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

كتبه مايكل Reitzenstein.

أساسي:مدرسة قديمة

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

الدفعة (NT):

@echo off

set n=%1
set result=1

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

echo %result%

الاستخدام:ج:>factorial.bat 15

F#:وظيفي

إلى الأمام مباشرة:

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

الحصول على الهوى:

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

برولوج العودية

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

الذيل العودي 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).

روبي العودية

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

الاستخدام:

factorial[5]
 => 120

مخطط

فيما يلي تعريف عودي بسيط:

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

في المخطط، تستخدم الوظائف العودية مساحة مكدس ثابتة.فيما يلي نسخة من العامل الذي يكون متكررًا:

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

أمثلة غريبة؟ماذا عن استخدام وظيفة جاما!منذ، Gamma n = (n-1)!.

أوكامل:باستخدام جاما

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

طالبة هاسكل مبرمج

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

مبرمج Sophomore Haskell ، في معهد ماساتشوستس للتكنولوجيا (مخطط الدراسة كطالب جديد)

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

مبرمج جونيور هاسكل (بداية لاعب بيانو)

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

مبرمج هاسكل جونيور آخر (اقرأ أن أنماط N+K هي "جزء مثير للاشمئزاز من Haskell" [1] وانضم إلى "أنماط Ban N+K"-الحركة [2])

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

كبار مبرمج هاسكل (تم التصويت عليه لصالح نيكسون بوكانان بوش - "يميل يمينًا")

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

مبرمج هاسكل آخر (تم التصويت عليه لصالح McGovern Biafra Nader - "يميل اليسار")

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

بعد مبرمج هاسكل آخر (انحنى حتى الآن إلى اليمين ، عاد إلى اليسار مرة أخرى!)

-- using foldr to simulate foldl

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

مذكرات Haskell Programmer (يأخذ Ginkgo Biloba Daily)

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

fac n = facs !! n

مبرمج هاسكل "خالي من النقاط) غير المنطقي (درس في أكسفورد)

fac = foldr (*) 1 . enumFromTo 1

مبرمج Haskell التكراري (مبرمج 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

مبرمج Haskell التكراري الواحد (APL و C السابق المبرمج)

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

تراكم مبرمج Haskell (بناء ما يصل إلى ذروة سريعة)

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

fac = facAcc 1

مبرمج Haskell الذي يمتاز بالاستمرار (Resured Ranravits في السنوات الأولى ، ثم انتقل إلى New Jersey)

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

fac = facCps id

Boy Scout Haskell Programmer (يحب ربط عقدة ؛دائمًا "التبجيل" ، ينتمي إلى كنيسة أقل نقطة ثابتة [8])

y f = f (y f)

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

Combinatory Haskell Programmer (يتجنب المتغيرات ، إن لم يكن التشويش ؛كل هذا الكاري هو مجرد مرحلة، على الرغم من أنه نادرا ما يعيق)

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

ترميز القائمة Haskell Programmer (يفضل الاعتماد في أحادي)

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

مبرمج Haskell التفسيري (لم يعجبه أبدًا لغة لم يعجبه)

-- 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 (يفعل ذلك مع الفصل ، لقد حصل على هذا Fundep Jones!بعد كتاب توماس هالجرين "المرح مع التبعيات الوظيفية" [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

بداية المبرمج Haskell الدراسات العليا (يميل تعليم الدراسات العليا إلى تحرير واحد من المخاوف البسيطة حول ، على سبيل المثال ، كفاءة الأعداد الصحيحة القائمة على الأجهزة)

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

اوريغاميست هاسكل مبرمج (يبدأ دائمًا مع "طية الطيور الأساسية")

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

مبرمج Haskell المتوافق مع ديكارت (يفضل الطعام اليوناني ، يتجنب الأشياء الهندية الحارة ؛مستوحاة من "فرز الأشكال" لليكس أوغسطين [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)

دكتوراه.مبرمج Haskell (أكل الكثير من الموز لدرجة أن عينيه قد تلاشت ، والآن يحتاج إلى عدسات جديدة!)

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

مبرمج Haskell بعد DOC (من مخططات عودية Uustalu و Vene و Pardo من 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

أستاذ محكم (تدريس هاسكل للطلاب الجدد)

fac n = product [1..n]

قوالب د:وظيفي

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

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

أو 

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

تستخدم مثل هذا:

factorial!(5)

جافا 1.6:متكرر، محفوظ (للمكالمات اللاحقة)

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

بوويرشيل

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

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

    $result 
}

وهنا بطانة واحدة:

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

سحق:العودية

في باش والعودي، ولكن مع ميزة إضافية تتمثل في التعامل مع كل تكرار في عملية جديدة.الحد الأقصى الذي يمكن حسابه هو!20 قبل أن يفيض، ولكن لا يزال بإمكانك تشغيله لأعداد كبيرة إذا كنت لا تهتم بالإجابة وتريد أن يسقط نظامك؛)

#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top