在golang中扁平化递归数据结构的有效方法

Question

I have a recursive data structure that can contain a few different type of data:

type Data interface{
 // Some methods
}
type Pair struct { // implements Data
  fst Data
  snd Data
}
type Number float64 // implements Data

Now I want to flatten a chain of Pairs into a []Data. However, the Data in the fst field should not be flattened, only data in snd should be flattened. E.g:

chain := Pair{Number(1.0), Pair{Number(2.0), Pair{Number(3.0), nil}}}
chain2 := Pair{Pair{Number(1.0), Number(4.0)}, Pair{Number(2.0), Pair{Number(3.0), nil}}}

becomes:

data := []Data{Number(1.0), Number(2.0), Number(3.0)}
data2 := []Data{Pair{Number(1.0), Number(4.0)}, Number(2.0), Number(3.0)}

My naive approach would be:

var data []Data
chain := Pair{Number(1.0), Pair{Number(2.0), Pair{Number(3.0), nil}}}

for chain != nil {
    data = append(data, chain.fst)
    chain = chain.snd
}

Is there a more efficient approach that can flatten a data structure like the one in the variable chain into an []Data array?

Answer 1

You can use a recursive function. On the way down, add up the number of pairs, at the bottom, allocate the array, and on the way back up, fill the array from back to front.

If you need to support arbitrary trees, you can add a size method to Data, and then do another tree traversal to actually fill the array.