Не понимаю, что эффективность отличается в foldLeft и foldRight в Scala

Question

Прочтите следующий параграф в Программе в Scala, 2nd Edition, который для меня не имеет смысла.

def flattenLeft[T](xss: List[List[T]]) = 
    (List[T]() /: xss) (_ ::: _) 

def flattenRight[T](xss: List[List[T]]) = 
    (xss :\ List[T]()) (_ ::: _) 

Поскольку список конкатенация xs ::: ys, занимает время, пропорциональное его первого аргумента хза, реализация с точкой зрения кратного права в flattenRight является более эффективной, чем кратное левой реализации в flattenLeft. Проблема заключается в том, что flattenLeft (XSS) копирует первый элемент списка xss.head п - 1 раз, где п есть длина списка XSS

Таким образом, если список конкатенации занимает время, пропорциональное его первый Аргумент, не так ли? flattenLeft тем более эффективным, так как его первый аргумент - пустой список и первый аргумент flattenRight - это список неизвестной длины?

Answer 1

Первый аргумент foldLeft - это просто пустой List в начале, то есть zero для этой складкой.

Как сбросить все List сек на одну List, то fold строит промежуточные списки с частичным результатом на каждой конкатенации, которая затем используется в качестве аргумента к следующему конкатенации. Этот промежуточный результат продолжает становиться все больше и больше. На foldLeft, это будет первый аргумент:

def flattenLeft[T](xss: List[List[T]]) = 
    (List[T]() /: xss) ((acc, xs) => acc ::: xs) 
         //^ this one 

Напротив, для foldRight вы строите результат справа, что означает промежуточный результат (тот, который растет) является правильным, что будет второй аргумент операции конкатенации

def flattenRight[T](xss: List[List[T]]) = 
    (xss :\ List[T]()) ((xs, acc) => xs ::: acc) 
          //^ this one gets bigger now 

Итак, flattenRight займет меньше времени, так как первый аргумент конкатенации не растет по мере продвижения.

Answer 2

сплющивания списков путем складывания с левой стороны протекает, как

[ [....] [....] [....] [....] [....] ] 
    [....] 
    [...........] 
    [..................] 
    [.........................] 
    [................................] 

и справа, как

[ [....] [....] [....] [....] [....] ] 
           [....] 
         [...........] 
       [..................] 
     [.........................] 
    [................................] 

При складывании п списков с левой стороны, каждый элемент в первом списке прослеживается более (n-1) раз; во втором списке (n-2) раз и т. д. Это классическое квадратичное поведение.

При складывании справа каждый элемент прослеживается ровно один раз, для линейного поведения всей операции.