كيف يمكنني تطبيق نمط إثراء مكتبتي على مجموعات Scala؟

Question

أحد أقوى الأنماط المتوفرة في Scala هو نمط إثراء مكتبتي*، والذي يستخدم التحويلات الضمنية لـ يظهر لإضافة أساليب إلى الفئات الموجودة دون الحاجة إلى تحليل الطريقة الديناميكية.على سبيل المثال، إذا أردنا أن يكون لجميع السلاسل هذه الطريقة spaces من خلال حساب عدد أحرف المسافة البيضاء الموجودة لديهم، يمكننا:

class SpaceCounter(s: String) {
  def spaces = s.count(_.isWhitespace)
}
implicit def string_counts_spaces(s: String) = new SpaceCounter(s)

scala> "How many spaces do I have?".spaces
res1: Int = 5

لسوء الحظ، يواجه هذا النمط مشكلة عند التعامل مع المجموعات العامة.على سبيل المثال، تم طرح عدد من الأسئلة حول تجميع العناصر بالتسلسل مع المجموعات.لا يوجد شيء مدمج يعمل في لقطة واحدة، لذا يبدو هذا مرشحًا مثاليًا لنمط إثراء مكتبتي باستخدام مجموعة عامة C ونوع العنصر العام A:

class SequentiallyGroupingCollection[A, C[A] <: Seq[A]](ca: C[A]) {
  def groupIdentical: C[C[A]] = {
    if (ca.isEmpty) C.empty[C[A]]
    else {
      val first = ca.head
      val (same,rest) = ca.span(_ == first)
      same +: (new SequentiallyGroupingCollection(rest)).groupIdentical
    }
  }
}

باستثناء ذلك بالطبع لا يعمل.يخبرنا REPL:

<console>:12: error: not found: value C
               if (ca.isEmpty) C.empty[C[A]]
                               ^
<console>:16: error: type mismatch;
 found   : Seq[Seq[A]]
 required: C[C[A]]
                 same +: (new SequentiallyGroupingCollection(rest)).groupIdentical
                      ^

هناك مشكلتان:كيف نحصل على C[C[A]] من فارغة C[A] قائمة (أو من فراغ)؟وكيف نحصل على C[C[A]] العودة من same +: سطر بدلاً من أ Seq[Seq[A]]?

* ^{كانت تُعرف سابقًا باسم Pimp-my-library.}

Answer 1

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

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

والآن السؤال هو:من أين نأتي بنائيننا؟المكان الواضح هو من المجموعة نفسها. هذا لا يعمل.لقد قررنا بالفعل، عند الانتقال إلى مجموعة عامة، أننا سننسى نوع المجموعة.لذا، على الرغم من أن المجموعة قد تُرجع مُنشئًا يمكنه إنشاء المزيد من المجموعات من النوع الذي نريده، إلا أنه لن يعرف ما هو النوع.

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

لذا، أمامنا قفزتان مفاهيميتان يجب القيام بهما:

1. نحن لا نستخدم عمليات التجميع القياسية، بل نستخدم أدوات البناء.
2. نحصل على هؤلاء البناة من ضمنا CanBuildFroms، وليس من مجموعتنا مباشرة.

لنلقي نظرة على مثال.

class GroupingCollection[A, C[A] <: Iterable[A]](ca: C[A]) {
  import collection.generic.CanBuildFrom
  def groupedWhile(p: (A,A) => Boolean)(
    implicit cbfcc: CanBuildFrom[C[A],C[A],C[C[A]]], cbfc: CanBuildFrom[C[A],A,C[A]]
  ): C[C[A]] = {
    val it = ca.iterator
    val cca = cbfcc()
    if (!it.hasNext) cca.result
    else {
      val as = cbfc()
      var olda = it.next
      as += olda
      while (it.hasNext) {
        val a = it.next
        if (p(olda,a)) as += a
        else { cca += as.result; as.clear; as += a }
        olda = a
      }
      cca += as.result
    }
    cca.result
  }
}
implicit def iterable_has_grouping[A, C[A] <: Iterable[A]](ca: C[A]) = {
  new GroupingCollection[A,C](ca)
}

دعونا نفصل هذا.أولاً، من أجل بناء مجموعة المجموعات، نعلم أننا سنحتاج إلى بناء نوعين من المجموعات: C[A] لكل مجموعة، و C[C[A]] الذي يجمع كل المجموعات معًا.وبالتالي، نحن بحاجة إلى بنائين، أحدهما يأخذ Aق ويبني C[A]الصورة، والتي تأخذ C[A]ق ويبني C[C[A]]س.النظر في نوع التوقيع CanBuildFrom, ، نحن نرى

