Scala - Coursera Course Discussion Thread

[Joe San]

Guys,

For all those who are doing the Scala course from Coursera, I'm creating this thread to share and discuss ideas on the course and Scala.

To start with: On the example assignment, to Sum the items in a List. The Scala doc in the example says that we should use recursion, but heck I just called sum on the List and returned it. I see no way to recursively call sum other than defining an inner method to keep track of the sum as a separate variable as the first argument to the inner function and tail as the second argument to the inner function. But the call to the sum method on the List still was accepted!

How did you guys go about doing this?

[Matthew Brown]

For a recursive solution for sum, all you need to realise is that the sum of the list is the first element plus the sum of the rest of the list. You only need to declare an inner function if you want to make sure the recursive call is tail recursive (in which case you can do it the way you describe).

Using the built in sum method is definitely cheating .

[Marco Ehrentreich]

But the call to the sum method on the List still was accepted!

Maybe it was just accepted because the sum() function was in the example assignment? But it was surely not one of the expected solutions

Anyway, the recursive algorithm is quite simple as Matthew already described!

Marco

[Joe San]

Marco Ehrentreich wrote:

But the call to the sum method on the List still was accepted!

Maybe it was just accepted because the sum() function was in the example assignment? But it was surely not one of the expected solutions

Anyway, the recursive algorithm is quite simple as Matthew already described!

Marco

Yes, I know that I can achieve that with an inner function, but my question was to do it without using an inner function by just fiddling around with the head and tail. If I was not able to solve this simple addition, I would not have been able to get the Week 1 assignment done.

But I've seen many people in the discussion forum (in Coursera) saying that they implemented sum just by using a call to the sum function in the List type.

[Marco Ehrentreich]

What about something like this?

def sum(xs: List[Int]): Int =
    if (xs.isEmpty) 0 else xs.head + sum(xs.tail)

As Matthew pointed out the function cannot be optimized by the compiler because it's not tail-recursive but it's very simple and it does the job. I think it can't get any simpler than this.

But I must admit that I personally had problems, too, with the official assigment for week 1. The solutions are very compact and simple if you're done but it can really take a lot of time to think about it if you're not used to this recursive programming style. On the other hand recursive functions can provide elegant solutions for some classes of problems once you're familiar with the basic recursion patterns.

Marco

[Jeanne Boyarsky]

I did what Marco did. of course you could call sum, but the point was to practice recursion.

I also spent some time learning more about sbt. It's interesting how it is layer on maven, but works a little differently.

[chris webster]

For the example assignment I just used the sum and max functions on the List, as my impression was that the main purpose was to try out the whole download/modify/upload mechanism for the exercises anyway.

When I was playing around with recursion for the Week 1 assignment (thank you, SICP chapter 1!) I did implement recursive "sum" and "factorial" functions of my own, although they don't use a List. I'm quite happy to lift ideas from sources like the SICP book (after all, the course team recommended it in the first place), especially as the course lectures didn't really go into much depth on recursion, but it's still important to play around with this stuff yourself to get a better understanding of it. And it gives me a chance to try and understand Scheme as well.

Looking forward to Tuesday and the next batch of brain-teasers!

[Matthew Brown]

I've a question about style in the "functional community" (I might ask the same question on the course forum).

I know about the advantage of making a recursive function tail recursive. In some cases the simplest approach isn't tail recursive but it's easy to make it so (e.g. the sum() function from the example assignment). Then you've got cases like the coin counting: it wouldn't be too hard to make it tail recursive on one branch but not both. But someone on the course forum says they've managed to create a (much more complicated) fully tail-recursive version.

The question is this: is it considered good style to always try and make functions tail recursive even at the cost of simplicity? Or is that considered premature optimisation? All my instincts tell me the latter, but I wondered what functional practitioners tend to prefer.

[Marco Ehrentreich]

I think it's always a good idea to strive for a tail-recursive solution if possible. This should in general avoid the risk of stack overflows and maybe reduce memory consumption and/or increase the performance.

Depending on the algorithm and use case I personally would not sacrifice readability and simplicity of the code if it's not really needed.

