• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Scala Coursera - Week 4

 
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here we go again. At least we will do when the videos come online...
 
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This week's assignment is going to be about Huffman Coding. Interesting to learn these stuff.
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Isn't Week4 supposed to be about Collections as per the Syllabus below?

https://www.coursera.org/course/progfun

The Week4 video lectures says that it is about Types and Pattern matching. I'm a bit surprised about this.
 
chris webster
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Joe Harry wrote:Isn't Week4 supposed to be about Collections as per the Syllabus below?

https://www.coursera.org/course/progfun

The Week4 video lectures says that it is about Types and Pattern matching. I'm a bit surprised about this.


Yes - it looks like we've skipped to the topic for Week 5 instead.
 
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Maybe there's just some overlap. I'm watching the first video at the moment and it's about linked lists, so collections are definitely on the menu as well. But it's a new course, and it wouldn't surprise me if they've decided to move things round a bit since the syllabus was announced.

Edit: OK, that may be overstated, the linked list is just a demonstration of polymorphism and generics. Looks like they've swapped weeks as Chris said.
 
chris webster
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The assignment has now appeared online and as Joe says, it's about Huffman coding. In case (like me), this is new to you, there's a handy 10 minute video introduction to Huffman coding here.

Also, despite the fact we've skipped the Collections lectures, there are loads of methods in the Scala List class that will come in handy here.

Incidentally, you may have received a mail from Coursera about cheating - apparently some people have been putting the assignment answers on Github - so we'll need to maintain our customary discretion about any hints we publish here: we don't want any unfortunate misunderstandings.
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Looks like for this week, I might have to consult the Scala API documentation many times to find out the right methods that I could use to implement the assignments. I understood the theory behind Huffman coding. I also managed to get the weight and chars done as well. Part 1 is done. 2 lines each for weight and chars.

Would start with Part2 tomorrow.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Got the decoding working, though I did resort to decoding it manually as a debugging aid! The encoding can wait .
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Matthew Brown wrote:Got the decoding working, though I did resort to decoding it manually as a debugging aid! The encoding can wait .



Sounds great. So that would mean you are done with Part1, Part2? But I'm sure most of the solutions this time aren't one liners as before.
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What is meant by Singleton? I do not get this comment on the singleton method.

Checks whether the list `trees` contains only one single code tree

 
chris webster
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Joe Harry wrote:What is meant by Singleton? I do not get this comment on the singleton method.


Yes, I thought that was a bit unclear, but I understood it as meaning simply that we should check if there is only one tree left in the list. We use the singleton() function later on in the until() function, which is supposed to stop when you have a "list containing only a single tree".

About to start looking at decoding...
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm trying out the times method and I'm surprised that eclipse complains about the following line:



It says that chars.head is not a member of List[Char]. My accu is of type List[(Char, Int)] and the chars is a List[Char]. So chars.head should result in a Char. Is there something fundamentally wrong with my understanding?

Later I tried to print it and to my surprise, chars.head evaluates to an Int

 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm not sure exactly what you're trying to do there, but that syntax looks a bit strange to me:

(* not tested - I have a vague memory of having trouble creating tuples like that, but intuitively it seems right)

Edit - posted before you added the second bit of the message
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This line
evaluates to

Note that isn't creating a List of Tuples. It's creating a list containing two items. One is a Char, the second is an Int, but it's probably inferring List[Int] (because Char can be automatically converted to an Int).
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Matthew Brown wrote:This line
evaluates to

Note that isn't creating a List of Tuples. It's creating a list containing two items. One is a Char, the second is an Int, but it's probably inferring List[Int] (because Char can be automatically converted to an Int).



Got that now. It takes a bit of time for me to get used to the syntax style in Scala.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
By the way, there's a shorthand for anonymous functions that you can use when it's a relatively simple function. Your code:
can be reduced to
because of type inference, but that can be simplified further to:

Obviously, only use it if you think it makes things clearer. Sometimes it does, sometimes it doesn't.
 
chris webster
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just finished implementing the encoding using the Huffman tree and I'm looking at the stuff for building a code table, merging sub-tables and so on. Is it just me, or is this needlessly complicated?

We already know what characters are held in the tree because there's a list of them stored at each node, including the root, and we already know how to encode an arbitrary message e.g. of a single character. So it would seem simpler (to me at least) if we just worked through the characters, fetched the encoding for each one, and added each char/code pair to the code table. I reckon that's probably just a couple of lines of code, instead of all this table-merging stuff.

I suppose they want us to practice recursion up and down trees and merging lists/trees, but I'm getting a wee bit tired of all this academic CS101 stuff that I doubt I'll ever need to know again in whatever remains of my career.

OK, rant over. I'm off to the pub for lunch before I start on the code table: Cheers!

 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Did you guys had to sort anything for the combine implementation?

I tried to sort my resulting List using the sortWith method as below:



But seems like the sorting won't happen!
 
chris webster
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Joe Harry wrote:Did you guys had to sort anything for the combine implementation?
I tried to sort my resulting List using the sortWith method as below:

But seems like the sorting won't happen!


The comment for the combine function says:

* The parameter `trees` of this function is a list of code trees ordered by ascending weights.


I didn't need to sort the list(s) here because the incoming list is already sorted. You just need to put the new Fork node, containing the first 2 elements of the original list, into the correct position in the rest of the original list. There are some useful methods on the Scala List class API that will help you do this.


 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I sorted it using sortBy() because it was easy, but after sleeping on it realised that it's not necessary, as Chris says, so I'm planning to change it when I'm next working on it.
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Matthew Brown wrote:I sorted it using sortBy() because it was easy, but after sleeping on it realised that it's not necessary, as Chris says, so I'm planning to change it when I'm next working on it.



