CODEWITHSUNDEEP
scala
MCP
MCP

Reputation: 4546

Flatten arbitrarily nested List in Scala

  def flatten(l: List[_]): List[_] = {
    def iflatten(l: List[_], ret: List[_]): List[_] = l match {
      case Nil => ret
      case h :: Nil =>
        if( h.isInstanceOf[List[_]]) { iflatten(h, ret) }
        else {
          l.head :: ret
          iflatten(l.tail, ret)
        }
    }
  }

I know there are multiple ways to do this, and I'm not 100% sure my way is correct. I would like to test it but one issue I'm running into is in the second case statement where I call:

... { iflatten(h, ret) }

I am getting the compiler error:

error: type mismatch;
found   : Unit
required: List[?]

I'm trying to work through these type issues to learn more about the typesystem as it's different than what I've worked with in the past. Any suggestions as to why the compiler is complaining would be greatly appreciated.

Upvotes: 2

Views: 1397

Answers (5)

stefan.schwetschke
stefan.schwetschke

Reputation: 8932

Sorry, but this code is very complicated. I tried to simplify it and got to this solution:

    scala> :paste
    // Entering paste mode (ctrl-D to finish)

        def flatten(l : List[_]) : List[_] = l flatMap {
          case l1 : List[_] => flatten(l1)
          case otherwise => List(otherwise)
        }


    // Exiting paste mode, now interpreting.

    flatten: (l: List[_])List[_]

    scala> flatten(List(1,2,3))
    res3: List[Any] = List(1, 2, 3)

    scala> flatten(List(1,2,List(3,4)))
    res4: List[Any] = List(1, 2, 3, 4)

    scala> flatten(List(List(1,List(2),3),4,List(4,5)))
    res5: List[Any] = List(1, 2, 3, 4, 4, 5)

After fixing the code (adding the call to iflat), I did the following refactorings:

  1. Removed the inner method
  2. Used the built in flatMap for the iteration (and hence could eliminate or simplify some case expressions)
  3. Replaced the instanceOf with type guards

I think a simpler solution would be using the shapeless library (hint: look for the "boilerplate" part).

Upvotes: 1

Sebastien Lorber
Sebastien Lorber

Reputation: 92210

I think this is something the Shapeless library is good at.

https://github.com/milessabin/shapeless/blob/master/examples/src/main/scala/shapeless/examples/flatten.scala

Upvotes: 2

Shadowlands
Shadowlands

Reputation: 15074

Actually, I suspect the problem lies in the fact that you define the inner method iflatten, but never call it, so that the outer method flatten doesn't return anything (ie defaults to a return type of Unit, conflicting with the stated return type of List[_]).

Try adding the following as the last line of the outer flatten method:

iflatten(l, Nil)

Beyond that, you have various other problems with your code, such as not handling all match cases: you handle the case of a list with one element - h :: Nil - but not several elements. You probably meant something like h :: theRest, and then use theRest somewhere - probably as your ret parameter for the recursive call.

You also use the check h.isInstanceOf[List[_]] (generally any use of isInstanceOf is a bad code smell in scala) but then try passing h into iflatten recursively without casting it as List[_] (for example, as in @ChristopherMartin's answer, although using asInstanceOf is an even bigger code smell). @Marth's answer gives a good example of how to avoid these explicit type checks.

Upvotes: 3

Marth
Marth

Reputation: 24832

I'm not getting the same error you are concerning iflatten(h,ret). I am getting the found : Unit; required : List[?] error, but it refers to the fact that you are not calling iflatten in flatten itself : after defining it, you need to call the function at the end of flatten's definition.

def flatten(l: List[_]): List[_] = {
  def iflatten(l: List[_], ret: List[_]): List[_] = l match {
    case Nil => ret
    case (h:List[_]) :: tail => iflatten(tail,iflatten(h,ret))
    case h :: tail => iflatten(tail,h::ret)
  }
  iflatten(l,List()).reverse
}

As for the code itself, you can (and should) verify types when matching. Also note that the case h :: Nil only matches 1-length list.

As for the algorithm, you need to call iflatten within itself (that's where the arbitrarily nesting takes place).

Upvotes: 9

Chris Martin
Chris Martin

Reputation: 30756

I think you're just missing a cast.

if( h.isInstanceOf[List[_]]) { iflatten(h.asInstanceOf[List[_]], ret) }

Alternately: It would be prettier with pattern matching.

h match {
  case hList: List[_] => 
    iflatten(hList, ret)
  case _ => 
    l.head :: ret
    iflatten(l.tail, ret)
}

(caveat: This is just off the top of my head and I haven't put anything through a compiler)

edit - Marth's solution of merging that into the previous pattern match looks better than mine.

Upvotes: 3

Related Questions