F#：编写递归构建元组列表的函数，语法错误

Question

我正在尝试编写一个返回 List < 的递归函数。 int * int>，但我在语法上遇到了一些问题。

当递归结束时，该函数应该返回一个空列表，否则一个元组 (int * int) 与递归调用自身返回的列表合并：

let rec foobar () : List<int * int> =
    if (recursionIsEnded) then
        []
    else 
        foobar () :: (10, 10) // this is wrong
        // (10,10) works, but I need to concatenate it with the elements returned by foobar recursive call

有人可以向我解释我做错了什么吗？

编辑：

我会尝试提供更多细节。 实际上我的功能有点复杂。我正在迭代一个二维数组，并使用满足特定条件的数组索引元素构建一个元组列表。实际上这是我的代码：

let rec GetSameColorNeighs(grid : Option<Ball> [,], row : int , col : int, color : Microsoft.Xna.Framework.Color) : List<int * int> =
    if (row < 0 || col < 0 || row > MaxLineNumber - 1 || col > BallsPerLine - 1) then
        []
    else
        let ball = grid.[row,col]
        match ball with 
            |Some(ball) -> 

                if (!ball.visited = false || not <| ball.color.Equals(color)) then
                    [row , col]
                else
                     ball.visited := true
                     (row,col) ::GetSameColorNeighs(grid, row + 1, col + 1, color) ::  GetSameColorNeighs(grid, row - 1, col - 1, color) 

            |None  -> []

所以这里还有两个问题:):

1. 如何修改以下行以使其编译？

   (row,col) ::GetSameColorNeighs(grid, row + 1, col + 1, color) :: GetSameColorNeighs(grid, row - 1, col - 1, color) 
   

2. 有没有更好的方法可以做到这一点？

我不关心列表的元素顺序。

Answer 1

Daniel 的解决方案对我来说看起来不错，但您不需要使用可变状态 (ResizeArray)。相反，您可以将 loop 函数编写为序列表达式，使用 yield 生成结果，并使用 yield! 进行递归调用：

let GetSameColorNeighs (grid:Option<Ball>[,], row, col, color:Color) =
  let rec loop (row, col) = seq {
    if not (row < 0 || col < 0 || row > MaxLineNumber - 1 
                    || col > BallsPerLine - 1) then
        let ball = grid.[row,col]
        match ball with 
        | Some(ball) -> 
          if (!ball.visited = false || not <| ball.color.Equals(color)) then
            // Not sure what you want here - yield items using 'yield'?
            // [row , col] 
          else
            ball.visited := true
            yield row, col                 // Add single item to results
            yield! loop(row + 1, col + 1)  // Add all generated to results
            yield! loop(row - 1, col - 1)  //        -- || --
        | None  -> () }
  loop(row, col) |> Seq.toList

Answer 2

使用带有累加器的内部函数可能是最简单的方法（作为奖励，它是尾递归的）。

let foobar() =
  let rec foobar acc =
    if (recursionIsEnded) then
        List.rev acc
    else 
        foobar ((10, 10)::acc)
  foobar []

根据您的更新，我更喜欢可变的解决方案。像这样的东西

let GetSameColorNeighs(grid : Option<Ball> [,], row : int , col : int, color : Microsoft.Xna.Framework.Color) : List<int * int> =
    let results = ResizeArray()
    let rec loop (row, col) =
      if (row < 0 || col < 0 || row > MaxLineNumber - 1 || col > BallsPerLine - 1) then ()
      else
          let ball = grid.[row,col]
          match ball with 
              |Some(ball) -> 

                  if (!ball.visited = false || not <| ball.color.Equals(color)) then
                      [row , col] //doesn't compile, not sure what to do here
                  else
                       ball.visited := true
                       results.Add(row, col)
                       loop(row + 1, col + 1) 
                       loop(row - 1, col - 1)

              |None  -> ()
    loop(row, col)
    results |> Seq.toList

Answer 3

由于 foobar 返回一个列表，您必须附加列表或连接，然后反转

(foobar())@(10,10) 但是我通常会

以相反的方式执行此操作

   (10,10)::(foobar()))

，然后在以下情况下反转你回来了。上面的尾递归有一个问题，所以到了 tweek，你最终会得到类似的结果：

let foobar () : List<int * int> =
  let rec inner acc =
    if (recursionIsEnded) then
        list.Rev acc
    else 
        inner ((10, 10)::acc)
  inner []

与将列表附加到列表相比，最终反转通常会导致更少的操作

Answer 4

虽然它是一个更简单的函数，但我希望它有助于说明这一点，因为您通过两个列表递归来构建元组。此函数采用 ([],[]) 形式的两个列表作为输入，并将每个元素作为新列表中的元组配对在一起。

let rec pairlists twolists = 
  match twolists  with
    | ([],[]) -> []
    | (x::xs, y::ys) -> 
            (x,y)::pairlists(xs,ys)
;;

给定两个长度相同的列表（如果它们长度不同，您将收到错误），每次递归都会将前两个元素配对为一个元组（x，y）。语法：

(x,y)::pairlists(xs,ys)

实际上只是说“用我们当前的元素（x，y）构建一个元组，然后继续用我们的列表的其余部分（xs，ys）构建元组。

运行：

pairlists ([1;2;3], 1;2;3])

您将得到输出：

[(1,1);(2,2);(3;3)]