CODEWITHSUNDEEP
listscalarecursionfunctional-programming
Moebius
Moebius

Reputation: 6508

Discussing implementation of list flattener function in scala

The flatten function is a function which take a list of list and return a list which is the concatenation of all the lists. As an exercise for functional programming in scala, we have to implement that function with a linear complexity. My solution is :

def flatten[A](l: List[List[A]]): List[A] = {
    def outer(ll: List[List[A]]):List[A]  = {
        ll match {
            case Nil => Nil
            case Cons(h,t) => inner(t, h)
        }
    }
    def inner(atEnd: List[List[A]], ll: List[A]): List[A] = {
        ll match {
            case Nil => outer(atEnd)
            case Cons(h,t) => Cons(h, inner(atEnd, t))
        }
    }
    outer(l)
}

It works. Now I looked at the solution proposed :

def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match {
        case Nil => a2
        case Cons(h,t) => Cons(h, append(t, a2))
    }

def flatten2[A](l: List[List[A]]): List[A] =
    foldRight(l, Nil:List[A])(append)

I am suspicious that flatten2 is really linear. At each iteration of foldLeft, the function append is called. This function will parse all the nodes of the accumulator. The first time, the accumulator is Nil, the second it is l.get(1) then l.get(1) + l.get(2)... So the first list in l won't be crossed only once, but l.length - 1 until the end of the function. Am I right ?

While my implementation really cross each list only once. Is my implementation really faster ?

Upvotes: 0

Views: 106

Answers (1)

FPstudent
FPstudent

Reputation: 841

Consider for example flatten2 (List(List(1,2,3), List(4,5), List(6))), which expands to:

append(List(1,2,3),
       append(List(4,5),
              append(List(6),
                     Nil)))

As a comment in the link says, "append takes time proportional to its first argument" and therefore "this function is linear in the total length of all lists". (On the other hand, neither flatten2 nor flatten is tail-recursive, though.)

Upvotes: 2

Related Questions