Unfortunately I'm not an expert in functional programming and recursive algorithms, so I'm not sure if there are ways to systematically transform any recursive solution into a clean and readable tail-recursive solution. I hope to learn more about this during the course ;-)

Marco

[Matthew Brown]

Good, Martin addressed this in the first of this week's lectures. Don't make it tail recursive at the expense of readability unless you know it's important in this case (quoting Donald Knuth). That's what I expected/hoped, I just wondered if the FP crowd saw things differently.

[Joe San]

Anone already working on the Week 2 assignments? I got the first question done. Kind of lost with the second assignment.

[chris webster]

Joe Harry wrote:Anone already working on the Week 2 assignments? I got the first question done. Kind of lost with the second assignment.

Just started today - currently looking at the filter() function. And I haven't figured out the test suite yet (so much for TDD...).

I'm scratching my head a bit with this stuff, as it's a long time since I looked at any maths - and it's only week 2! But I get the impression we can build up the required functionality for part 2 using the "atomic" functions we built in part 1, working with a defined set of integers between -1000 and +1000.

[Matthew Brown]

My background in maths helps a lot here. I found this set straightforward. Forcing myself to write a full set of tests was the only thing that made my first attempt take longer than 5 minutes...though I then did a bit of polishing.

[Joe San]

chris webster wrote:

Joe Harry wrote:Anone already working on the Week 2 assignments? I got the first question done. Kind of lost with the second assignment.

Just started today - currently looking at the filter() function. And I haven't figured out the test suite yet (so much for TDD...).

I'm scratching my head a bit with this stuff, as it's a long time since I looked at any maths - and it's only week 2! But I get the impression we can build up the required functionality for part 2 using the "atomic" functions we built in part 1, working with a defined set of integers between -1000 and +1000.

I can give you a hint! The filter that I have looks more or less like the intersect!

[chris webster]

Joe Harry wrote:I can give you a hint! The filter that I have looks more or less like the intersect!

Thanks - the "set-processing" neurons in my brain have woken up now, so I've finished the atomic functions (including tests) for part 1.

Now I'm trying to figure out what they want us to do with part 2.

[Joe San]

Matthew Brown wrote:My background in maths helps a lot here. I found this set straightforward. Forcing myself to write a full set of tests was the only thing that made my first attempt take longer than 5 minutes...though I then did a bit of polishing.

Can you help me with the Assignment number 2. My understanding is that, we have a set of integers (say anything between 0 and 1000). These Set of integers must pass the condition laid out by the predicate p?

def forall(s: Set, p: Int => Boolean): Boolean = {
}

Supposing, I have my p as defined below:

def j = (x: Int) => x+x == 2*x

And my Set which now conatins 1 and 2 as below:

val uSet = union(sSet(1), sSet(2))

Now the call to forall:

 println(forall(uSet, j))

From the above illustration, I would say that all the elements in the Set uSet (1,2) should pass the condition laid out by the predicate p which is x+x == 2*x. Is my understanding correct?

With this being the case, why have the bounds variable? My Set is anyways consisting of {1,2}. Help me understand this!

[Matthew Brown]

Your set contains {1, 2}. But how do you know that?

In order to tell whether forall() should return true, you have to test every member of the set against the predicate. The problem is, by representing a set in the way we are in this assignment, you have no way of listing all the members. Once you've got uSet in your example, you can check that 1 and 2 are members. But how do you know it contains only two elements (without looking at the definition)?

Because the set can't tell you what its contents are, the only way to evaluate forall() is to check every possible element. When you've got an infinite number of integers, that could take some time....hence the limit.

[Joe San]

Ok. With that idea, I came up with the following implementation:

  def forall(s: Set, p: Int => Boolean): Boolean = {
    def iter(a: Int): Boolean = { println(p(a)) 
      if (check if the bounds are within limits if not then fals3e) 
      else if (a does not satisfy p then return false) 
      else iter(increment a and continue)
    }
    iter(0)
  }

But when I iterate using the bounds in the forall method which is -1000 to +1000, how could I check at the same time for a single element in exists by calling the forall method from exists? I hope that I did not give away too many details!

