如何多次调用“flatMap”?-FP风格

Question

问题

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

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

我尝试了什么

• 一个简单的递归变量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))
}

问题：

• 为什么要像Alvaro建议的那样使用Scalaz和Kleisli？（不是指责，我想要争论；）
• 一个更优雅的解决方案可能吗

Answer 1

不知道它是否还有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，这是我尝试的前一个版本的残余。