2

问题

在玩玩具示例时 -位置，骑士可以在移动后到达棋盘n，从某个位置开始x- 我想知道是否存在更清洁的解决方案（在简洁和函数式编程的意义上）

  • 执行flatMap（暂时忽略filter）一定次数（每次移动一次）
  • 拥有（甚至）更多的 FP-ish 编码方式

我试过的

  • 一个简单的递归变体move(...)
  • 使用函数组合的变体move2(...)

代码

object ChessFun {

  import scala.annotation.tailrec

  case class Position(x: Int, y: Int)

  case class Chessboard(widthX: Int, widthY: Int) {
    def positionOnBoard(pos: Position) = {
      (0 <= pos.x) && (pos.x < widthX) && (0 <= pos.y) && (pos.y < widthY)
    }
  }

  def knightMoves(pos: Position) = Set(
    Position(pos.x + 1, pos.y + 2),
    Position(pos.x + 2, pos.y + 1),
    Position(pos.x + 1, pos.y - 2),
    Position(pos.x + 2, pos.y - 1),
    Position(pos.x - 1, pos.y + 2),
    Position(pos.x - 2, pos.y + 1),
    Position(pos.x - 1, pos.y - 2),
    Position(pos.x - 2, pos.y - 1)
  )

  def move(startPos: Position, steps: Int, chessboard: Chessboard) : Set[Position] = {
    @tailrec
    def moveRec(accum: Set[Position], remainingSteps: Int) : Set[Position] = {
      remainingSteps match {
        case 0 ⇒ accum
        // otherwise  
        case _ ⇒ {
          // take a position and calculate next possible positions
          val a: Set[Position] = accum
            .flatMap( pos ⇒ knightMoves(pos)
            .filter( newPos ⇒ chessboard.positionOnBoard(newPos)) )
          moveRec(a, remainingSteps - 1)
        }
      }
    }

    moveRec(Set(startPos), steps)
  }

  def move2(startPos: Position, steps: Int, chessboard: Chessboard) : Set[Position] = {
    val nextFnc : Set[Position] => Set[Position] = {
      positions => positions
        .flatMap( pos ⇒ knightMoves(pos)
        .filter( newPos ⇒ chessboard.positionOnBoard(newPos)) )
    }

    // nexts composes nextFnc `steps` times
    val nexts = (0 until steps).map( i ⇒ nextFnc).reduce( _ compose _)

    // apply nexts
    nexts(Set(startPos))
  }  

  def main(args: Array[String]): Unit = {
    val startPos = Position(0,0)
    println( move( Position(0,0), 2, Chessboard(8, 8)) )
    println( move2( Position(0,0), 2, Chessboard(8, 8)) )
  }
}

编辑 - 2015-11-29 - 02:25AM

从 Alvaro Carrasco 给出的答案中得到一些启发，我move2优雅地将方法重写为：

def move2b(startPos: Position, steps: Int, chessboard: Chessboard) : Set[Position] = {
  val nextFnc : Set[Position] => Set[Position] = {
    _.flatMap( knightMoves(_).filter( chessboard.positionOnBoard(_)) )
  }

  List.fill(steps)(nextFnc).reduce(_ compose _)(Set(startPos))
}

问题：

  • 为什么要Kleisli按照 Alvaro 的建议使用 Scalaz？（不是责备，我想要争论；））
  • 是否有可能更优雅的解决方案？
4

1 回答 1

3

不知道是不是 FP，但这里有一个使用 scalaz 的版本>=>。

import scalaz.Kleisli
import scalaz.syntax.kleisli._
import scalaz.std.list._

def move3 (startPos: Position, steps: Int, chessboard: Chessboard) : Set[Position] = {
  val validMove = Kleisli {a: Position => knightMoves(a).filter(chessboard.positionOnBoard).toList}
  List.fill(steps)(validMove).reduce(_ >=> _)(startPos).toSet
}

必须使用 List，因为 Set 没有 Bind 实例。

更新：删除step-1了我正在尝试的先前版本的残余。

于 2015-11-27T17:07:29.287 回答