2
\$\begingroup\$

I have been using Scala as a means to learn Functional Programming and writing better code. However, I have some questions regarding some exercises or if there's a better way to approach them.

In the exercises below, I have already defined the functions foldLeft, foldRight,append, sum, product, head and tail.


HARD - Write a function that concatenates a list of lists into a single list. Its runtime should be linear in the total length of all lists. Try to use functions we have already defined.

My solution:

//concatenates list of lists in a single list
def concatLists(x: List[List[Int]]):List[Int] = x.foldLeft( List[Int]() )( (x,y)=> x ++ y )

I have the feeling that the use of foldLeft and the concatenation operator is the right way to go and the runtime feels linear because we are appending one element at a time to the result of the fold, so the time is linear in the input size, am I right? Or is the ++ operator not efficient due to the List being implemented as a linked list? If not, how can I improve this?


EXERCISE 16: Write a function that transforms a list of integers by adding 1 to each element. (Reminder: this should be a pure function that returns a new List !)

//Adds one - exercise 16
def add1(x:List[Int]):List[Int]= for(elem <- x) yield elem+1

EXERCISE 18: Write a function map , that generalizes modifying each element in a list while maintaining the structure of the list. Here is its signature: def map[A,B](l: List[A])(f: A => B): List[B]

//implements map - exercise 18
def map[A,B](l: List[A])(f: A => B): List[B]=for(elem <- l) yield f(elem)

I've used yield before in some "toy exercises" in sites like hackerrank and similar and from my understanding, it is used in sequence comprehensions and adds a new element to the resulting sequence, much like in Python and the sequence assumes the return type declared in the function signature, is this correct?


What I want to know is if these implementations are correct in functional terms or if there are other/better ways of writing them.

\$\endgroup\$
1
\$\begingroup\$

General Comment

This looks like exercises from Functional Programming in Scala. It's some time since I read that, but I'm pretty sure you are expected each time to use the functions you have already written, better to learn their use, rather than reach for Scala's core library functions or build-in control structures like for loops.

List Concatenation

Are you using your own implementation or the library version? Either way, it looks as if you are doing this inefficiently because the first parameter in the library function passed to foldLeft is the accumulator, the second the list element. As I recall, the book version does the same.

When concatenating immutable lists, the list on the left is entirely recreated, while the list on the right is shared and not copied at all. foldLeft is the worst solution here because you start with the leftmost list and repeatedly add a new list on the right. So with the first two lists, you copy the one on the left. Then, when you add the third on the right, you completely copy your first two lists. And so on, until you reach the final list. This means that with n lists, the first list is copied n-1 times, the second n-2 times and so on. Very wasteful.

With a foldRight solution, where you start by appending the seed (empty list) on the right of the rightmost list and then in each subsequent operation append the accumulated value on the right and not the left, each list is only copied once.

By the time you reached this challenge, you should have written a stack-safe version of foldRight.

You could, alternatively, reverse the outer list and then foldLeft. Either way, remember that you want the accumulator to be on the right hand side of ++

add1

By using a for loop you have learned nothing about how to use the functions you have already written to build other functions.

You should, at this point, have written two stack-safe functions which make it possible to traverse a list: foldLeft and foldRight. Either can be used but remember that you need to preserve the original order.

map

Again, using a for loop you have learned nothing about how to use the functions you have already written. In fact, since Scala will actually rewrite the for loop using the core library map function, you've implemented map using map. Which works buy isn't in the spirit of the challenge.

map is just the general case of add1, so the same answer applies as in that challenge.

Summary

Your first solution didn't meet the requirements at all, since it scales exponentially and not linearly. The other two work functionally but don't meet the explicitly given (and often repeated) requirement to reuse functions you've written.

Forgive me for not providing you with any code examples but I don't want to rob you of the challenge to learn (which is the whole point of the book).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.