اجتياز وتعديل الرسم البياني الحلقية الموجهة غير المتجانسة في سكالا

0

اجتياز وتعديل الرسم البياني الحلقية الموجهة غير المتجانسة في سكالا

صباح الخير جميعا.

لدي بنية بيانات الرسم البياني الحلقية الموجهة التالية ، المنفذة في سكالا على النحو التالي:

abstract class Node // Generic abstract node

/** Various kind of leaf nodes */
case class LeafNodeA(x: String) extends Node
case class LeafNodeB(x: Int) extends Node

/** Various kind of inner nodes */
case class InnerNode1(x: String, depRoleA: Node) extends Node
case class InnerNode2(x: String, y: Double, depRoleX: Node, depRoleY: Node) extends Node
case class InnerNode3(x: List[Int], depRoleA: Node, y: Int, 
                      depRoleB: Node, depRoleG: Node) extends Node

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

مشكلة الاجتياز

لاحظ أنني اتصلت بمجالات التبعية المختلفة لفئات الحالة بأسماء مختلفة لأنها تمثل أدوارًا مختلفة في التبعيات (على سبيل المثال ، depRoleX له دور مختلف عن depRoleY في InnerNode2 اكتب العقدة). لهذا السبب لا أعتقد أنه من الممكن تخزين تبعيات كل عقدة في List[Node] كما هو الحال في أي تطبيق شجرة / داج تافه يمكنك اكتشافه ، لأن معنى كل حقل تبعية مختلف.

بالطبع عندما أجتاز هذه البنية ، يجب أن أقوم بمطابقة الأنماط لفهم نوع العقدة التي أتعامل معها في خطوة العودية الحالية:

// Random function which returns the list of all the String attributes of the nodes
def getAllStrings(dag: Node): List[String] = { 
  dag match {
    case LeafNodeA(x) => List(x)
    case LeafNodeB => List()
    case InnerNode1(x, dr) => List(x) ::: getAllStrings(dr)
    case InnerNode2(x, _, dX, dY) => List(x) ::: getAllStrings(dX) :: getAllStrings(dY)
    case InnerNode3(_, dA, _, dB, dG) => getAllStrings(dA) ::: getAllStrings(dB) ::: getAllStrings(dG)
  }
}

لنفترض الآن أنه بدلاً من هذه الأنواع الخمسة من العقد البسيطة نسبيًا ، لدي حوالي 20 نوعًا من العقدة. ستصبح الوظيفة السابقة طويلة للغاية ومتكررة (أ case بيان لكل نوع عقدة). والأسوأ من ذلك: في كل مرة أريد فيها القيام بعملية اجتياز يجب أن أفعل الشيء نفسه.

التفكير في هذه المشكلة توصلت إلى حلين.

الطريقة الخارجية للانتقال

الطريقة الأولى (الواضحة) للتعامل مع هذا هي تعديل الطريقة السابقة في تحديد دالة اجتياز DAG عامة.

object DAGManipulator {
  def getDependencies(dag: Node): List[Node] = {
    dag match {
        case LeafNodeA => List()
        case LeafNodeB => List()
        case InnerNode1(_, dr) => List(dr)
        case InnerNode2(_, _, dX, dY) => List(dX, dY)
        case InnerNode3(_, dA, _, dB, dG) => List(dA, dB, dG)
    }
  }
}

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

طريقة فئة مجردة للحصول على التبعيات

الحل الثاني الذي توصلت إليه هو إعطاء طريقة إضافية لكل عقدة بالطريقة التالية:

abstract class Node {
  def getDependencies : List[Node]
}

case class LeafNodeA(x: String) extends Node = {
  override def getDependencies : List[Node] = List()
}
case class LeafNodeB(x: Int) extends Node = {
  override def getDependencies : List[Node] = List()
}

/** Various kind of inner nodes */
case class InnerNode1(x: String, depRoleA: Node) extends Node = {
  override def getDependencies : List[Node] = List()
}

case class InnerNode2(x: String, y: Double, depRoleX: Node, depRoleY: Node) extends Node = {
  override def getDependencies : List[Node] = List(depRoleX, depRoleY)
}

case class InnerNode3(x: List[Int], depRoleA: Node, y: Int, 
                      depRoleB: Node, depRoleG: Node) extends Node = {
  override def getDependencies : List[Node] = List(depRoleA, depRoleB, depRoleG)
}

