5

Defining a concat function as below with foldRight can concat list correctly

def concat[T](xs: List[T], ys: List[T]): List[T] = (xs foldRight(ys))(_ :: _)

but doing so with foldLeft 

def concat1[T](xs: List[T], ys: List[T]): List[T] = (xs foldLeft(ys))(_ :: _)

results in an compilation error value :: is not a member of type parameter T, need help in understanding this difference.

EDIT :

Just in case someone might be looking for a detailed explanation on folds http://lampwww.epfl.ch/teaching/programmation_avancee/documents/programmation_avancee_5_en-2x2.pdf

daphshez
  • 9,272
  • 11
  • 47
  • 65
Somasundaram Sekar
  • 5,244
  • 6
  • 43
  • 85
  • Does this answer your question? [What 's the difference between foldRight and foldLeft in concat](https://stackoverflow.com/questions/40547305/what-s-the-difference-between-foldright-and-foldleft-in-concat) – alt-f4 May 13 '20 at 06:46

1 Answers1

13

Arguments order in foldLeft is not the same as in foldRight.

xs.foldRight(ys){(element, aggregator) => element :: aggregator}

xs.foldLeft(ys){(aggregator, element) => element :: aggregator}

With placeholder syntax for foldLeft - (_ :: _) - you are trying to do something like this: aggregator :: element. This means element.::(aggregator) and there is no :: method in element (type of element is T).

Community
  • 1
  • 1
senia
  • 37,745
  • 4
  • 88
  • 129
  • 1
    How do they differ conceptually and what are the scenarios that I can them respectively – Somasundaram Sekar Oct 22 '14 at 07:12
  • 3
    @SomasundaramSekar a look at the documentation would answer that. Also http://stackoverflow.com/questions/6253978/difference-between-fold-and-foldleft-or-foldright and http://stackoverflow.com/questions/1446419/how-do-you-know-when-to-use-fold-left-and-when-to-use-fold-right – The Archetypal Paul Oct 22 '14 at 07:17
  • 1
    @SomasundaramSekar `foldLeft` is more natural for List. `foldRight` requires reversing of the list first and it is slower. – ZhekaKozlov Oct 22 '14 at 07:24
  • 3
    @SomasundaramSekar: in addition to Paul's comment: note that `foldRight` on `List` is [implemented](https://github.com/scala/scala/blob/v2.11.3/src/library/scala/collection/immutable/List.scala#L397) as `reverse` + `foldLeft` since `reverse` is the best way to traverse `List` from lats to first element. – senia Oct 22 '14 at 07:24