You are creating Nile.com, which you hope will be the next big thing in online bookstores. You know that you can save money by anticipating what books people will buy; you will pass these savings on to your users by offering a discount if they buy books that Nile recommends.This assignment is meant to introduce you to the concept of collaborative filtering.
To do this, you offer an incentive for people to upload their lists of recommended books. From their lists, you can establish suggested pairs. A pair of books is a suggested pair if both books appear on one person’s recommendation list. Of course, some suggested pairs are more popular than others. Also, any given book is paired with some books much more frequently than with others.
Bezos II by Bo Burnham
Past students have found this assignment quite difficult relative to when it appears in the course. Think hard about decomposing the problem into simpler pieces rather than trying to solve it entirely in one step. Give yourself enough time!
A list of books recommended by one user is represented as a File:
| file(name :: String, content :: List<String>)
file("vty.txt", [list: "Crime and Punishment", "Heaps are Lame"])
You need to use Files of recommended books in the two following tasks.
A book title cannot be the empty string.
In what follows, we will say a book is paired with another book if both books are listed in the same file.
When someone buys a book, you want to suggest other books to accompany it. Specifically, you should provide the book that is paired most frequently with the book the user bought, along with a count of how frequent this is. Because there may be more than one book with that count, you should return a list of books (even if there is only one) as well as the count. This will be in the form of a Recommendation:
| recommendation(count :: Number, content :: List<A>)
Define the following function:
fun recommend(title :: String, book-records :: List<File>) -> Recommendation<String>
recommend takes a book title and a list of Files and produces a Recommendation. The Recommendation’s content is a list of the titles of the books that are most often paired with the input book. The Recommendation’s count is the number of times the books in the content list are each paired with the input book. When no pairing can be found, recommend should return recommendation(0,[list: ]).
Sometimes, an indecisive user just wants a recommendation of good books to read, not based on their previous purchases. Nile offers not one recommendation at a time, but pairs of them! Wow! To support this, you must be able to identify the most popular pairs of suggested books, i.e., the pairs of books that are listed together in the most number of files. Return the most popular pair, with a count of how often it occurs. Again, because there may be multiple pairs with the same count, you should return a list of pairs (even if there is only one).
Define the following function:
fun popular-pairs(records :: List<File>) -> Recommendation<BookPair>
popular-pairs takes a list of Files and produces a Recommendation. The Recommendation’s content is a list of BookPairs (defined below). Two books form a pair if they appear together in a given input File. The output of popular-pairs is the most frequently occurring pair (or pairs) found in all the input Files. So, if there is a tie for the most popular pair, all tied pairs are returned in the list. Each pair should appear exactly once and order is irrelevant. The Recommendation’s count is the number of times each pair occurred together in a file. When no pairing can be found, popular-pairs should return recommendation(0, [list: ]).
| pair(book1 :: String, book2 :: string)
For this assignment, you will need to write your own version of any built-in methods and functions that you choose to use, other than the higher-order functions map, filter, and fold.This is to force you to practice: you should be getting able to write such functions without much difficulty. Also, studies show that drill is a really good way to get better at programming. You may also use the variants of map and fold provided by Pyret.
You are welcome to use operators on Strings (+, <=, >, ==, etc.).
For lists, you may may not use any other built-in functions (such as length, member, get, split-at, etc.) other than the functions mentioned above. You should be able to write your own versions of these functions using link and empty.
The context for Nile should only let you use the functions we’ve permitted, but nevertheless you should refrain from trying to use any list built-ins without writing them yourself. Due to the way that we write contexts, list methods (like .length) are still accessible, but you should similarly avoid using them.
When writing your own version of built-in functions, we do expect to see the same steps of design recipe as you used in the placement, including a reasonable sample of examples (but not a detailed test suite).
Because we have not yet discussed any efficiency measures in class, you are not asked to consider the efficiency of your implementation.
You should not write your own data definitions for File, Recommendation, and BookPair. These have already been provided for you. Please don’t change what has been provided in the template, nor redefine the data definitions, or else your code will fail our autograder.
We have also redefined equality for both Recommendation and BookPair. When checking two Recommendations for equality, the order of the content list is ignored. When checking two BookPairs for equality, the order of book1 and book2 is ignored.
In essence, dating apps use collaborative filtering to aggregate opinions. How does this work out in practice?
Read this article.
(Optional: you can play the game if you want.)
How might aggregating opinions not generate favorable results? Pick a domain that interests you, aside from the one covered in the article, and discuss it.
Just in case you’ve forgotten, for this and all future assignments:
Your writeup of your findings should be brief and crisp. Anything longer than three paragraphs (excluding the text you pasted in, of course) is definitely too long. Be concrete by drawing on your experience. You can prepare your writeup in whatever editor you want; submit in text or PDF.
In addition submitting your own SRC write-up, you will get the opportunity to reflect on some of your classmates’ ideas and insights. In a future assignment, you will receive a curated set of excerpts from some of your classmates’ submissions. You will have the opportunity to read and reflect on their ideas. If your submission is selected to be shared with other students, it will, of course, be shared completely anonymously. However, if you would like your submission to not be shared, you will have an option to let us know when submitting your write-up on Gradescope.