author Jim Sat, 31 Jan 2015 01:57:45 +0000 (20:57 -0500) committer Jim Sat, 31 Jan 2015 01:57:45 +0000 (20:57 -0500)
 assignment1.mdwn [new file with mode: 0644] patch | blob index.mdwn patch | blob | history

diff --git a/assignment1.mdwn b/assignment1.mdwn
new file mode 100644 (file)
index 0000000..d6fdd9d
--- /dev/null
@@ -0,0 +1,100 @@
+1.  Define a function `zero?` that expects a single number as an argument, and returns `'true` if that number is `0`, else returns `'false`. Your solution should have a form something like this:
+
+        let
+          zero? match lambda x. FILL_IN_THIS_PART
+       in zero?
+
+    You can use the `if...then...else` construction if you like, but it will make it easier to generalize to later problems if you use the `case EXPRESSION of PATTERN1 then RESULT1; PATTERN2 then RESULT2; ... end` construction instead.
+
+2.  Define a function `empty?` that expects a sequence of values as an argument (doesn't matter what type of values), and returns `'true` if that sequence is the empty sequence `[]`, else returns `'false`. Here your solution should have a form something like this:
+
+        let
+          empty? match lambda xs. case xs of
+                                    FILL_IN_THIS_PART
+                                 end
+       in empty?
+
+3.  Define a function `tail` that expects a sequence of values as an argument (doesn't matter what type of values), and returns that sequence with the first element (if any) stripped away. (Applying `tail` to the empty sequence `[]` can just give us back the empty sequence.)
+
+4.  Define a function `drop` that expects two arguments, in the form (*number*, *sequence*), and works like this:
+
+        drop (0, [10, 20, 30])  # evaluates to [10, 20, 30]
+        drop (1, [10, 20, 30])  # evaluates to [20, 30]
+        drop (2, [10, 20, 30])  # evaluates to 
+        drop (3, [10, 20, 30])  # evaluates to []
+        drop (4, [10, 20, 30])  # evaluates to []
+
+    Your solution should have a form something like this:
+
+        let
+          drop match lambda (n, xs). FILL_IN_THIS_PART
+       in drop
+
+    What is the relation between `tail` and `drop`?
+
+5.  Define a function `take` that expects two arguments, in the same form as `drop`, but works like this instead:
+
+        take (0, [10, 20, 30])  # evaluates to []
+        take (1, [10, 20, 30])  # evaluates to 
+        take (2, [10, 20, 30])  # evaluates to [10, 20]
+        take (3, [10, 20, 30])  # evaluates to [10, 20, 30]
+        take (4, [10, 20, 30])  # evaluates to [10, 20, 30]
+
+6.  Define a function `split` that expects two arguments, in the same form as `drop` and `take`, but this time evaluates to a pair of results. It works like this:
+
+        split (0, [10, 20, 30])  # evaluates to ([], [10, 20, 30])
+        split (1, [10, 20, 30])  # evaluates to (, [20, 30])
+        split (2, [10, 20, 30])  # evaluates to ([10, 20], )
+        split (3, [10, 20, 30])  # evaluates to ([10, 20, 30], [])
+        split (4, [10, 20, 30])  # evaluates to ([10, 20, 30], [])
+
+    Here's a way to answer this problem making use of your answers to previous questions:
+
+        let
+         drop match ... ; # as in problem 4
+         take match ... ; # as in problem 5
+          split match lambda (n, xs). let
+                                       ys = take (n, xs);
+                                       zs = drop (n, xs)
+                                     in (ys, zs)
+       in split
+
+    However, we want you to instead write this function from scratch.
+
+7.  Write a function `filter` that expects two arguments. The second argument will be a sequence `xs` with elements of some type *t*, for example numbers. The first argument will be a function `p` that itself expects arguments of type *t* and returns `'true` or `'false`. What `filter` should return is a sequence that contains exactly those members of `xs` for which `p` returned `'true`. For example, helping ourself to a function `odd?` that works as you'd expect:
+
+        filter (odd?, [11, 12, 13, 14])  # evaluates to [11, 13]
+       filter (odd?, )              # evaluates to 
+       filter (odd?, [12, 14])          # evaluates to []
+
+8.  Write a function `partition` that expects two arguments, in the same form as `filter`, but this time evaluates to a pair of results. It works like this:
+
+        partition (odd?, [11, 12, 13, 14])  # evaluates to ([11, 13], [12, 14])
+       partition (odd?, )              # evaluates to (, [])
+       partition (odd?, [12, 14])          # evaluates to ([], [12, 14])
+
+9.  Write a function `double` that expects one argument which is a sequence of numbers, and returns a sequence of the same length with the corresponding elements each being twice the value of the original element. For example:
+
+        double [10, 20, 30]  # evaluates to [20, 40, 60]
+       double []            # evaluates to []
+
+10.  Write a function `map` that generalizes `double`. This function expects a pair of arguments, the second being a sequence `xs` with elements of some type *t*, for example numbers. The first argument will be a function `f` that itself expects arguments of type *t* and returns some type *t'* of result. What `map` should return is a sequence of the results, in the same order as the corresponding original elements. The result should be that we could say:
+
+        let
+         map match lambda (f, xs). FILL_IN_THIS_PART;
+         double match lambda xs. map ((lambda x. 2*x), xs)
+       in ...
+
+11. Write a function `map2` that generalizes `map`. This function expects a triple of arguments: the first being a function `f` as for `map`, and the second and third being two sequences. In this case `f` is a function that expects *two* arguments, one from the first of the sequences and the other from the corresponding position in the other sequence. The result should behave like this:
+
+        map2 ((lambda (x,y). 10*x + y), [1, 2, 3], [4, 5, 6])  # evaluates to [14, 25, 36]
+
+
+EXTRA CREDIT PROBLEMS
+
+*Will post shortly*
+
+<!-- take_while, drop_while, split_while -->
+
+<!-- unmap2 (g, xs) where g x \mapsto (y,z), and unmap2 (g, [x1, x2, x3]) \mapsto ([y1, y2, y3], [z1, z2, z3]) -->
+
index 50d1c03..5cf1180 100644 (file)
@@ -38,11 +38,10 @@ week's homework, for instance, before the session.

Here is information about [[How to get the programming languages running on your computer]].

-Here are Lecture notes for [[Week1]]; [[Assignment1]]. (*These will be posted soon.*)
+Here are Lecture notes for [[Week1]]; [[Assignment1]]. (*Lecture notes will be posted soon.*)

>      Topics: Basics of Functional Programming

-<!--
*      Henceforth, unless we say otherwise, every homework will be "due" by
Wednesday morning after the Thursday seminar in which we refer to it.
(Usually we'll post the assignment shortly before the seminar, but don't
@@ -73,7 +72,6 @@ too hard for you to complete to your own satisfaction, it is still
very much worthwhile (and very much appreciated) if you would explain
what is difficult, what you tried, why what you tried didn't work, and
what you think you need in order to solve the problem.
--->

## Course Overview ##