[Matthew Brown]

Well, get forall working first. Once you're happy with that, ask yourself this. If forall returns false, what does that mean? See if you can phrase the answer using the word "exists".

[Matthew Brown]

I can see a flaw in that pseudocode (possibly more than one, but it depends on how you fix the first one). Where are you referring to s?

[Joe San]

Matthew Brown wrote:Well, get forall working first. Once you're happy with that, ask yourself this. If forall returns false, what does that mean? See if you can phrase the answer using the word "exists".

With the forall I have, it returns false only if the bounds are exceeded!

[Matthew Brown]

Joe Harry wrote:With the forall I have, it returns false only if the bounds are exceeded!

As I said, get forall() working first . Try writing some unit tests.

[chris webster]

Matthew Brown wrote:Well, get forall working first. Once you're happy with that, ask yourself this. If forall returns false, what does that mean? See if you can phrase the answer using the word "exists".

Thanks for the hint, Matthew - now I only have to get map() working...

[Joe San]

Matthew Brown wrote:I can see a flaw in that pseudocode (possibly more than one, but it depends on how you fix the first one). Where are you referring to s?

Ok I thing I got that! s(a) && ! p(a) is a failure. But I'm concerned with the bounds. Why should I check if a is within the bounds and iterate until I reach my bounds? I think I'm missing some understanding here with the question and the bounds.

[Matthew Brown]

Well, one way or another you need to check every value within the bounds, because they might be in the set.

[Joe San]

The mistake that I did was I returned false if my bounds exceeded. I now return true if my bounds exceeded. I think I'm done with forall!

But with the forall implemented, seems exists it just a call to forall!

[Joe San]

The exercise says that we have to use forall to implement exists. Do they literally mean that we have to call forall from our exists? But how could that be possible as forall returns true for all set elements that conform to a given predicate and exists returns true if at least one of the element in the Set conforms to the predicate. Guys, please correct me if I'm wrong!

[Matthew Brown]

Joe Harry wrote:The mistake that I did was I returned false if my bounds exceeded. I now return true if my bounds exceeded. I think I'm done with forall!

Yes, that was the other mistake I was thinking about. What should forall return for an empty set?

Joe Harry wrote:But how could that be possible as forall returns true for all set elements that conform to a given predicate and exists returns true if at least one of the element in the Set conforms to the predicate.

They're different functions, but they are related, which is what my earlier hint was getting at. Try it the other way round. What condition holds if exists returns false?

[James Boswell]

Guys

Sorry to change the subject but am I right in thinking the hard deadline for the first assignment is Tuesday 2nd October?

[Matthew Brown]

James Boswell wrote:Sorry to change the subject but am I right in thinking the hard deadline for the first assignment is Tuesday 2nd October?

Yes, first thing in the morning - from the assignment page (which I think has adjusted to my time zone...which I think is yours as well ):

Due Date: Fri 28 Sep 2012 8:00:00 AM BST
Hard Deadline: Tue 2 Oct 2012 8:00:00 AM BST

[James Boswell]

Thanks Matthew, helpful as always.

[Joe San]

Matthew Brown wrote:

Joe Harry wrote:The mistake that I did was I returned false if my bounds exceeded. I now return true if my bounds exceeded. I think I'm done with forall!

Yes, that was the other mistake I was thinking about. What should forall return for an empty set?

forall should return true for an empty set.

I got the exists working as well, but I wrote them as different functions. The only difference would be the else if part where I return true if I hit a first match. But this cannot be accommodated in the forall as there I will have to iterate the entire bounds and the else if checks for any failures and returns false if any.

[chris webster]

Assignment 2 - how was it for you?

I just submitted mine, but it was hard work - not sure if I agree with the "fun" element in the "funsets" project name...

Q1 was OK, but Q2 was hard, and I'm glad we had Matthew here to offer suggestions. The map() function was particularly tricky - I could see the logic easily enough, but I really struggled with the implementation. Of course, once you see the final one-line solution, it looks really simple. 20-20 hindsight as usual!

