بطاريات حرف عطف و العودية

Question

لقد حللت 45 من المشاكل 4clojure.com و لاحظت مشكلة متكررة في الطريق أحاول حل بعض المشاكل باستخدام العودية و بطاريات.

سأحاول أن أشرح أفضل ما أستطيع ماذا أفعل أنا في نهاية المطاف مع بشعة حلول آمل أن بعض Clojurers أن "الحصول على" ما أنا لا تحصل على.

على سبيل المثال مشكلة 34 يسأل لكتابة وظيفة (دون استخدام مجموعة) مع اثنين من الاعداد الصحيحه كما الحجج يخلق مجموعة (دون استخدام مجموعة).ببساطة يمكنك القيام به (...1 7) ولا تحصل على (1 2 3 4 5 6).

الآن هذا السؤال ليس حول حل هذه المشكلة بالذات.

ماذا لو كنت تريد لحل هذه استخدام العودية و المتوازي ؟

بلدي عملية التفكير يذهب مثل هذا:

• أحتاج لكتابة وظيفة أخذ اثنين من الحجج ، أبدأ مع (fn [x y] )

• سوف تحتاج إلى recurse و سوف تحتاج إلى تتبع قائمة ، سوف تستخدم تراكمي ، لذلك أنا أكتب 2 وظيفة داخل أول واحد أخذ حجة إضافية:

  (fn [x y]
  ((fn g [x y acc] ...) x y '())

(يبدو أنني لا يمكن بشكل صحيح تنسيق Clojure رمز على هكذا!؟)

هنا أنا بالفعل لست متأكد أنا أفعل ذلك بشكل صحيح:أول وظيفة يجب أن تأخذ اثنين بالضبط صحيح الحجج (غير طلبي) وأنا لست متأكدا من:إذا كنت ترغب في استخدام اللاسلكي ، هل يمكنني استخدام البطاريات دون خلق متداخلة وظيفة ؟

ثم أريد أن حرف عطف, ولكن لا أستطيع أن أفعل:

(conj 0 1)

لذلك أفعل أشياء غريبة للتأكد من أنني قد حصلت على التسلسل الأول و أنا في نهاية المطاف مع هذا:

(fn
   [x y]
   ((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x)))
    x
    y
    '()))

لكن هذا ينتج هذا:

(1 (2 (3 4)))

بدلا من هذا:

(1 2 3 4)

لذلك أنا في نهاية المطاف القيام إضافية تتسطح ويعمل ولكنها قبيحة.

بدأت أفهم بعض الأشياء أنا حتى البدء في بعض الحالات إلى "التفكير" في أكثر clojuresque الطريقة ولكن لدي مشكلة في كتابة الحل.

على سبيل المثال هنا قررت:

• استخدام اللاسلكي
• إلى recurse بتزايد x حتى يصل إلى y

ولكن كنت في نهاية المطاف مع المسخ أعلاه.

وهناك الكثير من طريقة لحل هذه المشكلة و, مرة أخرى, ليس هذا ما اريده....

ما أنا بعد ما قررت سلبيات/حرف عطف ، استخدام اللاسلكي ، recurse, أنا يمكن في نهاية المطاف مع هذا (ليس مكتوب لي من قبل):

#(loop [i %1
        acc nil]
  (if (<= %2 i)
    (reverse acc)
    (recur (inc i) (cons i acc))))

بدلا من هذا:

