F #: Написание функции, которая рекурсивно создает список кортежей, синтаксическая ошибка

Question

Я пытаюсь написать рекурсивную функцию, которая возвращает List , но у меня возникли некоторые проблемы с синтаксисом.

Функция должна возвращать пустой список по окончании рекурсиив противном случае кортеж (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

Может ли кто-нибудь объяснить мне, что я делаю неправильно?

РЕДАКТИРОВАТЬ:

Я постараюсь дать более подробную информацию.На самом деле моя функция немного сложнее.Я перебираю 2d массив и строю список кортежей с элементами индекса массива, которые удовлетворяют определенному условию.На самом деле это мой код:

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  -> []

Итак, вот еще 2 вопроса:):

1. Как изменить следующую строку, чтобы она компилировалась?

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

2. Есть ли лучший способ сделать это?

Меня не волнует порядок элементов списка.

Answer 1

Использование внутренней функции с аккумулятором, вероятно, самый простой способ сделать это (в качестве бонуса это хвостовая рекурсия).

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 2

Решение Дэниела выглядит хорошо для меня, но вам не нужно использовать изменяемое состояние (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 3

Так как foobar возвращает список, вы должны либо добавить списки, либо concat, а затем изменить

(foobar())@(10,10), однако я обычно делаю

наоборот

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

и затем поверните вспять, когда вы вернетесь.вышеупомянутые проблемы с хвостовой рекурсией, так что для настройки, чтобы вы получили что-то вроде:

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)]