CanBuildFrom[-From, -Elem, +To]

مما يعني أن CanBuildFrom يريد معرفة نوع المجموعة التي نبدأ بها -- في حالتنا، C[A], ثم عناصر المجموعة التي تم إنشاؤها ونوع تلك المجموعة.لذلك نقوم بملء تلك المعلمات ضمنية cbfcc و cbfc.

وبعد أن أدركت هذا، هذا هو معظم العمل.يمكننا استخدام لدينا CanBuildFromلتزويدنا بالبناة (كل ما عليك فعله هو تطبيقهم).ويمكن لباني واحد أن يبني مجموعة به +=, ، قم بتحويلها إلى المجموعة التي من المفترض أن تكون معها في النهاية result, ، وأفرغ نفسه وكن مستعدًا للبدء من جديد clear.يبدأ المنشئون فارغين، مما يحل خطأ الترجمة الأول لدينا، وبما أننا نستخدم المنشئون بدلاً من التكرار، فإن الخطأ الثاني يختفي أيضًا.

هناك تفصيل صغير أخير - بخلاف الخوارزمية التي تقوم بالعمل بالفعل - في التحويل الضمني.لاحظ أننا نستخدم new GroupingCollection[A,C] لا [A,C[A]].وذلك لأن إعلان الفصل كان لـ C بمعلمة واحدة، والتي تملأها بنفسها A مرت عليه.لذلك نحن فقط نسلمه النوع C, ، والسماح لها بالإنشاء C[A] خروج منه.تفاصيل بسيطة، ولكنك سوف تحصل على أخطاء وقت الترجمة إذا حاولت بطريقة أخرى.

هنا، جعلت الطريقة أكثر عمومية قليلاً من مجموعة "العناصر المتساوية" - بدلاً من ذلك، تقوم الطريقة بتقطيع المجموعة الأصلية كلما فشل اختبار العناصر المتسلسلة.

دعونا نرى طريقتنا في العمل:

scala> List(1,2,2,2,3,4,4,4,5,5,1,1,1,2).groupedWhile(_ == _)
res0: List[List[Int]] = List(List(1), List(2, 2, 2), List(3), List(4, 4, 4), 
                             List(5, 5), List(1, 1, 1), List(2))

scala> Vector(1,2,3,4,1,2,3,1,2,1).groupedWhile(_ < _)
res1: scala.collection.immutable.Vector[scala.collection.immutable.Vector[Int]] =
  Vector(Vector(1, 2, 3, 4), Vector(1, 2, 3), Vector(1, 2), Vector(1))

إنها تعمل!

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

---

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

class GroupingCollection[A, C, D[C]](ca: C)(
  implicit c2i: C => Iterable[A],
           cbf: CanBuildFrom[C,C,D[C]],
           cbfi: CanBuildFrom[C,A,C]
) {
  def groupedWhile(p: (A,A) => Boolean): D[C] = {
    val it = c2i(ca).iterator
    val cca = cbf()
    if (!it.hasNext) cca.result
    else {
      val as = cbfi()
      var olda = it.next
      as += olda
      while (it.hasNext) {
        val a = it.next
        if (p(olda,a)) as += a
        else { cca += as.result; as.clear; as += a }
        olda = a
      }
      cca += as.result
    }
    cca.result
  }
}

لقد أضفنا هنا ضمنيًا يمنحنا Iterable[A] من C--بالنسبة لمعظم المجموعات، ستكون هذه هي الهوية فقط (على سبيل المثال: List[A] بالفعل هو Iterable[A])، ولكن بالنسبة للمصفوفات سيكون تحويلًا ضمنيًا حقيقيًا.وبالتالي، فقد أسقطنا هذا الشرط C[A] <: Iterable[A]--لقد قمنا للتو بوضع المتطلبات اللازمة لـ <% صريح، حتى نتمكن من استخدامه بشكل صريح حسب الرغبة بدلاً من أن يقوم المترجم بتعبئته لنا.كما قمنا أيضًا بتخفيف القيود المفروضة على مجموعتنا من المجموعات C[C[A]]--بدلاً من ذلك، أي شيء D[C], والتي سوف نقوم بتعبئتها لاحقا لتكون ما نريد.لأننا سنقوم بملء هذا لاحقًا، فقد دفعناه إلى مستوى الفصل بدلاً من مستوى الطريقة.خلاف ذلك، هو في الأساس نفسه.

والسؤال الآن هو كيفية استخدام هذا.بالنسبة للمجموعات العادية، يمكننا:

