F #: Writing a function that recursively builds a list of tuples, syntax error

Question

I am trying to write a recursive function that returns List <int * int>, but I am having some problems with the syntax.

The function should return an empty list at the end of the recursion, otherwise the tuple (int * int) merges with the list returned by the recursive call to itself:

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 

Can someone explain to me what I'm doing wrong?

EDIT:

I will try to give more detailed information. Actually my function is a bit more complicated. I iterate through a 2d array and build a list of tuples with array index elements that satisfy a certain condition. Actually my code is:

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

So, 2 more questions :):

• How to change the following line to compile it?

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

• Is there a better way to do this?

I don't need the order of the list items.

Answer 1

Using an internal function with a battery is probably the easiest way to do this (as a bonus, it is recursive).

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

Based on your update, I would rather use a mutable solution. Sort of

 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

Daniel's solution looks good to me, but you don't need to use a resizable state ( ResizeArray ). Instead, you can write the loop function as a sequence expression that generates results with yield and makes recursive calls with 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

Since foobar returns a list, you need to either add lists or concat and then cancel

(foobar())@(10,10) however I usually did

it's the other way around

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

and then back when you come back. have the aforementioned problem with tail recursion to tweek what you end up with something like:

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

reverse at the end should usually result in fewer operations than adding a list to a list

Answer 4

Although this is a simpler function, I hope this helps to illustrate the essence of your recursion through two lists in order to build tuples. This function takes two lists as input in the form ([], []) and concatenates each element together as a tuple in a new list.

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

Given two lists of the same length (if they do not have the same length, you get an error), each recursion will associate the first two elements with a tuple as (x, y). Syntax:

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

Actually, he simply said: "Build a tuple with our current elements (x, y), and then continue to build tuples with the rest of our lists (xs, ys).

Run:

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

And you will get the result:

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