CODEWITHSUNDEEP
listsyntaxrecursionf#tuples
Heisenbug
Heisenbug

Reputation: 39164

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

I'm trying to write a recursive function that return a List < int * int>, but I'm having some trouble with the syntax.

The function should return an empty list when the recursione ends, otherwise a tuple (int * int) merged with a List returned by a 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

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

EDIT:

I'll try to give more details . Actually my function is a bit more complicated. I'm iterating through a 2d array and build a list of tuples with the array index elements that satisfy a certain condition. Actually that's my code:

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 here's 2 more question :):

  1. How modify the following row in order to make it compile?

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

  2. Is there any better way to do that?

I don't care about the list's elements order.

Upvotes: 3

Views: 4066

Answers (4)

Alex Mapley
Alex Mapley

Reputation: 922

Although it's a simpler function, I hope it helps illustrate the point as your recurse through two lists to build tuples. This function takes two lists as input in the form ([],[]), and pairs 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 aren't the same length you'll get an error), each recursion will pair the first two elements into a tuple as (x,y). The syntax:

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

Is really just saying "Build a tuple with our current elements (x,y), then proceed building tuples with the rest of our lists (xs,ys).

Run:

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

And you'll get the output:

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

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243041

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

Upvotes: 3

Daniel
Daniel

Reputation: 47904

Using an inner function with an accumulator is probably the easiest way to do it (as a bonus it's tail recursive).

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

Based on your update, I'd prefer a mutable solution. Something like

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

Upvotes: 2

Rune FS
Rune FS

Reputation: 21742

Since foobar returns a list you either have to append the lists or concat and then reverse

(foobar())@(10,10) however I'd usually do

it the other way around

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

and then reverse when you return. the above have a problem with tail recursion so to tweek that 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 []

reversing in the end should usually result in fewer operations than if you append a list to a list

Upvotes: 1

Related Questions