لا يعجبني أي من الحلول السابقة:

  1. يجب تحديث الأولى في كل مرة يتم فيها إضافة نوع عقدة جديد إلى التسلسل الهرمي. بالإضافة إلى ذلك ، فإنه يفوض ميزة أساسية لهيكل DAG (الاجتياز) إلى كائن خارجي ، أجده مزعجًا للغاية من وجهة نظر هندسة البرمجيات.

  2. الحل الثاني في رأيي أسوأ من ذلك لأن كل نوع عقدة يجب عليه بشكل أساسي أن يذكر تبعياته بشكل متكرر (مرة في حقوله ومرة في getDependencies طريقة. أجد هذا قبيحًا جدًا وعرضة لأخطاء البرمجة.

هل لديك حل أفضل لهذه المشكلة؟

مشكلة التحديث

المشكلة الثانية التي يجب أن أتعامل معها هي تحديث / تعديل هيكل البيانات.

افترض أن لدي DAG محددة بالطريقة التالية.

val l1 = LeafNodeB(1)
val dag =
  InnerNode3(List(1, 2, 3),
    InnerNode1("InnerNode1", LeafNodeA("leafA1")),
    1, l1, InnerNode2("InnerNode2", 2, l1, LeafNodeA("leafA2")))

المقابلة لهذا الهيكل .

افترض أنني أريد تغيير LeafNodeA("leafA1") (وهي تبعية لل InnerNode1 ) على سبيل المثال ، l1 ، وهو أ LeafNodeB .

هذا هو نوع العملية التي يتعين علي القيام بها:

def modify(dag: Node): Node = {
  dag match {
    case x: InnerNode1 => if(x.x == "InnerNode1") x.copy(depRoleA = l1) else x
    case x: LeafNodeB => x
    case x: LeafNodeA => x
    case x: InnerNode2 => x.copy(depRoleX = modify(x.depRoleX), depRoleY = modify(x.depRoleY))
    case x: InnerNode3 => x.copy(depRoleA = modify(x.depRoleA), depRoleB = modify(x.depRoleB), depRoleG = modify(x.depRoleG))
  }
}

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

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

هل لديك حل / تصميم أفضل لاستراتيجية التحديث هذه؟

1 إجابة

0

لمعالجة هذه المشكلة:

The first one must be updated every time a new node type is added to the hierarchy. In addition to this, it delegates a fundamental feature of the DAG structure (traversal) to an external object, which I find very unpleasant from the software engineering point of view.

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

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

abstract class NodeF[+A] // Generic abstract node

/** Various kind of leaf nodes */
case class LeafNodeA(x: String) extends NodeF[Nothing]
case class LeafNodeB(x: Int) extends NodeF[Nothing]

/** Various kind of inner nodes */
case class InnerNode1[A](x: String, depRoleA: A) extends NodeF[A]
case class InnerNode2[A](x: String, y: Double, depRoleX: A, depRoleY: A) extends NodeF[A]
case class InnerNode3[A](x: List[Int], depRoleA: A, y: Int, 
                      depRoleB: A, depRoleG: A) extends NodeF[A]


implicit val nodeFunctor: Functor[NodeF] = new Functor[NodeF] {
  def map[A, B](fa: NodeF[A])(f: A => B): NodeF[B] = fa match {
    case LeafNodeA(x) => LeafNodeA(x)
    case LeafNodeB(x) => LeafNodeB(x)
    case InnerNode1(x, depA) => InnerNode1(x, f(depA))
    case InnerNode2(x, y, depX, depY) => InnerNode2(x, y, f(depX), f(depY))
    case InnerNode3(x, depA, y, depB, depG) => InnerNode3(x, f(depA), y, f(depB), f(depG))
  }
}

ولكن بعد ذلك يخفي العودية منك بشكل أساسي ويمكنك بسهولة تحديد هذه الأنواع من الأشياء:

type FixNode = Fix[NodeF]

def someExprGeneric[T](implicit T : Corecursive.Aux[T, NodeF]): T =
  InnerNode2("hello", 1.0, InnerNode1("world", LeafNodeA("!").embed).embed, LeafNodeB(1).embed).embed

val someExpr = someExprGeneric[FixNode]

def getStrings: Algebra[NodeF, List[String]] = {
  case LeafNodeA(x) => List(x)
  case LeafNodeB(_) => List()
  case InnerNode1(x, depA) => x :: depA
  case InnerNode2(x, _, depX, depY) => x :: depX ::: depY
  case InnerNode3(_, depA, _, depB, depG) => depA ::: depB ::: depG
}

someExpr.cata(getStrings)  // List("hello", "world", "!")

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

def expandToUniverse: Algebra[NodeF, Node] = {
  case InnerNode1("world", dep) => InnerNode1("universe", dep).embed
  case x => x.embed
}

someExpr.cata(expandToUniverse).cata(getStrings)  // List("hello", "universe", "!")

نظرًا لأنك فوضت هذا العودية ، فما عليك سوى تنفيذ الحالة (الحالات) التي تهتم بها حقًا.

:مؤلف

أسئلة ذات صلة

فوق
قائمة طعام