[C++] ListArray's Flatten function should support recursive flattening of nested lists

[ZhangHuiGui]

Describe the enhancement requested

The function FlattenListArray seems only support flat the list array like list(int32),

arrow/cpp/src/arrow/array/array_nested.cc

Lines 240 to 254 in 6aa3321

	std::vector<std::shared_ptr<Array>> non_null_fragments;
	int64_t valid_begin = 0;
	while (valid_begin < list_array_length) {
	int64_t valid_end = valid_begin;
	while (valid_end < list_array_length &&
	(list_array.IsValid(valid_end) || list_array.value_length(valid_end) == 0)) {
	++valid_end;
	}
	if (valid_begin < valid_end) {
	non_null_fragments.push_back(
	SliceArrayWithOffsets(*value_array, list_array.value_offset(valid_begin),
	list_array.value_offset(valid_end)));
	}
	valid_begin = valid_end + 1; // skip null entry
	}

Users need to flatten nested list-arrays( list(list(int32)) ), and then the upper layer needs to implement recursive flatten, which seems inconvenient for them.

@felipecrv do you think we should implement this internally(and also for ListViewArray)?

Component(s)

C++

[felipecrv]

Users need to flatten nested list-arrays( list(list(int32)) ), and then the upper layer needs to implement recursive flatten, which seems inconvenient for them.

Right. But we can't change the behavior of existing Flatten to go recursive, but we can add a version that works recursively (and is not naively doing successive concatenations). And yes, it would treat all of (Large)?List(View)? as logical lists that need to be flattened until a non-list-like type is reached.

It would have to be a single implementation that dispatches based on the type->id() of the array because all combinations of list and list-view nesting should be supported.

[felipecrv]

And we shouldn't forget fixed_size_list either. It's logically a list as well.

[felipecrv]

Issue resolved by pull request 41092
#41092