The Javadoc of the combine method also says the following:

This node is then added back into the remaining elements of `trees` at a position such that the ordering by weights is preserved.



What happens if you test your combine method with the following test case?



Mine fails even though I do a sortWith by passing the head and tail as I've mentioned in my post above!
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
May be a silly question, but you are remembering to use the return value of sortWith, aren't you, because the list you call it on is unaffected?

Mine passed a comparable test. What I'm not 100% sure of (because it depends on the sort algorithm) is whether it might possibly reorder nodes that have the same weight. And also, I'm not sure if that's actually a problem. But I'm going to change it anyway.
 
Joe San
Ranch Hand
Posts: 10198
3
Mac PPC Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Matthew Brown wrote:May be a silly question, but you are remembering to use the return value of sortWith, aren't you, because the list you call it on is unaffected?



I did not quite understand your statement here?

You are right. The List is unaffected by the sortWith and that us exactly my concern.

What I get as a restult of the call to the combine method is as below:

 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What I mean is - List is immutable. The method returns a new List with the required order. If that's where you're going wrong, it's the equivalent mistake to:
 
chris webster
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Joe Harry wrote:Mine fails even though I do a sortWith by passing the head and tail as I've mentioned in my post above!


I don't know if this will help (and we don't want to be accused of cheating of course ), but here is one way to put a new item in an ordered list without having to re-sort it.

  • Say you have an ordered list: [1, 7 , 12, 15, 21]
  • You now want to add an extra element (13) in the correct position.
  • One way to do this is by breaking your original list in two at the appropriate point e.g. where the element values are < your new element (13).
  • This would give you two new lists: [1, 7 , 12] and [15, 21]
  • You could now build a new list by combining these two lists with your new element: [1, 7 , 12] and [13] and [15, 21] ---> [1, 7 , 12, 13, 15, 21]

  • The Scala List API provides methods to do each of these steps.

    Mind you, the submission tests have just informed me that I have a separate bug in my combine() method! Doh!

    Edit: Bug fixed - forgot to handle an empty list of Trees in combine() and singleton(). Also FYI, you will lose points if you don't call mergeCodeTables() from the convert() function.

     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Matthew Brown wrote:What I mean is - List is immutable. The method returns a new List with the required order. If that's where you're going wrong, it's the equivalent mistake to:



    My logic has somethihng like this:



     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Could you guys help me visualize how the Tree would look like for the following CodeTree:

     
    Matthew Brown
    Bartender
    Posts: 4568
    9
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Fair enough. As I said, might be a silly question, but it would have explained the symptoms.

    Here's your tree for that structure...

    so 'a' -> 00, 'b' -> 01, 'c' -> 1

    (I actually sketched the whole French alphabet tree while I was debugging!)

    Someone's actually posted some code to the Coursera forums that will draw any tree for you, though I haven't tried it.
     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I just managed to draw that myself. The SICP book helped me with that.
     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Done with the decode and encode. It was easier than I originally thought.

    Coming back to combine. What did you guys get for the following test case?

     
    Matthew Brown
    Bartender
    Posts: 4568
    9
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Since you're only supposed to call combine() with a list already sorted by weight, I don't think the behaviour is defined. My implementation would produce the second of those.
     
    chris webster
    Bartender
    Posts: 2407
    36
    Scala Python Oracle Postgres Database Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Matthew Brown wrote:Since you're only supposed to call combine() with a list already sorted by weight, I don't think the behaviour is defined. My implementation would produce the second of those.


    Same result here: submitting Joe's list to my combine() function passes the second test but not the first.

    combine() expects the input list to be ordered beforehand anyway, so why are you doing this?
     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I got confused on the scaladoc comments given for this method where it says:

     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I still have untill, createCodeTree and decodedSecret pending. Could you guys throw some light on untill and decodedSecret?
     
    Greenhorn
    Posts: 4
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Joe Harry wrote:I still have untill, createCodeTree and decodedSecret pending. Could you guys throw some light on untill and decodedSecret?



    until is pretty simple, just focus on function passing and recursion. The result can/should be a concise effective method.
     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Yes, until was simple and so is makeCodeTree. decodedSecret is pending!
     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    decodedSecret was the easiest of all.

    Just wanted to check with you guys as to what you got for the following test case when you print out the method calls?



    Do you guys also get what I got above?

     
    Greenhorn
    Posts: 24
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    HI everyone,
    I was wondering if you guys use recursion, pattern matching in implementing times() method? Because my solution is (again) very imperative.
     
    Joe San
    Ranch Hand
    Posts: 10198
    3
    Mac PPC Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Wen Tong Lin wrote:HI everyone,
    I was wondering if you guys use recursion, pattern matching in implementing times() method? Because my solution is (again) very imperative.



    You are supposed to use pattern matching and recursion and so is the purpose of doing this course. If you think your solution is imperative, take a look at the videos again and understand the concepts and ideas behind recursion and pattern matching. Take a look at how accumulator pattern works in recursion and you will be better at writing recursive algorithms.
     
    chris webster
    Bartender
    Posts: 2407
    36
    Scala Python Oracle Postgres Database Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Wen Tong Lin wrote:HI everyone,
    I was wondering if you guys use recursion, pattern matching in implementing times() method? Because my solution is (again) very imperative.


    My implementation of the times() method is half a line of code, and it uses several functions that are provided by the Scala List API to map the input list via some transformations into the output list. This seems to be a fairly functional approach - it passes the tests, anyway!

    I did use recursion and pattern matching for some of the other methods, though.
     
    Don't get me started about those stupid light bulbs.
    reply
      Bookmark Topic Watch Topic
    • New Topic