((fn
  f
  [x y]
  (flatten
   ((fn
     g
     [x y acc]
     (if (= x y) acc (conj (conj acc (g (inc x) y acc)) x)))
    x
    y
    '())))
 1
 4)

أنا أعتبر بداية أن تكون قادرة على حل بعض المشاكل ولكن أنا قليلا بخيبة أمل من القبيح حلول لا تميل إلى إنتاج...

Answer 1

أعتقد أن هناك بضعة أشياء أن تعلم هنا.

أولا, نوع من القاعدة العامة - وظائف العودية وعادة ما يكون النظام الطبيعي ، إضافة المجمع عكس ذلك.يمكنك أن ترى ذلك لأنه عندما "طبيعية" (دون مركم) وظيفة العودية يدير يفعل بعض العمل لحساب قيمة ثم recurses لتوليد ذيل القائمة ، وأخيرا تنتهي مع قائمة فارغة.في المقابل ، مع تراكم ، عليك أن تبدأ مع قائمة فارغة و إضافة أشياء إلى الجبهة انه ينمو في الاتجاه الآخر.

لذا عادة عند إضافة تراكمي تحصل على عكس النظام.

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

لكن في حالتك هو الذهاب إلى هذه المسألة.أنت ذاهب للحصول على قائمة إلى الوراء:

(defn my-range-0 [lo hi] ; normal recursive solution
  (if (= lo hi)
    nil
    (cons lo (my-range-0 (inc lo) hi))))

(deftest test-my-range-1
  (is (= '(0 1 2) (my-range-0 0 3))))

(defn my-range-1 ; with an accumulator
  ([lo hi] (my-range-1 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (cons lo acc)))))

(deftest test-my-range-1
  (is (= '(2 1 0) (my-range-1 0 3)))) ; oops!  backwards!

وغالبا ما تكون أفضل ما يمكنك القيام به لإصلاح هذا هو تماما عكس تلك القائمة في نهاية المطاف.

ولكن هنا هناك بديل - يمكننا القيام به في الواقع عمل إلى الوراء.بدلا من تزايد انخفاض الحد الذي يمكن أن تنقيص ارتفاع الحد:

(defn my-range-2
  ([lo hi] (my-range-2 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (let [hi (dec hi)]
        (recur lo hi (cons hi acc))))))

(deftest test-my-range-2
  (is (= '(0 1 2) (my-range-2 0 3)))) ; back to the original order

[ملاحظة - هناك طريقة أخرى عكس الأشياء أدناه ؛ لم هيكل حجتي بشكل جيد للغاية]

الثاني, كما يمكنك أن ترى في my-range-1 و my-range-2, طريقة لطيفة من كتابة وظيفة مع المجمع هو وظيفة مع اثنين من مجموعات مختلفة من الحجج.يعطيك نظيفة جدا (imho) التنفيذ دون الحاجة إلى وظائف متداخلة.

---

أيضا لديك المزيد من الأسئلة العامة حول متواليات ، conj وما شابه ذلك.هنا clojure هو نوع من الفوضى ، ولكن من المفيد أيضا.أعلاه لقد تم إعطاء جدا وجهة النظر التقليدية مع سلبيات على أساس القوائم.ولكن clojure تشجع استخدام متواليات أخرى.وعلى عكس سلبيات قوائم ناقلات تنمو إلى اليمين وليس اليسار.لذلك آخر الطريق إلى عكس هذه النتيجة هو استخدام ناقلات:

(defn my-range-3 ; this looks like my-range-1
  ([lo hi] (my-range-3 lo hi []))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (conj acc lo)))))

(deftest test-my-range-3 ; except that it works right!
  (is (= [0 1 2] (my-range-3 0 3))))

هنا conj إضافة إلى اليمين.أنا لم تستخدم conj في my-range-1, حتى هنا هو إعادة كتابتها أن تكون أكثر وضوحا:

(defn my-range-4 ; my-range-1 written using conj instead of cons
  ([lo hi] (my-range-4 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (conj acc lo)))))

(deftest test-my-range-4
  (is (= '(2 1 0) (my-range-4 0 3))))

لاحظ أن هذه التعليمات البرمجية تبدو جدا على غرار my-range-3 ولكن النتيجة إلى الوراء لأننا بدأنا مع قائمة فارغة ، وليس فارغة ناقلات.في كلتا الحالتين ، conj يضيف عنصر جديد في "الطبيعية" الموقف.عن ناقل للحق ، ولكن انها قائمة على اليسار.

وأنه مجرد حدث لي أن كنت قد لا نفهم حقا ما قائمة.الأساس cons يخلق مربع تحتوي على أمرين (حجج).الأول هو محتويات والثاني هو بقية القائمة.حتى قائمة (1 2 3) هو في الأساس (cons 1 (cons 2 (cons 3 nil))).في المقابل, ناقلات [1 2 3] يعمل أكثر مثل مجموعة (على الرغم من أنني أعتقد أنه من تنفيذها باستخدام شجرة).

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

---

كل رمز أعلاه متوفرة في https://github.com/andrewcooke/clojure-lab

---

تحديث:لقد أعدت كتابة الاختبارات بحيث تكون النتيجة المتوقعة هي نقلت قائمة في الحالات التي يكون فيها رمز يولد قائمة. = مقارنة القوائم و ناقلات و العودة الحقيقية إذا كان المحتوى هو نفسه ، ولكن جعلها صريحة يظهر بوضوح أكثر ما كنت في الواقع الحصول على كل حال.علما بأن '(0 1 2) مع ' في الجبهة هو مجرد مثل (list 0 1 2) ـ ' يتوقف قائمة من يجري تقييمها (دون ذلك ، 0 سوف تعامل على أنها الأمر).

Answer 2

بعد قراءة كل ذلك ما زلت غير متأكد من السبب في أنك بحاجة إلى المجمع.

((fn r [a b]
    (if (<= a b) 
       (cons a (r (inc a) b)))) 
  2 4)
=> (2 3 4)

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

كيف وصلت إلى هذا الحل:

عندما كنت تفكر في استخدام العودية, أجد أنه يساعد في محاولة الدولة المشكلة مع أقل عدد ممكن حيث يمكنك التفكير و محاولة للتخلص من الكثير من "العمل" إلى العودية نفسها.

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

في هذه الحالة ماذا فكرت عندما بدأت الكتابة:"أول حجة على وظيفة هو أيضا بداية عنصر من مجموعة وآخر الحجة هو آخر عنصر".عودي التفكير هو شيء عليك أن تدرب نفسك على القيام به ، ولكن فكرة واضحة إلى حد ما الحل إذن هو أن نقول:a مجموعة [a, b] هو سلسلة بدءا من عنصر a تليها a مجموعة من [a + 1, b].لذلك يتراوح يمكن أن يكون في الواقع هو موضح بشكل متكرر.رمز كتبت إلى حد كبير المباشرة في تنفيذ هذه الفكرة.

إضافة:

لقد وجدت أن عند كتابة رمز وظيفي, بطاريات (الفهارس) هي الأفضل تجنبها.بعض المشاكل تتطلب منهم, ولكن إذا كان يمكنك أن تجد وسيلة للتخلص منهم ، وكنت عادة ما تكون أفضل حالا إذا كنت تفعل.

إضافة 2:

بخصوص وظائف العودية وقوائم/متواليات ، على أفضل طريقة التفكير عند كتابة هذا النوع من التعليمات البرمجية إلى الدولة مشكلتك في "البند الأول (رئيس) من قائمة" و "بقية القائمة (الذيل)".

Answer 3

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

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

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

فمن الصعب أن تتعلم من الكتب التي تتحدث عن ناقلات nth, حلقة ..تتكرر وهلم جرا ، ومن ثم تحقيق التعلم Clojure ينمو إلى الأمام من هناك.

واحدة من الأشياء التي كنت قد وجدت ما هو جيد عن التعلم Clojure ، هو المجتمع محترمة ومفيدة.بعد كل شيء, أنهم مساعدة شخص الأولى التي تعلم لغة Fortran الرابع على CDC الإنترنت مع البطاقات المثقبة والتي التجارية الأولى البرمجة لغة PL/I.

Answer 4

إذا لم تحل هذه باستخدام البطاريات أود أن تفعل شيئا مثل:

user=> (defn my-range [lb up c]
         (if (= lb up)
           c
           (recur (inc lb) up (conj c lb))))
#'user/my-range

ثم اتصل مع

#(my-range % %2 [])

بالطبع, كنت استخدم letfn أو شيء للحصول على حول عدم وجود defn المتاحة.

لذا نعم, كنت بحاجة الداخلية وظيفة لاستخدام المجمع النهج.

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

باستخدام ناقلات يساعد كثيرا لأن conj سوف إلحاقي إلى ذلك ، هناك حاجة لاستخدام reverse.

أنا على 4clojure جدا, راجع للشغل.لقد كنت مشغولا حتى لقد تخلفت في الآونة الأخيرة.

Answer 5

يبدو أن سؤالك هو أكثر حول "كيف تتعلم" ثم التقنية/مدونة المشكلة.كنت في نهاية المطاف في كتابة هذا النوع من التعليمات البرمجية من أي وسيلة أو مصدر تعلمت البرمجة بشكل عام أو Clojure محددة قد خلق "العصبية السريع" في الدماغ الذي يجعلك تفكر في الحلول في هذا الطريق وكنت في نهاية المطاف كتابة التعليمات البرمجية مثل هذا.في الأساس كلما كنت تواجه أي مشكلة (في هذه الحالة بالذات العودية و/أو تراكم) كنت في نهاية المطاف استخدام هذه "العصبية الطريق السريع" و تأتي دائما مع هذا النوع من التعليمات البرمجية .

الحل للتخلص من هذه "العصبية الطريق السريع" هو التوقف عن كتابة التعليمات البرمجية لحظة ، حافظ على لوحة المفاتيح بعيدا والبدء في قراءة الكثير من القائمة clojure رمز (من الحلول القائمة من 4clojure المشكلة إلى مشاريع مفتوحة المصدر على github) والتفكير بعمق (حتى قراءة وظيفة 2-3 مرات السماح حقا يستقر في الدماغ).بهذه الطريقة يمكنك أن ينتهي إلى تدمير الخاص بك القائمة "العصبية الطريق السريع" (التي تنتج البرمجية التي تكتب الآن) و خلق جديد "العصبية الطريق السريع" التي من شأنها أن تنتج جميلة الاصطلاحية Clojure رمز.أيضا ، ليس محاولة للقفز إلى كتابة التعليمات البرمجية في أقرب وقت رأيت مشكلة ، بل تعطي نفسك بعض الوقت للتفكير بوضوح وبعمق عن المشكلة والحلول.