F# 如何搜索和计算某个点出现的次数？

Question

我制作了一个数据结构来表示一个房子迷宫。它的工作方式是，一条路径可以通向有蛋糕、冰淇淋或 toastr 的死胡同，也可以通向左、右、双(左右路径)或三重(左、中、右路径)。

这是房子的类型和布局

type path =
|End of string
|Double of path * path
|Triple of path * path * path
|Left of path
|Right of path

let GingerbreadHouse = Triple(
                        Double( Double(End("*"), End("X")), Left(Right(End("X"))) ),     
                        Left( Double(End("*") , Left( Double(End("X") , Right(End("O"))))))  ,    
                        Left( Triple(Right(End("X")) , Double( Double(End("*") , End("X")) , End("X")) , Double(End("X") , Right(End("*"))) )) 
                        )

现在我要做的是计算在到达 toastr 之前达到的蛋糕数量，同时首先遵循最右边的路径。

我首先尝试使用一个简单的辅助函数来执行此操作，该函数会跟踪计数，当它到达 toastr 时，它会重新计算。但是我碰壁了，因为我无法以这种方式完全返回死角。

let YummyKids house =
let rec helper house count =
    match t with
    |Left(p) -> helper p count
    |Right(p) -> helper p
    |Double(lp,rp) -> helper count + helper count
    |Triple(lp, fp, rp) -> helper rp count + helper mp count + helper lp count
    |End(treat) when treat = "*" -> helper ??? count
    |End(treat) when treat = "X" -> helper ??? (count+1)
    |End(treat) when treat = "O" -> count     
helper house 0 

所以我的第二次尝试我认为我会坚持使用正常的向后递归方法但是我碰壁了因为我不知道如何在它到达 toastr 时真正结束整个事情。

let YummyKids house =
match t with
|Left(p) -> YummyKids p
|Right(p) -> YummyKids p
|Double(lp,rp) -> YummyKids rp + YummyKids lp
|Triple(lp, fp, rp) -> YummyKids rp + YummyKids mp + YummyKids lp
|End(treat) when treat = "*" -> 0
|End(treat) when treat = "X" -> 1
|End(treat) when treat = "O" -> //???

如果要计算整个迷宫中蛋糕的数量，这会起作用，但我只想计算到某个点，以便它到达 toastr 时。我该怎么做？

Answer 1

你的递归函数的结果需要表明你到目前为止找到了多少蛋糕，以及这个过程是否已经到达 toastr 并因此应该终止。

然后你可以实现分支，如果还没有找到 toastr (添加蛋糕的数量)，它会继续到其他分支，但是当在一个分支中找到 toastr 时立即返回 - 在查看另一个分支之前分支机构。

在下面，返回类型是int * bool，其中int代表蛋糕的数量，bool是true 当我们打开 toastr 时。有趣的案例是 Double 的处理:

let rec YummyKids path =
  match path with
  | Left(p) -> YummyKids p
  | Right(p) -> YummyKids p
  | Double(lp,rp) -> 
      let cakes, finished = YummyKids rp
      if finished then cakes, finished else
        let moreCakes, finished = YummyKids lp
        cakes + moreCakes, finished
  | End(treat) when treat = "*" -> 0, false
  | End(treat) when treat = "X" -> 1, false
  | End(treat) when treat = "O" -> 0, true

在 Double 中，我们首先查看正确的分支，如果找到 toastr ，我们返回到目前为止蛋糕的数量。如果 finished = false，我们查看正确的分支并添加蛋糕。

我没有实现 Triple 情况，但是您应该能够按照与 Double 情况相同的模式相当轻松地完成它。