Scala flatten depth function confusion

Question

I am a bit confused with documentation about this function/with examples of use provided. Does flatten can happen only once? like

List(List(1, 2), List(3, List(4, 5, 6))) -> List(1, 2, 3, List(4, 5, 6))

Or you somehow specify the depth of flattening, so that it could become a List(1, 2, 3, 4, 5, 6) ?

Because, for example, in JS it seems that function can flat() whatever depth you want into a 1D array. Can Scala flatten do that or it's capable of only elevating once?

I am trying to recreate that function by myself and want to mimic the required behavior and understand the reason why it may work differently.

`List#flatten` will only flatten 1 level. You can probably try it by yourself ;) If you want to deeply flatten, you'll probably have to build a recursive method. — Gaël J, Jun 25 '21 at 14:38
Note that your `List(List(1, 2), List(3, List(4, 5, 6)))` is suspicious though as it's probably defined as a `List[Any]` which is a shame to do in Scala. — Gaël J, Jun 25 '21 at 14:40
@GaëlJ, not even a recursive method would work since the type of the function is impossible to define, you can try it. You can do something very nasty with class checks and unsafe access but is not really worth it, the moment you would need a dynamic-depth flatten it means you have a design problem elsewhere. — Luis Miguel Mejía Suárez, Jun 25 '21 at 14:47
Nested lists like this, where the nesting level may vary, are tree-shaped. They are fundamentally trees, not lists. Use an actual tree type instead of using `List`. — Seth Tisue, Jun 25 '21 at 15:47
@GaëlJ I heard a lot of things about trying to avoid type `Any` . I am trying to make my own version of linked lists, am I alright using `Any` for a value field of a list, or it's also bad and I should use a more elegant solution? Because it makes sense for me, you kinda should be able to put anything inside a list. — Jermog, Jun 26 '21 at 08:30
Related https://stackoverflow.com/questions/12160596/generic-type-safe-way-to-flatten-arbitrarily-nested-collections-in-scala — Mario Galic, Jun 26 '21 at 19:56
@Jermog yes you can put anything inside a **List** but you want to remember that the elements of a list of strings are strings not numbers or dogs nor anything else, so for that, we use **Generics** or parametric-polymorphism. — Luis Miguel Mejía Suárez, Jun 26 '21 at 21:52

Krzysztof Atłasik · Accepted Answer · 2021-06-26T19:01:27.053

As mentioned in the comments defining such a method in Scala 2 would not be straightforward to do in a typesafe manner. First of all, recursive types are not supported directly in Scala 2, so you'd have to operate on List[Any] and use runtime reflection to distinguish if the element is a list or an integer.

Recently released Scala 3 has many improvements in its type system, so I wondered that maybe it would be possible to implement such a method there? I tried and I think I was able to achieve usable implementation.

First of all, I wondered if it would be possible to implement recursive union type (a similar thing is possible in typescript):

type ListOr[A] = A | List[ListOr[A]]

unfortunately, such type was raising compiler error:

illegal cyclic type reference: alias ... of type ListOr refers back to the type itself

That was disappointing, but after some digging, I found that I could define such recursive type as:

type ListOr[A] = A match {
  case AnyVal => AnyVal | List[ListOr[AnyVal]]
  case _ => A | List[ListOr[A]] 
}

and it was usable:

val ints: ListOr[Int] = List(List(1), 2, 3, List(List(4, List(5)), 6), 7, 8, List(9))

val strings: ListOr[String] = List(List("A", "B", "C"), List(List("D", List("E")), "F"), "G", "H", List("I"), "J")

so now I needed to just implement the flattening function:

//I needed class tag for A to be able to do a match
def deepFlatten[A: ClassTag](s: ListOr[A]): List[A] =
  s match 
    case a: A => List(a)
    case ls: List[_ <: ListOr[A]] => ls.flatMap(deepFlatten(_))

and it seemed to be working correctly:

@main
def main = 
  val i: List[Int] = deepFlatten[Int](ints) //List(1, 2, 3, 4, 5, 6, 7, 8, 9)
  val j: List[String] = deepFlatten[String](strings)//List(A, B, C, D, E, F, G, H, I, J)

Obviously, such implementation could be improved (it's not tail-recursive), but it's doing its job.

Since I'm Scala 3 novice I'm not sure if that's the best implementation, but it's definitely possible to implement such arbitrarily deep flattening functions as type-safe.

Scastie with the solution.

Scala should work on this `illegal cyclic type reference: alias` — John, Jun 26 '21 at 17:12
@John it can not be worked, a type alias is just that an alias, it can not be recursive because it would be infinite. You can just create a normal class instead that can be recursive. — Luis Miguel Mejía Suárez, Jun 26 '21 at 18:21
It's working in typescript. It's still infinite recursion there, but It think it's handled lazily there so it's not causing the cyclic reference error. — Krzysztof Atłasik, Jun 26 '21 at 18:59

score 2 · Answer 2 · answered Jun 26 '21 at 16:15

This is an attempt of doing something similar using a simple Tree data structure.

final case class Tree[+A](value: A, children: List[Tree[A]] = Nil)

def flattenTree[A](tree: Tree[A]): List[A] = {
  @annotation.tailrec
  def loop(remainingNodes: List[Tree[A]], acc: List[A]): List[A] =
    remainingNodes match {
      case Tree(value, children) :: tail =>
        loop(
          remainingNodes = children reverse_::: tail,
          value :: acc
        )
      
      case Nil =>
        acc
    }
  
  loop(remainingNodes = tree :: Nil, acc = List.empty)
}

Which can be used like this:

val tree = Tree(
  value = 1,
  children = List(
    Tree(value = 2),
    Tree(
      value = 3,
      children = List(
        Tree(value = 4),
        Tree(value = 5),
        Tree(value = 6)
      )
    )
  )
)

val flattenedTree = flattenTree(tree)
println(flattenedTree.mkString("[", ", ", "]"))

Which will produce the following output:

[2, 4, 5, 6, 3, 1]

As you can see is a reversed DFS (whose results are also reversed). If the order doesn't matter this is a straightforward and efficient implementation, if order matters then one can play with the code.

Another approach would be to use a data structure like:

sealed trait ListOr[+A] extends Product with Serializable
final case class NestedList[+A](data: List[ListOr[A]]) extends ListOr[A]
final case class SingleValue[+A](value: A) extends ListOr[A]

You can see the code running here.

Scala flatten depth function confusion

2 Answers2