Functional Programming In Scala - reversing lists exercise

0
votes

While working trough the exercises and concepts of the book: Functional Programming in Scala by Paul Chiusano and Rúnar Bjarnason, I stumbled upon the exercise of writing my own function to reverse a list.

The "suggestion" the authors gave to motivate readers to learn more, was to see if we can write such a function using a fold.

My "non-fold" version is the following:

def myrev(arr:List[Int]):List[Int] = if (arr.length > 0) { myrev(arr.tail) :+ arr.head } else arr

However, can someone give me some pointers on how to at least start the logic to reverse a list via a fold?

I know that:

List(1,2,3,4).foldLeft(0)({case(x,y)=>x})

gives me the initial "seed" value, which is 0 above, and that:

List(1,2,3,4).foldLeft(0)({case(x,y)=>y})

gives me 4 which is the last element of the list.

So I would need to supply as function to foldLeft a sort of "identity" function that can give me an element in a certain position and maybe use it to reverse the list somehow, but I feel at a loss.

I didn't fully understood some Haskell code I found online and I want to "struggle" and try to get there on my own only with some pointers, instead of simply blindly copy some solution, so any help would be greatly appreciated.

2
scalalinked-listfunctional-programming
Well... one thing you should do is to stop thinking of Scala List as Arrays. They are quite different. Scala Lists are actually linked-list with a pointer to the head of list. So... append on List of length n is O(n). Do not do appends on a list. - sarveshseri
Thanks for the tip. I am not seeking for efficiency here, I am seeking to learn FP and thinking mostly on an abstract level that uses recursion, functions, HOFs, etc... How could I re-write that code above without an append? - Bruno Oliveira
list.foldLeft(List[Int]())((acc, item) => item :: acc) - sarveshseri
The first parenthesis are supposed to be provided with initial value of something that you will use to accumulate through your fold. In this case it will be an empty list of Int. Now you second argument is a function which takes the accumulator and an item from list and returns the accumulated result. - sarveshseri
Thanks I understood everything perfectly. I had never thought of using an empty list as initial value for fold, but the function itself to return the accumulated result sounds perfectly logical. Thanks a lot!! - Bruno Oliveira

2 Answers

3
votes
scala> List(1, 2, 3, 4).foldLeft(List.empty[Int])((result, currentElem) => currentElem :: result)
res2: List[Int] = List(4, 3, 2, 1)
0
votes

An implementation of a function that takes a list and inverse it using foldLeft

def reverse (l: List[String]) = 
    l.foldLeft(List[String]())( (x: List[String], y: String) => y :: x )

Create a list and call the reverse function

val l = List("1", "2", "3")
reverse(l)

Result

res2: List(3, 2, 1): List[String]