implicit def collections_have_grouping[A, C[A]](ca: C[A])(
  implicit c2i: C[A] => Iterable[A],
           cbf: CanBuildFrom[C[A],C[A],C[C[A]]],
           cbfi: CanBuildFrom[C[A],A,C[A]]
) = {
  new GroupingCollection[A,C[A],C](ca)(c2i, cbf, cbfi)
}

حيث نقوم الآن بتوصيل C[A] ل C و C[C[A]] ل D[C].لاحظ أننا بحاجة إلى الأنواع العامة الصريحة عند الاستدعاء new GroupingCollection حتى يتمكن من الحفاظ على الأنواع التي تتوافق مع ماذا.شكرا ل implicit c2i: C[A] => Iterable[A], ، وهذا يعالج المصفوفات تلقائيًا.

ولكن مهلا، ماذا لو أردنا استخدام السلاسل؟نحن الآن في ورطة، لأنه لا يمكن أن يكون لديك "سلسلة من الخيوط".هذا هو المكان الذي يساعد فيه التجريد الإضافي:يمكننا الاتصال D شيء مناسب لعقد الأوتار.دعونا نختار Vector, ، وقم بما يلي:

val vector_string_builder = (
  new CanBuildFrom[String, String, Vector[String]] {
    def apply() = Vector.newBuilder[String]
    def apply(from: String) = this.apply()
  }
)

implicit def strings_have_grouping(s: String)(
  implicit c2i: String => Iterable[Char],
           cbfi: CanBuildFrom[String,Char,String]
) = {
  new GroupingCollection[Char,String,Vector](s)(
    c2i, vector_string_builder, cbfi
  )
}

نحن بحاجة إلى جديد CanBuildFrom للتعامل مع بناء متجه للسلاسل (لكن هذا أمر سهل حقًا، حيث نحتاج فقط إلى استدعاء Vector.newBuilder[String])، ومن ثم نحتاج إلى ملء جميع الأنواع حتى يتسنى لـ GroupingCollection تتم كتابته بشكل معقول.لاحظ أن لدينا بالفعل عائمة حول a [String,Char,String] CanBuildFrom، لذلك يمكن إنشاء سلاسل من مجموعات من الأحرف.

دعونا نجربها:

scala> List(true,false,true,true,true).groupedWhile(_ == _)
res1: List[List[Boolean]] = List(List(true), List(false), List(true, true, true))

scala> Array(1,2,5,3,5,6,7,4,1).groupedWhile(_ <= _) 
res2: Array[Array[Int]] = Array(Array(1, 2, 5), Array(3, 5, 6, 7), Array(4), Array(1))

scala> "Hello there!!".groupedWhile(_.isLetter == _.isLetter)
res3: Vector[String] = Vector(Hello,  , there, !!)

Answer 2

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

import scala.collection.generic.{ CanBuildFrom, FromRepr, HasElem }
import language.implicitConversions

class FilterMapImpl[A, Repr](val r : Repr)(implicit hasElem : HasElem[Repr, A]) {
  def filterMap[B, That](f : A => Option[B])
    (implicit cbf : CanBuildFrom[Repr, B, That]) : That = r.flatMap(f(_).toSeq)
}

implicit def filterMap[Repr : FromRepr](r : Repr) = new FilterMapImpl(r)

مما يضيف احترام "نفس نوع النتيجة". filterMap العملية للجميع GenTraversableLikeس،

