First, here's a super quick overview on currying (to be discussed in class further): a curried function to handle multiplication can be defined as:
(define mult
(lambda (a)
(lambda (b)
(* a b))))
A curried function of two arguments, for example, is one that really just takes one argument, and returns another function to handle the second argument.
(a) Define a function curry3 that takes a
three-argument function and returns a curried version of that
function. Thus ((((curry3 f) x) y) z) returns the result
of (f x y z).
(b) In class, we will discuss / have discussed a Scheme function called reduce-left, defined as:
(define reduce-left
(lambda (f value lst)
(if (null? lst)
value
(reduce-left f (f value (car lst)) (cdr lst)))))
Pretend that the built-in Scheme function map worked in parallel, just like in Google's MapReduce implementation. It doesn't in DrRacket, but we'll imagine that it does. If that were true, we could define a function mapreduce, as follows:
(define mapreduce
(lambda (mapper reducer base-case data)
(reduce-left reducer base-case (map mapper data))))
Write a function called google that simulates web searching efficiently in parallel using the above. Specifically, google takes a word to search for, and a list of "web pages" (each of which is a list containing a URL and the words within). For example:
(google 'dave '((www.sillypage.com this page says dave among other things)
(www.happypage.com this page does not say the name)
(www.theone.com but this dave sure says dave)))
should return the list
(www.sillypage.com www.theone.com)
To make this efficient in parallel, your code for google must contain only a single call to mapreduce. Here, I'll write the code for you, mostly:
(define google
(lambda (word pages)
(mapreduce _____ _____ _____ _____)))
Your goal is to define a mapper function, a reducer function, and a base case that can then be used to fill in the blanks above.
FAQ: Can I modify reduce-left, mapreduce, or add other content to google apart from filling in the blanks?
A: Nope. The whole idea here is to simulate using Google's MapReduce library, which is fixed. If you're curious to know more about it, feel free to google it and read the papers, or also read about Hadoop, which is the open source version.
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
Submit your code in a file called curry.rkt.