Решение соответствует функциональному стилю программирования?

Question

[jdev]

Всем доброго времени суток.

Пытаюсь познать дзен ФП и в качестве упражнения написал на scala программу поиска пути обхода конём шахматной доски. Гуру ФП, скажите, соответствует ли данное решение функциональному подходу?

def possibleSteps(pos: (Int, Int)) =
  for (x <- -2 to 2; y <- -2 to 2; if x != 0 && y != 0 && scala.math.abs(x) != scala.math.abs(y))
  yield (pos._1 + x, pos._2 + y)

def canStep(path: List[(Int, Int)], pos: (Int, Int)) =
  if (path.length == 0) true
  else possibleSteps(path.head).contains(pos)

def nextSteps(available: scala.List[(Int, Int)], path: scala.List[(Int, Int)]): List[(Int, Int)] =
  for (pos <- available; if canStep(path, pos)) yield pos

def getPath(path: List[(Int, Int)], available: List[(Int, Int)]): List[(Int, Int)] =
  if (available.size == 0)
    path
  else
    nextSteps(available, path).foldLeft(List[(Int, Int)]()) (
      (found, e) => found match {
          case Nil => getPath(e :: path, available filter { _ != e })
          case lst: List[(Int, Int)] => lst
        }
    )

def generatePositions(side: Int) = for (x <- Range(0, side); y <- Range(0, side)) yield (x, y)

println(getPath(List(), generatePositions(5).toList))

В особенности я сомневаюсь в следующих пунктах:
1) Реализация possibleSteps
2) Применим ли в данном случае foldLeft? Какие есть альтернативы (я больше ничего не смог придумать, чтобы исключить поиск всех возможных путей)?
3) Общий стиль написания (форматирование) — я понимаю, что это сильно зависит от языка и субъективных предпочтений, но может быть есть какие-то общепринятые паттерны?

Comments

[jdev]

Не много переформулирую вопрос: не витает ли в этом коде запашок импиративщины?

Answer 1

[Артур]

Дзен ФП — использовать функции и значения. Так что тут что-угодно в эту категорию попадает.

Comments

[jdev]

Переформулировал вопрос

[Артур]

От императивщины не избавиться полностью, достаточно изолировать её в определенных местах. Соответственно, больше чистых функций и меньше с побочным эффектом.

Answer 2

[shock_one]

Присваиваний нет? Нету. Var’ов тоже. Значит, функциональненько. Должен сказать, в вашем алгоритме черт ногу сломит — я так до конца и не разобрался как он работает, но что мог переделал. Стало еще более запутанно, но короче.

def canStep(path: List[(Int, Int)], pos: (Int, Int)) =
  if (path.length == 0) true
  else List((pos._1 - path.head._1).abs, (pos._2 - path.head._2).abs).filter(_ < 3).sum == 3

def getPath(path: List[(Int, Int)], available: List[(Int, Int)]): List[(Int, Int)] =
  if (available.size == 0)
    path
  else
    available.filter(canStep(path, _)).foldLeft(List[(Int, Int)]()) {
      (found, e) => found match {
        case Nil => getPath(e :: path, available.filter(_ != e))
        case lst: List[(Int, Int)] => lst
      }
    }

def generatePositions(side: Int) = for (x <- 0 until side; y <- 0 until side) yield (x, y)

println(getPath(List(), generatePositions(5).toList))