scala> val l = List(1, 2, 3, 4, 5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> l.filterMap(i => if(i % 2 == 0) Some(i) else None)
res0: List[Int] = List(2, 4)

scala> val a = Array(1, 2, 3, 4, 5)
a: Array[Int] = Array(1, 2, 3, 4, 5)

scala> a.filterMap(i => if(i % 2 == 0) Some(i) else None)
res1: Array[Int] = Array(2, 4)

scala> val s = "Hello World"
s: String = Hello World

scala> s.filterMap(c => if(c >= 'A' && c <= 'Z') Some(c) else None)
res2: String = HW

وعلى سبيل المثال من السؤال، يبدو الحل الآن،

class GroupIdenticalImpl[A, Repr : FromRepr](val r: Repr)
  (implicit hasElem : HasElem[Repr, A]) {
  def groupIdentical[That](implicit cbf: CanBuildFrom[Repr,Repr,That]): That = {
    val builder = cbf(r)
    def group(r: Repr) : Unit = {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if(!rest.isEmpty)
        group(rest)
    }
    if(!r.isEmpty) group(r)
    builder.result
  }
}

implicit def groupIdentical[Repr : FromRepr](r: Repr) = new GroupIdenticalImpl(r)

عينة من جلسة REPL،

scala> val l = List(1, 1, 2, 2, 3, 3, 1, 1)
l: List[Int] = List(1, 1, 2, 2, 3, 3, 1, 1)

scala> l.groupIdentical
res0: List[List[Int]] = List(List(1, 1),List(2, 2),List(3, 3),List(1, 1))

scala> val a = Array(1, 1, 2, 2, 3, 3, 1, 1)
a: Array[Int] = Array(1, 1, 2, 2, 3, 3, 1, 1)

scala> a.groupIdentical
res1: Array[Array[Int]] = Array(Array(1, 1),Array(2, 2),Array(3, 3),Array(1, 1))

scala> val s = "11223311"
s: String = 11223311

scala> s.groupIdentical
res2: scala.collection.immutable.IndexedSeq[String] = Vector(11, 22, 33, 11)

مرة أخرى، لاحظ أن نفس مبدأ نوع النتيجة قد تمت ملاحظته بنفس الطريقة التي كان من الممكن أن يتم بها groupIdentical تم تعريفها مباشرة على GenTraversableLike.

Answer 3

اعتبارا من هذا الالتزام تغيرت التعويذة السحرية قليلاً عما كانت عليه عندما أعطى مايلز إجابته الممتازة.

الأعمال التالية، ولكن هل هو الكنسي؟آمل أن يقوم أحد الشرائع بتصحيح ذلك.(أو بالأحرى، المدافع، أحد الأسلحة الكبيرة.) إذا كان حد العرض هو الحد الأعلى، فستفقد التطبيق على Array وString.لا يبدو أنه يهم إذا كان الحد GenTraversableLike أو TraversableLike؛لكن IsTraversableLike يمنحك GenTraversableLike.

import language.implicitConversions
import scala.collection.{ GenTraversable=>GT, GenTraversableLike=>GTL, TraversableLike=>TL }
import scala.collection.generic.{ CanBuildFrom=>CBF, IsTraversableLike=>ITL }

class GroupIdenticalImpl[A, R <% GTL[_,R]](val r: GTL[A,R]) {
  def groupIdentical[That](implicit cbf: CBF[R, R, That]): That = {
    val builder = cbf(r.repr)
    def group(r: GTL[_,R]) {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if (!rest.isEmpty) group(rest)
    }
    if (!r.isEmpty) group(r)
    builder.result
  }
}

implicit def groupIdentical[A, R <% GTL[_,R]](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] =
  new GroupIdenticalImpl(fr conversion r)

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

class GroupIdenticalImpl[A, R](val r: GTL[A,R]) {
  def groupIdentical[That](implicit cbf: CBF[GT[A], GT[A], That]): That = {
    val builder = cbf(r.toTraversable)
    def group(r: GT[A]) {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if (!rest.isEmpty) group(rest)
    }
    if (!r.isEmpty) group(r.toTraversable)
    builder.result
  }
}

implicit def groupIdentical[A, R](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] =
  new GroupIdenticalImpl(fr conversion r)

تتضمن هذه المحاولة الأولى تحويلًا قبيحًا لـ Repr إلى GenTraversableLike.

import language.implicitConversions
import scala.collection.{ GenTraversableLike }
import scala.collection.generic.{ CanBuildFrom, IsTraversableLike }

type GT[A, B] = GenTraversableLike[A, B]
type CBF[A, B, C] = CanBuildFrom[A, B, C]
type ITL[A] = IsTraversableLike[A]

class FilterMapImpl[A, Repr](val r: GenTraversableLike[A, Repr]) { 
  def filterMap[B, That](f: A => Option[B])(implicit cbf : CanBuildFrom[Repr, B, That]): That = 
    r.flatMap(f(_).toSeq)
} 

implicit def filterMap[A, Repr](r: Repr)(implicit fr: ITL[Repr]): FilterMapImpl[fr.A, Repr] = 
  new FilterMapImpl(fr conversion r)

class GroupIdenticalImpl[A, R](val r: GT[A,R])(implicit fr: ITL[R]) { 
  def groupIdentical[That](implicit cbf: CBF[R, R, That]): That = { 
    val builder = cbf(r.repr)
    def group(r0: R) { 
      val r = fr conversion r0
      val first = r.head
      val (same, other) = r.span(_ == first)
      builder += same
      val rest = fr conversion other
      if (!rest.isEmpty) group(rest.repr)
    } 
    if (!r.isEmpty) group(r.repr)
    builder.result
  } 
} 

implicit def groupIdentical[A, R](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] = 
  new GroupIdenticalImpl(fr conversion r)