Action Items
PS2 is due Monday, September 30. You should be at least up to Problem 4 by now.
Before Thursday's class, read either the paper or slides for MapReduce: Simplified Data Processing on Large Clusters (Jeffrey Dean and Sanjay Ghemawat, Symposium on Operating System Design and Implementation, December, 2004).
Links
Linux Foundation Annual Linux Development Report (16 September 2013) (To download the full PDF, you need to survive an intrusive web form, which seems odd from an organization who's goal is to promote openness on the web.)
Github is your
resume
Github is my
resume
StackOverflow: Top Rust Users; Top Java
Users (Which list is
easier to make?)
Lists in Rust
For this exercise, we'll implement a linked list data structure using Rust. (Note that the Rust library provides a vector type, so it is unlikely you would want to use this linked list code, but it is a worthwhile exercise to explore some issues in programming in Rust.)
Version 1: Automatically Managed
struct Node {
head : int,
tail : Option<@Node>
}
type List = Option<@Node> ;
impl ToStr for List {
fn to_str(&self) -> ~str {
fn elements_to_str(n: @Node) -> ~str {
match (n.tail) {
None => fmt!("%?", n.head),
Some(tail) => fmt!("%?, %s", n.head, elements_to_str(tail))
}
}
match(*self) {
None => ~"Null",
Some(n) => fmt!("[%s]", elements_to_str(n))
}
}
}
fn main() {
let lst : List = Some(@Node{head: 1, tail: Some(@Node{head : 2, tail: Some(@Node{head: 3, tail: None})})});
println(fmt!("%s", lst.to_str()));
}
Version 2: Mutable List with Mapping
struct Node {
head : int,
tail : Option<@mut Node>
}
type List = Option<@mut Node> ;
trait Map {
fn mapr(&self, &fn(int) -> int);
}
trait Filter {
fn filtr(&self, &fn(int) -> bool);
}
impl Map for List {
fn mapr(&self, f: &fn(int) -> int) { // Thanks to dbaupp for figuring out why this breaks when called "map"!
let mut current = *self;
loop {
match(current) {
None => break,
Some(node) => { node.head = f(node.head); current = node.tail },
}
}
}
}
impl ToStr for List {
fn to_str(&self) -> ~str {
fn elements_to_str(n: @mut Node) -> ~str {
match (n.tail) {
None => fmt!("%?", n.head),
Some(tail) => fmt!("%?, %s", n.head, elements_to_str(tail))
}
}
match(*self) {
None => ~"Null",
Some(n) => fmt!("[%s]", elements_to_str(n))
}
}
}
fn main() {
let lst : List = Some(@mut Node{head: 1, tail: Some(@mut Node{head : 2, tail: Some(@mut Node{head: 3, tail: None})})});
println(lst.to_str());
lst.mapr(|x: int| { x + 1 });
println(lst.to_str());
lst.mapr(|x: int| { x * x });
println(lst.to_str());
lst.mapr(|x: int| { if x % 2 == 0 { x } else { -x }});
println(lst.to_str());
}
Exercise 1. Add an append(&self, List) method that appends two lists. (You should think carefully about what semantics append should have
before implementing it.)
Exercise 2. Add an filtr(&self, &fn(int) -> bool) method that removes elements for which a predicate is not true from a list.
Version 3: Owned Nodes
// listo.rs - Owned List
struct Node {
head : int,
tail : Option<~Node>
}
type List = Option<~Node> ;
trait Map {
fn mapr(&self, &fn(int) -> int) -> List;
}
impl Map for List {
fn mapr(&self, f: &fn(int) -> int) -> List {
match(*self) {
None => None,
// need the ref here to keep the matched variable type borrowed
Some(ref node) => { Some(~Node{ head: f(node.head), tail: node.tail.mapr(f) }) },
}
}
}
impl ToStr for List {
fn to_str(&self) -> ~str {
fn elements_to_str(n: &~Node) -> ~str {
match (n.tail) {
None => fmt!("%?", n.head),
Some(ref tail) => fmt!("%?, %s", n.head, elements_to_str(tail))
}
}
match(*self) {
None => ~"Null",
Some(ref n) => fmt!("[%s]", elements_to_str(n))
}
}
}
fn main() {
let lst0 : List = Some(~Node{head: 1, tail: Some(~Node{head : 2, tail: Some(~Node{head: 3, tail: None})})});
println(lst0.to_str());
let lst1 = lst0.mapr(|x: int| { x + 1 });
println(lst1.to_str());
let lst2 = lst1.mapr(|x: int| { x * x });
println(lst2.to_str());
let lst3 = lst2.mapr(|x: int| { if x % 2 == 0 { x } else { -x }});
println(lst3.to_str());
println(lst0.to_str());
}
Exercise 3. Make a generic List where the element type is a type
parameter and can be any type that implements ToStr.
Exercise 4. Evaluate the performance and usability tradeoffs for the different list implementations.