This is a good course and I'm finding it pretty challenging already (in Week 2), so I hope I'll be able to keep up until Week 7.

[chris webster]

Joe Harry wrote:I got the exists working as well, but I wrote them as different functions. The only difference would be the else if part where I return true if I hit a first match. But this cannot be accommodated in the forall as there I will have to iterate the entire bounds and the else if checks for any failures and returns false if any.

I think you may lose marks if you don't re-use forall() in your exists() function, and you can definitely implement exists() by calling forall(). Matthew gave us good advice here - think about what happens if a set fails the "forall()" test, and what happens if that test succeeds/fails for only some elements.

[Joe San]

chris webster wrote:Assignment 2 - how was it for you?

I just submitted mine, but it was hard work - not sure if I agree with the "fun" element in the "funsets" project name...

Q1 was OK, but Q2 was hard, and I'm glad we had Matthew here to offer suggestions. The map() function was particularly tricky - I could see the logic easily enough, but I really struggled with the implementation. Of course, once you see the final one-line solution, it looks really simple. 20-20 hindsight as usual!

This is a good course and I'm finding it pretty challenging already (in Week 2), so I hope I'll be able to keep up until Week 7.

Did you use the forall method to implement exists? Do you also have an interator in exists?

[chris webster]

Joe Harry wrote:Did you use the forall method to implement exists? Do you also have an iterator in exists?

My forall() method was similar to the pseudo-code you posted earlier i.e. it uses an iterator.

Assuming my version is correct (I passed the assignment, so hopefully it is), then exists() doesn't need an iterator, because you can implement it by calling forall() in the appropriate way.

As you know, forall(s, p) returns "whether all bounded integers within `s` satisfy `p`".

In other words, with our given set of integers, forall() returns true if ALL elements in s pass test p, and it returns false if ANY elements in s do NOT pass test p.

So think about what happens if you play around with with true and false here to give you a function that does what exists() is supposed to do i.e. return true if "there exists a bounded integer within s that satisfies p".

[Joe San]

chris webster wrote:

Joe Harry wrote:Did you use the forall method to implement exists? Do you also have an iterator in exists?

My forall() method was similar to the pseudo-code you posted earlier i.e. it uses an iterator.

Assuming my version is correct (I passed the assignment, so hopefully it is), then exists() doesn't need an iterator, because you can implement it by calling forall() in the appropriate way.

As you know, forall(s, p) returns "whether all bounded integers within `s` satisfy `p`".

In other words, with our given set of integers, forall() returns true if ALL elements in s pass test p, and it returns false if ANY elements in s do NOT pass test p.

So think about what happens if you play around with with true and false here to give you a function that does what exists() is supposed to do i.e. return true if "there exists a bounded integer within s that satisfies p".

The problem is as soon as you hit true for one of the element you return the method call in the forall. In this case, how could I check for the remaining elements as I still have some more bounds that I have to iterate? This is where I'm stuck!

Did you use Currying to implement exists?

[Joe San]

I have to edit my post as I've written additional test cases and it fails. Have to analyze why!

[Joe San]

Finally the penny dropped. All long, I was trying to play around with the forall, but later I realized with some support that I need to look into the exists, I got it working! Sheesh!

Moving on to the map assignment. So my understanding is given a Set (1,2,3,4), the map function should apply the function f: Int => Int to each elements in the set and return the applied Set. So for the given Set (1,2,3,4) and the function f: (x: Int) => x + x, map should return (2,4,6,8). Hope my understanding is correct!

[chris webster]

Joe Harry wrote:Moving on to the map assignment. So my understanding is given a Set (1,2,3,4), the map function should apply the function f: Int => Int to each elements in the set and return the applied Set. So for the given Set (1,2,3,4) and the function f: (x: Int) => x + x, map should return (2,4,6,8). Hope my understanding is correct!

Yes, that's what the results of map() should look like for your example, but don't get too hung up on thinking about it in terms of iteration, as the solution is more like functional judo using the functions you've already implemented. I spent hours trying to figure it out, and finally got there with some helpful tips from fellow students on the Assignments / Week 2 forum.