الوظيفية:بناء قائمة من الأعداد الصحيحة 1..n

Question

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

بلدي التي فرضتها على نفسها مهمة لكتابة وظيفة أن يبني قائمة من الأعداد الصحيحة من 1 إلى n.على سبيل المثال قائمة(7) يجب أن تعود [1,2,3,4,5,6,7].O(n) لن يكون الحل المثالي.

فإنه من السهل لإنشاء قائمة في الاتجاه المعاكس (أي [n,n-1,..,1]) في الزمن الخطي:

fun list 1 = 1::nil
|   list n = n::list(n-1);

محاولة بناء قائمة للمضي قدما O(n^2) لأن إلحاق العملية هو الخطية.

fun list 1 = 1::nil
|   list n = list(n-1) @ n::nil;

التالي كان محاولة لبناء قائمة من النهاية إلى الأمام (اليمين إلى اليسار) خلال البدء مع النيل, ربط n إلى الجبهة ، recursing إلى الوراء إلى 1.لكنه لم يعمل على الإطلاق.

fun list n = (if n = 1
              then 1
              else list(n-1) :: n) :: nil;

شيء يجعلني أعتقد أنني في حاجة الى وظيفة مساعد الذي يبني الأمم المتحدة إنهاء قوائم تستخدم في الإعادة لكن أنا الحيرة.

Answer 1

باستخدام أساس المكتبة,

fun list n = List.tabulate (n, fn x => x + 1)

مع بسيطة المتوازي ،

val list =
    let fun list' k 0 = k
          | list' k n = list' (n::k) (n-1)
    in list' nil end

هذا يبني قائمة بدءا من نهاية الذيل.إذا كنت تعتقد أن من التخفيضات ،

   list 5
=> list' nil 5
=> list' (5::nil) 4
=> list' (4::5::nil) 3
=> list' (3::4::5::nil) 2
=> list' (2::3::4::5::nil) 1
=> list' (1::2::3::4::5::nil) 0
=> [1, 2, 3, 4, 5]

بدلا من ذلك ،

شيء يجعلني أعتقد أنني في حاجة الى وظيفة مساعد الذي يبني الأمم المتحدة إنهاء قوائم تستخدم في الإعادة لكن أنا الحيرة.

تمثيل من غير منهي قائمة دالة التي تأخذ قائمة بإرجاع قائمة:على سبيل المثال ، تمثل 10::_, هل يمكن استخدام fn x => 10::x.

fun list n =
    let fun list' m k = if m > n then k nil else
                        list' (m+1) (fn x => k (m::x))
    in list' 1 (fn x => x) end

مرة أخرى, إذا كنت تعتقد من التخفيضات ،

   list 5
=> list' 1 (fn x => x)
=> list' 2 (fn x => (fn x => x) (1::x))
=> list' 3 (fn x => (fn x => (fn x => x) (1::x)) (2::x))
=> list' 4 (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x))
=> list' 5 (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x))
=> list' 6 (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x))
=> (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x)) nil
=> (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::nil)
=> (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::5::nil)
=> (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::4::5::nil)
=> (fn x => (fn x => x) (1::x)) (2::3::4::5::nil)
=> (fn x => x) (1::2::3::4::5::nil)
=> [1, 2, 3, 4, 5]

في هذه الحالة, يمكن أن تكون خوارزمية منظم بحيث عادي البيانات هيكل يكفي المجمع ، ولكن باستخدام استمرار باعتبارها تراكم قوية جدا ومفيدة التقنية التي ينبغي عدم إغفالها.

Answer 2

ونهج واحد الكلاسيكي هو لبنائه في ترتيب عكسي، ثم عكس ذلك. هذا مرتين O (ن)، الذي هو بطبيعة الحال مثلما O (ن).

Answer 3

إليك الحل:

fun list n =
  let
    fun f 1 m = m::nil
    |   f n m = m::f (n-1) (m+1)
  in
    f n 1
  end;

Answer 4

وهنا نسخة باستخدام وظيفة مساعد وتراكم-تمكين ذيل العودية:

fun list n =
  let
    fun aux i acc = 
      if i > 0
      then aux (i-1) (i::acc)
      else acc
  in
    aux n nil
  end;

Answer 5

مع قائمة مشاكل مثل هذه ، فإنه غالبا ما يكون من الأسهل لحل مشكلة أعم.

كيف يمكنني إنشاء قائمة تحتوي على الأعداد الصحيحة أنا مثل أن n <= أنا <= m, في النظام ؟

الحل لديه قاعدة القضية التعريفي خطوة:

• إذا n > m, قائمة فارغة.

• إذا n <= m, الحل هو أن يكتب n تليها حل المشكلة n+1 <= أنا <= m.

هذا الرأي يؤدي بسرعة إلى واضحة وموجزة مل رمز (اختبار):

fun range n m = if n > m then [] else n :: range (n+1) m
fun list n = range 1 n

Answer 6

(define (iota n)
  (let f ((i n)(a '())
    (if (zero? i)
        (reverse a)
        (f (- i 1) (cons i a)))))