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?

SCJP 1.4, SCWCD 1.4 - Hints for you, Certified Scrum Master

Did a rm -R / to find out that I lost my entire Linux installation!

Using the built in sum method is definitely cheating .

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

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.

SCJP 1.4, SCWCD 1.4 - Hints for you, Certified Scrum Master

Did a rm -R / to find out that I lost my entire Linux installation!

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

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

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

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!

No more Blub for me, thank you, Vicar.

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.

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

SCJP 1.4, SCWCD 1.4 - Hints for you, Certified Scrum Master

Did a rm -R / to find out that I lost my entire Linux installation!

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.

No more Blub for me, thank you, Vicar.

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!

Did a rm -R / to find out that I lost my entire Linux installation!

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.

No more Blub for me, thank you, Vicar.

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?

Supposing, I have my p as defined below:

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

Now the call to forall:

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!

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.

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!

Did a rm -R / to find out that I lost my entire Linux installation!

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.

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

Did a rm -R / to find out that I lost my entire Linux installation!

Did a rm -R / to find out that I lost my entire Linux installation!

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 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

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.

Did a rm -R / to find out that I lost my entire Linux installation!

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.

No more Blub for me, thank you, Vicar.

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.

No more Blub for me, thank you, Vicar.

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?

Did a rm -R / to find out that I lost my entire Linux installation!

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".

No more Blub for me, thank you, Vicar.

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?

Did a rm -R / to find out that I lost my entire Linux installation!

Did a rm -R / to find out that I lost my entire Linux installation!

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!

Did a rm -R / to find out that I lost my entire Linux installation!

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.

No more Blub for me, thank you, Vicar.

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |