Функциональный поиск в ширину в Scala с монадой состояния

Я пытаюсь реализовать функциональный поиск в ширину в Scala для вычисления расстояний между данным узлом и всеми остальными узлами в невзвешенном графе. Я использовал для этого State Monad с подписью: -

case class State[S,A](run:S => (A,S))

Другие функции, такие как карта, плоская карта, последовательность, изменение и т. д., аналогичны тем, что вы найдете внутри стандартной Монады состояния.

Вот код: -

case class Node(label: Int)

case class BfsState(q: Queue[Node], nodesList: List[Node], discovered: Set[Node], distanceFromSrc: Map[Node, Int]) {
  val isTerminated = q.isEmpty
}

case class Graph(adjList: Map[Node, List[Node]]) {
  def bfs(src: Node): (List[Node], Map[Node, Int]) = {
    val initialBfsState = BfsState(Queue(src), List(src), Set(src), Map(src -> 0))
    val output = bfsComp(initialBfsState)
    (output.nodesList,output.distanceFromSrc)
  }

  @tailrec
  private def bfsComp(currState:BfsState): BfsState = {
     if (currState.isTerminated) currState
     else bfsComp(searchNode.run(currState)._2)
  }

  private def searchNode: State[BfsState, Unit] = for {
    node <- State[BfsState, Node](s => {
      val (n, newQ) = s.q.dequeue
      (n, s.copy(q = newQ))
    })
    s <- get
    _ <- sequence(adjList(node).filter(!s.discovered(_)).map(n => {
      modify[BfsState](s => {
        s.copy(s.q.enqueue(n), n :: s.nodesList, s.discovered + n, s.distanceFromSrc + (n -> (s.distanceFromSrc(node) + 1)))
      })
    }))
  } yield ()
}

Пожалуйста, не могли бы вы посоветовать: -

  1. Должен ли State Transition при удалении из очереди в функции searchNode быть членом самой BfsState?
  2. Как сделать этот код более производительным/кратким/читабельным?

scala functional-programming breadth-first-search state-monad
person Aarsh Shah    schedule 16.08.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Во-первых, я предлагаю переместить все private def, связанные с bfs, в саму bfs. Это соглашение для методов, которые используются исключительно для реализации другого.

Во-вторых, я предлагаю просто не использовать State в этом отношении. State (как и большинство монад) относится к композиции. Это полезно, когда у вас есть много вещей, которым нужен доступ к одному и тому же глобальному состоянию. В этом случае BfsState специализируется на bfs и, скорее всего, никогда не будет использоваться где-либо еще (может быть хорошей идеей также переместить класс в bfs), а сам State всегда run, поэтому внешний мир его никогда не увидит. (Во многих случаях это нормально, но здесь область действия слишком мала, чтобы State могла быть полезной.) Было бы намного чище включить логику searchNode в само bfsComp.

В-третьих, я не понимаю, зачем вам нужны и nodesList, и discovered, когда вы можете просто вызвать _.toList на discovered после того, как вы выполнили свои вычисления. Однако я оставил его в своей повторной реализации на случай, если в этом коде есть что-то еще, что вы не отобразили.

def bfsComp(old: BfsState): BfsState = {
  if(old.q.isEmpty) old // You don't need isTerminated, I think
  else {
    val (currNode, newQ) = old.q.dequeue
    val newState = old.copy(q = newQ)
    adjList(curNode)
      .filterNot(s.discovered) // Set[T] <: T => Boolean and filterNot means you don't need to write !s.discovered(_)
      .foldLeft(newState) { case (BfsState(q, nodes, discovered, distance), adjNode) =>
        BfsState(
          q.enqueue(adjNode),
          adjNode :: nodes,
          discovered + adjNode,
          distance + (adjNode -> (distance(currNode) + 1)
        )
      }
  }
}

def bfs(src: Node): (List[Node], Map[Node, Int]) = {
  // I suggest moving BfsState and bfsComp into this method
  val output = bfsComp(BfsState(Queue(src), List(src), Set(src), Map(src -> 0)))
  (output.nodesList, output.distanceFromSrc)
  // Could get rid of nodesList and say output.discovered.toList
}

Если вы считаете, что у вас есть веская причина использовать здесь State, вот мои мысли. Вы используете def searchNode. Смысл State в том, что он чистый и неизменный, поэтому он должен быть val, иначе вы будете восстанавливать одно и то же State при каждом использовании.

Ты пишешь:

node <- State[BfsState, Node](s => {
  val (n, newQ) = s.q.dequeue
  (n, s.copy(q = newQ))
})

Во-первых, синтаксис Scala был разработан таким образом, что вам не нужно иметь () и {}, окружающие анонимную функцию:

node <- State[BfsState, Node] { s =>
  // ...
}

Во-вторых, мне это кажется не совсем правильным. Одним из преимуществ использования for-syntax является то, что анонимные функции скрыты от вас, а отступы минимальны. Я бы просто написал это

oldState <- get
(node, newQ) = oldState.q.dequeue
newState = oldState.copy(q = newQ)

Сноска: имеет ли смысл сделать Node внутренним классом Graph? Просто предложение.

person HTNW    schedule 17.08.2017
comment
Спасибо за подробный и блестящий ответ. Я рефакторинг кода соответственно. Только один вопрос 1.) Не могли бы вы немного подробнее рассказать, почему State Monad здесь не очень хорошая идея, и привести несколько примеров, когда вы считаете, что это хорошая идея? - person Aarsh Shah; 18.08.2017
comment
State здесь не очень полезен, потому что используется не очень часто. В этом случае существует только одно реальное значение State, и сложность, добавляемая использованием State, просто больше, чем польза, которую оно дает. Если бы вы делали что-то более сложное, State было бы полезнее, но здесь это не так. - person HTNW; 18.08.2017