From: Jim Date: Tue, 10 Feb 2015 11:12:22 +0000 (-0500) Subject: Merge branch 'master' into working X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=07ebc9292a8db8b98707232d2d01717293f473e9;hp=077b3c9d4eb81dc63a3b5cf75d4185812728e1f3 Merge branch 'master' into working * master: (22 commits) rename exercises/assignment2_answers.mdwn to exercises/_assignment2_answers.mdwn just link to hint for `reverse` compare `cons` create page link to answers1 formatting, code style link to answers to week1 homework create solutions redo hint links removed create page create page reorganize, add some (as-yet-unlinked) titles for week 3 add anchors tweak explanation of why `f` is curried clarify why Lambda Calculus prefers curried functions, thanks for input Kyle 38e98c659e1819ddd4457935508ee12824b50241 edits to combinatory logic added old CL text clarify constraints ... --- diff --git a/content.mdwn b/content.mdwn index cabcc71b..52945505 100644 --- a/content.mdwn +++ b/content.mdwn @@ -5,35 +5,61 @@ week in which they were introduced. ## Topics by content ## -* [[Introduction to functional programming|topics/week1 kapulet intro]] +* Functional Programming + + * [[Introduction|topics/week1 kapulet intro]] + * [[Week 1 Advanced notes|topics/week1 kapulet advanced]] + * [["Rosetta Stone" page #1 for Kaupulet, Scheme, OCaml, Haskell|rosetta1]] + * Offsite links for help on [[learning Scheme]], [[OCaml|learning OCaml]], and [[Haskell|learning Haskell]] + * List Comprehensions + +* Order, "static versus dynamic" + + * [[Order in programming languages and natural language|topics/week1 order]] + * Reduction Strategies and Normal Forms in the Lambda Calculus + +* The Lambda Calculus + + * [[Introduction to the Lambda Calculus|topics/week2 lambda intro]] + * [[Advanced notes on the Lambda Calculus|topics/week2 lambda advanced]] + * Encoding data types in the Lambda Calculus + * [[Booleans|topics/week2 encodings#booleans]] + * [[Tuples|topics/week2 encodings#tuples]] + * [[Lists|topics/week2 encodings#lists]], v1 (as right-folds) + * [[Numbers|topics/week2 encodings#numbers]], v1 ("Church's encoding") + * How to get the `tail` of v1 lists? + * Reduction Strategies and Normal Forms + + +* Combinatorial Logic -* [[Order: static versus dynamic|topics/week1 order]] ## Topics by week ## Week 1: -* [[Order in programming languages and natural language|topics/week1 order]] +* [[Order in programming languages and natural language|topics/week1 order]] This discussion considers conjunction in a language that recognized presupposition failure. -* [[Introduction to functional programming|topics/week1 kapulet intro]] +* [[Introduction to functional programming|topics/week1 kapulet intro]] Basics of functional programming: `let`, `case`, pattern matching, and recursion. Definitions of factorial. -* [[Advanced notes on functional programming|topics/week1 kapulet advanced]] -* [[Homework for week 1|exercises/assignment1]] +* [[Advanced notes on functional programming|topics/week1 kapulet advanced]] +* [[Homework for week 1|exercises/assignment1]] ([[Answers|exercises/assignment1_answers]]) Week 2: -* [[Introduction to the Lambda Calculus|topics/week2 lambda intro]] -* [[Advanced notes on the Lambda Calculus|topics/week2 lambda advanced]] -* [[Encoding Booleans, Tuples, Lists, and Numbers|topics/week2 encodings]]; -* [[Homework for week 2|exercises/assignment2]] +* [[Introduction to the Lambda Calculus|topics/week2 lambda intro]] +* [[Advanced notes on the Lambda Calculus|topics/week2 lambda advanced]] +* [[Encoding Booleans, Tuples, Lists, and Numbers|topics/week2 encodings]] +* [[Homework for week 2|exercises/assignment2]] Week 3: -* More on Lists -Introduces list comprehensions, shows how to encode `tail` in the Lambda Calculus -* Combinatorial Logic -* Homework for week 3 +* More on Lists +Introduces list comprehensions, discusses how to get the `tail` of lists in the Lambda Calculus +* Combinatorial Logic +* Reduction Strategies and Normal Forms +* Homework for week 3 diff --git a/exercises/_assignment2_answers.mdwn b/exercises/_assignment2_answers.mdwn new file mode 100644 index 00000000..e131311c --- /dev/null +++ b/exercises/_assignment2_answers.mdwn @@ -0,0 +1,205 @@ +Syntax +------ + +Insert all the implicit `( )`s and `λ`s into the following abbreviated expressions. + +1. `x x (x x x) x` + `(((x x) ((x x) x)) x)` +2. `v w (\x y. v x)` + `((v w) (\x (\y (v x))))` +3. `(\x y. x) u v` + `(((\x (\y x)) u) v)` +4. `w (\x y z. x z (y z)) u v` + `(((w (\x (\y (\z ((x z) (y z)))))) u) v)` + +Mark all occurrences of `(x y)` in the following terms: + +5. `(\x y. x y) x y` +6. `(\x y. x y) (x y)` +7. `\x y. x y (x y)` + +Reduction +--------- + +Find "normal forms" for the following---that is, reduce them until no more reductions are possible. As mentioned in the notes, we'll write `λx` as `\x`. If we ever say "reduce" without qualifications, we mean just "beta-reduce" (as opposed to "(beta + eta)-reduce"). + +8. `(\x \y. y x) z` ~~> `\y. y z` +9. `(\x (x x)) z` ~~> `z z` +10. `(\x (\x x)) z` ~~> `\x x` +11. `(\x (\z x)) z` ~~> `\y z`, be sure to change `\z` to a different variable so as not to "capture" `z` +12. `(\x (x (\y y))) (\z (z z))` ~~> `\y y` +13. `(\x (x x)) (\x (x x))` umm..., reductions will forever be possible, they just don't "do" much +14. `(\x (x x x)) (\x (x x x))` that's just mean + + + +Booleans +-------- + +For these questions, and the ones on triples below, we're setting them up so as to encourage you to experiment with Racket and to formulate your answer in Scheme/Racket syntax. But you can answer in Lambda Calculus syntax if you prefer. + +Recall our definitions of true and false. + +> **true** is defined to be `\t f. t` +> **false** is defined to be `\t f. f` + +In Racket, these functions can be defined like this: + + (define true (lambda (t) (lambda (f) t))) + (define false (lambda (t) (lambda (f) f))) + +(Note that they are different from Racket's *primitive* boolean values `#t` and `#f`.) + + +15. Define a `neg` operator that negates `true` and `false`. + + Expected behavior: + + (((neg true) 10) 20) + + evaluates to `20`, and + + (((neg false) 10) 20) + + evaluates to `10`. + + (define neg (lambda (p) ((p false) true))) + +16. Define an `or` operator. + + (define or (lambda (p) (lambda (q) ((p p) q)))) + + or: + + (define or (lambda (p) (lambda (q) ((p true) q)))) + + +17. Define an `xor` operator. If you haven't seen this term before, here's a truth table: + + true xor true == false + true xor false == true + false xor true == true + false xor false == false + + + + (define xor (lambda (p) (lambda (q) ((p (neg q)) q)))) + + +Triples +------- + +Recall our definitions of ordered triples. + +> the triple **(**a**, **b**, **c**)** is defined to be `\f. f a b c` + +To extract the first element of a triple `t`, you write: + + t (\fst snd trd. fst) + +Here are some definitions in Racket: + + (define make-triple (lambda (fst) (lambda (snd) (lambda (trd) (lambda (f) (((f fst) snd) trd)))))) + (define fst_of_three (lambda (fst) (lambda (snd) (lambda (trd) fst)))) + (define snd_of_three (lambda (fst) (lambda (snd) (lambda (trd) snd)))) + +Now we can write: + + (define t (((make-triple 10) 20) 30)) + (t fst_of_three) ; will evaluate to 10 + (t snd_of_three) ; will evaluate to 20 + +If you're puzzled by having the triple to the left and the function that +operates on it come second, think about why it's being done this way: the triple +is a package that takes a function for operating on its elements *as an +argument*, and returns *the result of* operating on its elements with that +function. In other words, the triple is a higher-order function. + + +18. Define the `swap12` function that permutes the elements of a triple. Expected behavior: + + (define t (((make-triple 10) 20) 30)) + ((t swap12) fst_of_three) ; evaluates to 20 + ((t swap12) snd_of_three) ; evaluates to 10 + + Write out the definition of `swap12` in Racket. + + (define swap12 (lambda (x) (lambda (y) (lambda (z) + (lambda (f) (((f y) x) z)))))) + + +19. Define a `dup3` function that duplicates its argument to form a triple +whose elements are the same. Expected behavior: + + ((dup3 10) fst_of_three) ; evaluates to 10 + ((dup3 10) snd_of_three) ; evaluates to 10 + + + + (define dup3 (lambda (x) + (lambda (f) (((f x) x) x)))) + +20. Define a `dup27` function that makes +twenty-seven copies of its argument (and stores them in a data structure of +your choice). + + OK, then we will store them in a triply-nested triple: + + (define dup27 (lambda (x) (dup3 (dup3 (dup3 x))))) + +Folds and Lists +--------------- + +21. Using Kapulet syntax, define `fold_left`. + + # fold_left (f, z) [a, b, c] == f (f (f z a) b) c + letrec + fold_left (f, z) xs = case xs of + [] then z; + x' & xs' then fold_left (f, f (z, x')) xs' + end + in fold_left + + +22. Using Kapulet syntax, define `filter` (problem 7 in last week's homework) in terms of `fold_right` and other primitive syntax like `lambda`, `&`, and `[]`. Don't use `letrec`! All the `letrec`-ing that happens should come from the one inside the definition of `fold_right`. + + let + filter (p, xs) = fold_right ((lambda (y, ys). if p y then y & ys else ys), []) xs + in filter + +23. Using Kapulet syntax, define `&&` in terms of `fold_right`. (To avoid trickiness about the infix syntax, just call it `append`.) As with problem 22 (the previous problem), don't use `letrec`! + + let + xs && ys = fold_right ((&), ys) xs + # or append (xs, ys) = ... + in (&&) + +24. Using Kapulet syntax, define `head` in terms of `fold_right`. When applied to a non-empty list, it should give us the first element of that list. When applied to an empty list, let's say it should give us `'err`. As with problem 22, don't use `letrec`! + + let + head xs = fold_right ((lambda (y, _). y), 'err) xs + in head + +25. We mentioned in the Encoding notes that `fold_left (flipped_cons, []) xs` would give us the elements of `xs` but in the reverse order. So that's how we can express `reverse` in terms of `fold_left`. How would you express `reverse` in terms of `fold_right`? As with problem 22, don't use `letrec`! + + See the [[hint|assignment2 hint]]. + + +Numbers +------- + +26. Given that we've agreed to Church's encoding of the numbers: + + `0 ≡ \f z. z` + `1 ≡ \f z. f z` + `2 ≡ \f z. f (f z)` + `3 ≡ \f z. f (f (f z))` + `...` + + How would you express the `succ` function in the Lambda Calculus? + + let succ = \n. \f z. f (n f z) in ... + + Compare the definition of `cons`, which has an additional element: + + `let cons = \d ds. \f z. f d (ds f z) in ...` diff --git a/exercises/assignment1_answers.mdwn b/exercises/assignment1_answers.mdwn new file mode 100644 index 00000000..49668201 --- /dev/null +++ b/exercises/assignment1_answers.mdwn @@ -0,0 +1,233 @@ +1. Define a function `zero?` that expects a single number as an argument, and returns `'true` if that number is `0`, else returns `'false`. + + let + zero? match lambda x. case x of + 0 then 'true; + y then 'false + end + in zero? + + +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`. + + let + empty? match lambda xs. case xs of + [] then 'true; + _ & _ then 'false + end + in empty? + + The second `case` clause could also just be `_ then 'false`. + +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.) + + let + tail match lambda xs. case xs of + [] then []; + _ & xs' then xs' + end + in tail + + +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 [30] + drop (3, [10, 20, 30]) # evaluates to [] + drop (4, [10, 20, 30]) # evaluates to [] + + + + letrec + drop match lambda (n, xs). case (n, xs) of + (0, _) then xs; + (_, []) then []; + (_, _ & xs') then drop (n-1, xs') + end + in drop + + What is the relation between `tail` and `drop`? + + let + tail xs = drop (1, xs) + in ... + + That uses [[the shorthand explained here|topics/week1_kapulet_advanced#funct-declarations]], which I will continue to use below. + +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 [10] + 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] + + + + letrec + take (n, xs) = case (n, xs) of + (0, _) then []; + (_, []) then []; + (_, x' & xs') then x' & take (n-1, xs') + end + in take + + +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 ([10], [20, 30]) + split (2, [10, 20, 30]) # evaluates to ([10, 20], [30]) + split (3, [10, 20, 30]) # evaluates to ([10, 20, 30], []) + split (4, [10, 20, 30]) # evaluates to ([10, 20, 30], []) + + + + letrec + split (n, xs) = case (n, xs) of + (0, _) then ([], xs); + (_, []) then ([], []); + (_, x' & xs') then let + (ys, zs) match split (n-1, xs') + in (x' & ys, zs) + end + in split + +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`. + + letrec + filter (p, xs) = case xs of + [] then []; + x' & xs' when p x' then x' & filter (p, xs'); + _ & xs' then filter (p, xs') + end + in filter + + The above solution uses [[pattern guards|/topics/week1_kapulet_advanced#guards]]. + + +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?, [11]) # evaluates to ([11], []) + partition (odd?, [12, 14]) # evaluates to ([], [12, 14]) + + + + letrec + partition (p, xs) = case xs of + [] then ([], []); + x' & xs' then let + (ys, zs) match partition (p, xs') + in if p x' then (x' & ys, zs) else (ys, x' & zs) + end + in partition + + +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. + + letrec + double xs = case xs of + [] then []; + x' & xs' then (2*x') & double xs' + end + in double + + +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: + + letrec + map match lambda (f, xs). case xs of + [] then []; + x' & xs' then (f x') & map (f, xs') + end; + 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] + + + + letrec + map2 (f, xs, ys) = case (xs, ys) of + ([], _) then []; + (_, []) then []; + (x' & xs', y' & ys') then (f x' y') & map2 (f, xs', ys') + end + in map2 + + +###Extra credit problems### + +* In class I mentioned a function `&&` which occupied the position *between* its arguments, rather than coming before them (this is called an "infix" function). The way that it works is that `[1, 2, 3] && [4, 5]` evaluates to `[1, 2, 3, 4, 5]`. Define this function, making use of `letrec` and the simpler infix operation `&`. + + letrec + xs && ys = case xs of + [] then ys; + x' & xs' then x' & (xs' && ys) + end + in (&&) + + This solution is using a variation of [[the shorthand explained here|topics/week1_kapulet_advanced#funct-declarations]]. We didn't expect you'd know how to deal with the special syntax of `&&`. You might have just defined this using a regular name, like `append`. + +* Write a function `unmap2` that is something like the inverse of `map2`. This function expects two arguments, the second being a sequence of elements of some type *t*. The first is a function `g` that expects a single argument of type *t* and returns a *pair* of results, rather than just one result. We want to collate these results, the first into one sequence, and the second into a different sequence. Then `unmap2` should return those two sequences. Thus if: + + g z1 # evaluates to (x1, y1) + g z2 # evaluates to (x2, y2) + g z3 # evaluates to (x3, y3) + + Then `unmap2 (g, [z1, z2, z3])` should evaluate to `([x1, x2, x3], [y1, y2, y3])`. + + letrec + unmap2 (g, zs) = case zs of + [] then ([], []); + z' & zs' then let + (x, y) match g z'; + (xs, ys) match unmap2 (g, zs') + in (x & xs, y & ys) + end + in unmap2 + +* Write a function `takewhile` that expects a `p` argument like `filter`, and also a sequence. The result should behave like this: + + takewhile ((lambda x. x < 10), [1, 2, 20, 4, 40]) # evaluates to [1, 2] + + Note that we stop "taking" once we reach `20`, even though there are still later elements in the sequence that are less than `10`. + + letrec + takewhile (p, xs) = case xs of + [] then []; + x' & xs' then if p x' then x' & takewhile (p, xs') + else [] + end + in takewhile + +* Write a function `dropwhile` that expects a `p` argument like `filter`, and also a sequence. The result should behave like this: + + dropwhile ((lambda x. x < 10), [1, 2, 20, 4, 40]) # evaluates to [20, 4, 40] + + Note that we stop "dropping" once we reach `20`, even though there are still later elements in the sequence that are less than `10`. + + letrec + dropwhile (p, xs) = case xs of + x' & xs' when p x' then dropwhile (p, xs'); + _ & _ then xs; + [] then [] + end + in dropwhile + + Unlike the previous solution, this one uses [[pattern guards|/topics/week1_kapulet_advanced#guards]], merely for variety. (In this solution the last two `case` clauses could also be replaced by the single clause `_ then xs`.) + +* Write a function `reverse` that returns the reverse of a sequence. Thus, `reverse [1, 2, 3, 4]` should evaluate to `[4, 3, 2, 1]`. + + letrec + aux (ys, xs) = case xs of + [] then ys; + x' & xs' then aux (x' & ys, xs') + end; + reverse xs = aux ([], xs) + in reverse + diff --git a/exercises/assignment2.mdwn b/exercises/assignment2.mdwn index 1fa69788..dff7cc23 100644 --- a/exercises/assignment2.mdwn +++ b/exercises/assignment2.mdwn @@ -127,13 +127,13 @@ Folds and Lists 21. Using Kapulet syntax, define `fold_left`. -22. Using Kapulet syntax, define `filter` (problem 7 in last week's homework) in terms of `fold_right` and other primitive syntax like `lambda`, `&`, and `[]`. Don't use `letrec`! +22. Using Kapulet syntax, define `filter` (problem 7 in last week's homework) in terms of `fold_right` and other primitive syntax like `lambda`, `&`, and `[]`. Don't use `letrec`! All the `letrec`-ing that happens should come from the one inside the definition of `fold_right`. -23. Using Kapulet syntax, define `&&` in terms of `fold_right`. (To avoid trickiness about the infix syntax, just call it `append`.) +23. Using Kapulet syntax, define `&&` in terms of `fold_right`. (To avoid trickiness about the infix syntax, just call it `append`.) As with problem 22 (the previous problem), don't use `letrec`! -24. Using Kapulet syntax, define `head` in terms of `fold_right`. When applied to a non-empty list, it should give us the first element of that list. When applied to an empty list, let's say it should give us `'err`. +24. Using Kapulet syntax, define `head` in terms of `fold_right`. When applied to a non-empty list, it should give us the first element of that list. When applied to an empty list, let's say it should give us `'err`. As with problem 22, don't use `letrec`! -25. We mentioned in the Encoding notes that `fold_left (flipped_cons, []) xs` would give us the elements of `xs` but in the reverse order. So that's how we can express `reverse` in terms of `fold_left`. How would you express `reverse` in terms of `fold_right`? +25. We mentioned in the Encoding notes that `fold_left (flipped_cons, []) xs` would give us the elements of `xs` but in the reverse order. So that's how we can express `reverse` in terms of `fold_left`. How would you express `reverse` in terms of `fold_right`? As with problem 22, don't use `letrec`! This problem does have an elegant and concise solution, but it may be hard for you to figure it out. We think it will a useful exercise for you to try, anyway. We'll give a [[hint|assignment2 hint]]. Don't look at the hint until you've gotten really worked up about the problem. Before that, it probably will just be baffling. If your mind has really gotten its talons into the problem, though, the hint might be just what you need to break it open. diff --git a/exercises/assignment3.mdwn b/exercises/assignment3.mdwn index d1cec2a9..e2fd9627 100644 --- a/exercises/assignment3.mdwn +++ b/exercises/assignment3.mdwn @@ -6,7 +6,7 @@ 2. What does `[ 10*x + y | y from [4], x from [1, 2, 3] ]` evalaute to? -3. Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. [[Here is a hint|assignment3 hints]], if you need it. +3. Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. [[Here is a hint|assignment3 hint1]], if you need it. ## Lists @@ -17,7 +17,7 @@ 6. Continuing to encode lists in terms of their left-folds, what should `last` be, where `last [a, b, c]` should result in `c`. Let `last []` result in whatever `err` is bound to. -7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. [[Here is a hint|assignment3 hints]], if you need it. +7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. [[Here is a solution|assignment3 hint2]], if you need help. ## Numbers diff --git a/exercises/assignment3_hint1.mdwn b/exercises/assignment3_hint1.mdwn new file mode 100644 index 00000000..c222c091 --- /dev/null +++ b/exercises/assignment3_hint1.mdwn @@ -0,0 +1,7 @@ +## Comprehensions + +3. Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. + +*Here is a hint* + +Define a function `dup (n, x)` that creates a list of *n* copies of `x`. Then use list comprehensions to transform `[3, 1, 0, 2]` into `[[3, 3, 3], [1], [], [2, 2]]`. Then use `join` to "flatten" the result. diff --git a/exercises/assignment3_hints.mdwn b/exercises/assignment3_hint2.mdwn similarity index 89% rename from exercises/assignment3_hints.mdwn rename to exercises/assignment3_hint2.mdwn index 86cda049..2efd11d2 100644 --- a/exercises/assignment3_hints.mdwn +++ b/exercises/assignment3_hint2.mdwn @@ -1,11 +1,3 @@ -## Comprehensions - -3. Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. - -*Here is a hint* - -Define a function `dup (n, x)` that creates a list of *n* copies of `x`. Then use list comprehensions to transform `[3, 1, 0, 2]` into `[[3, 3, 3], [1], [], [2, 2]]`. Then use `join` to "flatten" the result. - ## Lists 7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. diff --git a/index.mdwn b/index.mdwn index 470f703d..7b39b981 100644 --- a/index.mdwn +++ b/index.mdwn @@ -98,6 +98,7 @@ The [[differences between our made-up language and Scheme, OCaml, and Haskell|ro > Also, if you're reading the Hankin book, try reading Chapters 1-3. You will most likely need to come back again and read it multiple times; but this would be a good time to make the first attempt. +> We posted [[answers to Week 1's homework|exercises/assignment1_answers]].