add anchors
[lambda.git] / rosetta1.mdwn
1 [[!toc levels=2]]
2
3 More details are also available on these [[two|/rosetta2]] [[pages|/rosetta3]]. (But some information is only discussed below; the others aren't supersets of this page.)
4
5 ## Can you summarize the differences between your made-up language and Scheme, OCaml, and Haskell? ##
6
7 The made-up language we wet our toes in in week 1 is called Kapulet. (I'll tell you [the story behind its name](/images/randj.jpg) sometime.) The purpose of starting with this language is that it represents something of a center of gravity between Scheme, OCaml, and Haskell, and also lacks many of their idiosyncratic warts. One downside is that it's not yet implemented in a form that you can run on your computers. So for now, if you want to try out your code on a real mechanical evaluator, you'll need to use one of the other languages.
8
9 Also, if you want to read code written outside this seminar, or have others read your code, for these reasons too you'll need to make the shift over to one of the established languages.
10
11 We hope, though, that learning Kapulet first puts you in a position to make that shift more effortlessly, and also to more quickly see the places where there's underlying unity to Scheme, OCaml, and Haskell, despite their diverse syntaxes. (And idiosyncratic warts.)
12
13 This is a complex document. We don't expect that you will be learning all of these languages simultaneously. But you may find it helpful to read through the whole thing to get a broad overview, then consult it more carefully about the language you're focused on learning at any given point. You may also find it helpful to consult when confronting code you don't understand in one of the other languages. There are important parts of these languages that aren't covered here, especially parts concerning types and monads and continuations, that we will be discussing later in the seminar. We will add additional Rosetta pages for those later. If you master the ideas summarized here, however, you will have a good understanding of the basic skeleton of each of these languages.
14
15
16
17
18 ### Comments
19
20     ...  # this is a comment in Kapulet, that goes until the end of the line
21
22     ...  ; this is a comment in Scheme, that goes until the end of the line
23
24     ...  -- this is a comment in Haskell, that goes until the end of the line
25
26 Note that for Haskell's comments, the `--` must be immediately followed by something like a space or a letter. `-->` does not begin a comment; it's a legal operator symbol.
27
28 OCaml doesn't have comments of that sort. It only has "block" comments like this:
29
30     (* ... *)
31
32 which may last for several lines. These comments *nest*, so that:
33
34     (* ... (* inner *) ... *)
35
36 is a single comment.
37
38 Haskell also has block comments, though it `{- writes them differently -}`.
39 Haskell's block comments also nest.
40
41 Racket and Scheme also have block comments, though they `#| write them differently |#`.
42 These block comments also nest. Another form of block comments is `#;( ... )`. Those may contain nested parentheses, and extend until the next *matching* `)`. So prefixing `#;` to a complex parenthesized expression is a way to turn the whole thing into a comment. (These two comment styles only recently became part of the official Scheme standard, but they have been widely implemented.)
43
44
45
46
47 ### Variables
48
49 Our [[syntax for variables|topics/week1_kapulet_intro#variables]] in Kapulet is close to that in the other languages. Haskell and OCaml differ only in that they do not permit trailing `?` or `!`; however, they do permit trailing `'`s (and even permit `'`s *in the middle* of a variable too, which Kapulet does not). Scheme permits all of these characters, plus many more punctuation symbols as well, to occur anywhere in a variable. Scheme also permits variables to begin with capital letters, or to consist solely of the single character `_`; but the other languages reserve these terms for special purposes.
50
51 In addition to the variables made of letters (more properly, of alphanumerics), Haskell and OCaml and Kapulet also permit some variables made exclusively of punctuation symbols, like `<` or Haskell's `>=>` and `<$>`. In Haskell, these always have infix syntax, and the variables made of letters never do. (But the former can have their infix syntax suppressed with parentheses, and the latter can be "flagged" to temporarily take on infix syntax, as we'll discuss below.)
52
53 In OCaml and Kapulet, some variables made of letters also have infix syntax, such as `comp` in Kapulet or `mod` in OCaml. I haven't presented to you the complex mechanisms needed to declare this.
54
55
56
57
58 ### Equality and Booleans
59
60 The relation that's written `==` in Kapulet is also written that way in Haskell. That symbol means something else in OCaml, having to do with mutable reference cells; to get the same notion in OCaml one writes just a single `=`. The negation of this relation is written `!=` in Kapulet, `/=` in Haskell, and `<>` in OCaml. (Again, `!=` means something else in OCaml.)
61
62 These comparison operators are "polymorphic". This is a notion we'll discuss later when we get to types, but in the present context it means that you can apply `==` to two numbers, or to two booleans, and so on. In Kapulet, OCaml, and Haskell, however, you cannot apply that comparison to a number and a boolean at the same time. That will fail as a type error, instead of evaluating to `'false`.
63
64 Also, these languages (and Scheme too) behave in idiosyncratic ways if you try to compare two function values for equality. The equivalence of function values is not in general recursively decidable; it may be possible in some specific cases to give you a definite yes-or-no answer, but you'll have to look up the specific rules for (each implementation of) each language. I recommend that you in general just avoid comparing function values for equality.
65
66 Scheme has a whole bunch of equality functions. First, there are functions restricted to specific kinds of values: `=` for numbers, `symbol=?` for symbolic atoms, `boolean=?` for booleans (this is more familiar to us as "iff"), and so on. Those functions fail if called with arguments that aren't of the expected types. Scheme also has a couple of unrestricted equality functions, which can take arguments of any type, and the arguments need not even be of the same type (but if they're not, they'll always be counted as unequal). The two most fundamental of these are `eqv?` and `equal?`. They behave the same for numbers (at least, for "exact" numbers like integers), for symbols, for booleans, and the like. As we'll discuss [[below|rosetta1#mlists]], containers in Scheme (lists, pairs, vectors, strings) are generally "mutable", so there's a choice when comparing two such containers whether we're asking if the containers merely *happen now to contain corresponding values* (including, if their elements are themselves containers, they too containing corresponding values). Or whether we're asking if the containers *occupy the same mutable location in memory*, so that it'd be impossible for them to become unequal at any stage in the program's evaluation. The first comparison is expressed by `equal?`; the second by `eqv?`. (You may also see Scheme programs that use the predicate `eq?`. This is a variant of `eqv?` that may sometimes be more efficient.)
67
68 The relations that are written `and`, `or`, and `not` in Kapulet are written the same way in Scheme. Note that in Scheme the first two can take zero or more arguments:
69
70     ; Scheme
71     (and)
72     (and bool1)
73     (and bool1 bool2)
74     (and bool1 bool2 bool3)
75
76 As you'd expect `(and bool1)` evaluates the same as plain `bool1`; similarly with `(or bool1)`. What do you think `(and)` with no arguments should evaluate to? How about `(or)`?
77
78 These relations are written in Haskell and OCaml as `&&`, `||`, and `not`. (Haskell uses `and` and `or` to express other functions, which compute the joint conjunction or disjunction of every `Bool` value in a List of such. OCaml permits `or` as an old synonym for `||`, but discourages using that spelling. OCaml also permits `&` as an old, discouraged synonym for `&&`.)
79
80 The values that are written `'true` and `'false` in Kapulet are written in Haskell as `True` and `False`, and in OCaml as just `true` and `false`. (It'd be more consistent with OCaml's other naming policies for them to have said True and False<!-- other value constructors must be capitalized -->, but they didn't.) These are written `#t` and `#f` in Scheme, but in Scheme in many contexts any value that isn't `#f` will behave as though it were `#t`, even values you might think are more "false-like", like `0` and the empty list.
81 <a id=truth-like></a> Thus `(if 0 'zero 'nope)` will evaluate to `'zero`.
82
83 Some Scheme implementations, such as Racket, permit `#true` and `#false` as synonyms for `#t` and `#f`. (These aliases are also mandated in "version 7", r7rs, of the Scheme standard.)
84
85 Scheme also recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "truth-like" value, like all of its other values that aren't `#f`. Kapulet essentially took Scheme's `boolean` values and collapsed them into being a subtype of its `symbol` values.
86 <!-- This is also what it does with Scheme's `char`s ?? see [[below|rosetta1#chars]] -->
87
88
89
90
91 ### Infix operators and parentheses
92
93
94 Kapulet, OCaml, and Haskell all understand some expressions like `+` to be infix operators. So you would write:
95
96     1 + 2
97
98 not:
99
100     + 1 2
101
102 <a id=pre-curried></a>
103 But all three of these languages permits you to enclose an infix operator in parentheses to make a *section*, which no longer has infix syntax. In Kapulet, `( + )` is the same as &lambda; `(x, y). x + y`, whereas in OCaml and Haskell it's a *curried* function, which we can write (in Kapulet syntax) as &lambda; `x y. x + y`. We'll discuss [[sections|rosetta1#sections]] and [[curried functions|rosetta1#curried]] below.
104
105 Kapulet and OCaml have some variables made of (or spelled with) letters also taking infix syntax, such as `comp` in Kapulet or `mod` in OCaml. In Haskell, this is never the case: variables that are made of letters are only treated as function terms being applied to arguments *when they're at the start* of a list of expressions; and variables that are made of punctuation symbols, and not enclosed in parentheses, will only be treated as infix operators. However, Haskell permits you to temporarily "flag" a  function term made of letters to behave like an infix operator, by enclosing it in `` ` `` marks. Thus in Haskell you can write:
106
107     3 `mod` 2
108
109 But without the `` ` ``, you'd have to write: `mod 3 2`.
110
111 Scheme has no infix operators. It ruthlessly demands that all functions to be applied to arguments come at the start of a list of expressions, regardless of whether the functions are specified by variables made of letters, punctuation symbols, or a mix of the two, or even if the functions are computed by evaluating more complex expressions. Thus in Scheme one always writes:
112
113     (+ 3 2)
114
115 and the like. Here is an example where the function to be applied is the result of evaluating a more complex expression:
116
117     ((if #t + *) 3 2)
118
119 which will evaluate to `5`, not `6`.
120
121 In Scheme the parentheses are never optional and never redundant. In expressions like `(+ 3 2)`, the parentheses are necessary to express that the function is being applied; `+ 3 2` on its own is not a complete Scheme expression. And if the `+` were surrounded by its own parentheses, as in:
122
123     ((+) 3 2)
124
125 what that would mean is that `+` is first being applied to *zero* arguments, which is different from not applying it all. (In Kapulet, OCaml, and Haskell, one would write that `f` is being applied to "zero arguments" like this: `f ()`; see [[below|rosetta1#void]]. We will discuss functions that "take zero arguments" a few weeks into the seminar.) Scheme helpfully defines the result of applying `+` to zero arguments to be `0`. So `((+) 3 2)` would evaluate to whatever `(0 3 2)` does, and that's an error, because `0` is not a function.
126
127 Note that `(0 3 2)`, although it *is*, qua expression, a list of numbers, does not evaluate to a list. To get an expression that *evaluates to* that list, you'd have to use `(list 0 3 2)` or `'(0 3 2)`. (Notice the initial `'`.) More on this [[below|rosetta1#writing-scheme-lists]].
128
129 In Scheme, you can also write `(+ 3 2 10)`, and so on. You only have to write `(+ (+ 3 2) 10)` if you really want to.
130
131 Parentheses have many other roles in Scheme, too; they're a ubiquitous part of the syntax, and don't always express function application. You might sometimes feel they are overused.
132
133 You may sometimes see `[ ... ]` being used in Scheme, instead of `( ... )`. This is just a stylistic variant; they work exactly the same. The official Scheme standard doesn't permit this usage, but most Scheme implementations do. It can help keep track of which closing `]` or `)` goes with which opening `[` or `(`. The opening and closing symbols always have to correspond.
134
135 <a id=curried></a>
136 In Scheme, the default style for defining functions is as taking several arguments simultaneously, that is the *uncurried* style. In OCaml and Haskell, the default style is to define them *curried*. Curried functions can easily be partially applied:
137
138     (* OCaml *)
139     let add  = fun x y -> x + y in
140     let add2 = add 2 in
141         add2 3
142     ;;
143
144 will result in `5`.
145
146 In Scheme, the common idiom would be to define `add` like this:
147
148     (define add (lambda (x y) (+ x y)))
149
150 (We'll explain `define` [[below|rosetta1#define]].) After this, you cannot say `(add 2)`, because `add` will be expecting two arguments, but you only supplied one. You can however define curried functions in Scheme, it's just more laborious:
151
152     (define curried_add (lambda (x) (lambda (y) (+ x y))))
153     (define add2 (curried_add 2))
154     (add2 3)
155
156 will result in `5`. This is the best one can do in official Scheme, but there are various syntax extensions and macros out there to make it possible to write this sort of thing more succinctly.
157
158 OCaml and Haskell also permit defining functions in uncurried form:
159
160     (* OCaml *)
161     let add  = fun (x, y) -> x + y (* uncurried*) in
162     let add2 = add 2 in ...
163
164 Here the last displayed line will fail, because `add` expects as its argument a tuple of two numbers.
165
166 Kapulet essentially works like OCaml and Haskell; though for pedagogical reasons we started out by introducing uncurried definitions, rather than the *curried* definitions those other languages predominantly use.
167
168 Here are some interesting functions we can define in Kapulet. See [[below|rosetta1#curried-patterns]] for the pattern syntax used here.
169
170     # Kapulet
171     let
172       curry   match lambda f. lambda  x  y.  f (x, y);
173       uncurry match lambda g. lambda (x, y). g  x  y ;
174       uncurried_flip match lambda f. lambda (y, x). f (x, y)
175       curried_flip   match lambda g. lambda  y  x.  g  x  y;
176     in ...
177
178 The function `curry` takes as an argument a function `f` that expects its arguments *uncurried*, and returns instead `lambda x y. f (x, y)`, a function that expects its arguments *curried* --- but then does with them whatever `f` does. Going in the other direction, the function `uncurry` takes a function `g` that expects its arguments *curried*, and returns instead a function that expects its arguments *uncurried* --- but then does with them whatever `g` does.
179
180 The function `uncurried_flip` takes as an argument again an uncurried function `f`, and returns another function that also expects its arguments uncurried, but that expects them in the other order. `curried_flip` transforms a curried function `g` in the analogous way. These are both different from the function `swap` we defined in the [[course notes|topics/week1_kapulet_advanced#functions]] as:
181
182     lambda (x, y) = (y, x)
183
184 *That* function operates on a tuple and returns another tuple. The `..._flip` functions operate on functions, and transform them into other functions that expect their arguments in a different order.
185
186
187 <a id=sections></a>
188 [[As we mentioned in the course notes|topics/week1_kapulet_advanced#sections]], in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
189
190     # Kapulet
191     let
192       ten_minus match lambda x. 10 - x;
193       and_ys    match lambda x. x & ys;
194       plus      match lambda (x, y). x + y
195     in (ten_minus, and_ys)
196
197 like this:
198
199     # Kapulet
200     let
201       ten_minus match (10 - );
202       and_ys    match ( & ys);
203       plus      match ( + )
204     in (ten_minus, and_ys)
205
206 There are just minor differences between these languages. First, OCaml doesn't have the `( + 10)` or `(10 + )` forms, but only the `( + )`.
207
208 Second, as a special case, OCaml doesn't permit you to do this with its list cons-ing operator `::`. You have to write `fun x xs -> x :: xs`, not `( :: )`. <!-- Syntax error -->
209 Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its sequence cons-ing operator `&`; and in Haskell, `( : )`, `(x : )`, and `( : xs)` are the same.
210
211 Third, as [[mentioned above|rosetta1#pre-curried]], OCaml's and Haskell's `( + )` and the like evaluate to *curried* functions.
212
213 Fourth, in Kapulet, `( - 10)` expresses &lambda; `x. x - 10` (consistently with `(10 - )`), but Haskell (and OCaml) treat this specific form differently, and interpret it as meaning the integer `-10`. Here's how to express some things in Kapulet:
214
215     # Kapulet
216     (0 - 2)
217     ( - 2)         # ( - 2) 10 == 8
218     (0 - )
219     ( - ) (5, 3)
220
221
222 and here are their translations into natural Haskell:
223
224     -- Haskell
225     ( -2 )        -- (0 - 2) also works
226     (subtract 2)  -- subtract 2 10 == 8
227     negate        -- (0 - ) also works
228     ( - ) 5 3
229
230 OCaml expresses `(0 - )` or `negate` as `~-`. You can write `3 * (0 - 2)` in OCaml either like that, or as `3 * ( -2 )`, or as `3 * ~-2`.
231
232 I know all these languages fairly well, and I still find this fourth issue difficult to keep track of. You may be starting to understand why I spoke of "warts."
233
234
235
236
237 ### Sequences and Lists
238
239 In Kapulet, we have a notion I called a "sequence" which has an empty form `[]` and a cons-ing operator `&`, so that:
240
241     1 & 2 & 3 & []
242
243 can also be written:
244
245     [1, 2, 3]
246
247 Haskell is very similar, except that it calls these Lists, and its cons-ing operator is written `:`. OCaml also calls them `list`s, and its cons-operator is written `::`. (OCaml *also* uses Haskell's symbol `:`, but it uses it to deal with types; and Haskell in turn also uses OCaml's symbol `::`, but that's what *it* uses to deal with types. Grr.)
248
249 Kapulet writes the operator that concatenates or appends sequences as `&&`. Thus:
250
251     # Kapulet
252     [1, 2] && [3, 4, 5]
253
254 evaluates to `[1, 2, 3, 4, 5]`. Haskell writes this operator as `++`. In Haskell, a `String` is just a List of `Char`, so `++` is also the operator we use to append strings:
255
256     -- Haskell
257     "over" ++ "due"
258
259 evaluates to `"overdue"`. In OCaml, `string`s aren't implemented as `list`s, so their append operators are different: `^` for `string`s and `@` for `list`s:
260
261     (* OCaml *)
262     [1; 2] @ [3; 4; 5] ;;
263     "over" ^ "due" ;;
264
265 evaluate to `[1; 2; 3; 4; 5]` and `"overdue"`. Note that OCaml separates its `list` elements with semicolons not commas. If you write `[1, 2, 3]` in OCaml, it will think that's a one-element list whose first element is a triple, that is, what you'd write in Haskell as `[(1, 2, 3)]`.
266
267 Here are some list functions in Kapulet:
268
269     length
270     (&&)
271     # the following were defined in homework
272     empty?       # can also use ([] == ) or pattern-match against []
273     tail
274     drop
275     take
276     split
277     filter
278     partition
279     map
280     map2
281     # the following were defined in extra credit
282     unmap2
283     takewhile
284     dropwhile
285     reverse
286     # new functions
287     join         # converts [[10, 20], [30], [], [40, 50]]
288                  # to [10, 20, 30, 40, 50] (but only "joining" a single layer of []s)
289     (mem)        # infix syntax, 2 mem [1, 2, 3] == 'true
290     nth          # nth [10, 20, 30] 1 == 20, because 10 occupies position 0
291                  # fails if the index is out of bounds
292     all p xs     # all odd? [1, 3, 5] == 'true
293     any p xs     # any even? [1, 3, 5] == 'false
294
295
296
297 Here are the corresponding functions in Haskell:
298
299     length
300     (++)
301     null     -- can also use ([] == ) or pattern-match against []
302     tail     -- compare head, which fails on []
303     drop     {- but these are curried functions, so you write `drop n xs`
304                 not `drop (n, xs)` as in Kapulet -}
305     take
306     splitAt
307     filter
308     Data.List.partition
309     map
310     zipWith  {- zip handles the special case of zipWith where f is the function that forms ordered pairs
311                 both zipWith and zip stop with the shortest list -}
312     unzip    {- unlike unmap2, doesn't take an explicit f argument
313                 just assumes it's (\(x, y) -> (x, y)) -}
314     takeWhile
315     dropWhile
316     reverse
317     concat   -- corresponding to join
318     elem     -- not infix syntax, but often written as: 2 `elem` [1, 2, 3]
319     (!!)     -- infix syntax: [10, 20, 30] !! 1 == 20
320              -- fails if the index is out of bounds
321     all p xs
322     any p xs
323
324
325
326 Here they are in OCaml:
327
328     List.length
329     (@)          (* or List.append *)
330     (* no function predefined for empty?
331        can use fun xs -> [] == xs, or function [] -> true | _ -> false *)
332     List.tl      (* compare List.hd, which fails on [] *)
333     (* no function predefined for drop or take *)
334     (* no function predefined for split; OCaml uses List.split to mean something else *)
335     List.filter  (* also List.find_all *)
336     List.partition
337     List.map
338     List.map2    (* compare List.combine, like Haskell's zip
339                     both map2 and combine fail if the lists are different lengths *)
340     List.split   (* like Haskell's unzip, doesn't take an f argument *)
341     (* no function predefined for takewhile or dropwhile *)
342     List.rev
343     List.concat  (* also List.flatten, which still only "joins" a single layer of []s *)
344     List.mem     (* not infix syntax *)
345     List.nth     (* List.nth [10; 20; 30] 1 = 20; fails if the index is out of bounds *)
346     List.for_all p xs
347     List.exists p xs
348
349 Recall that in addition to sequences/lists, Kapulet also has a notion of *sets*, which can be literally expressed using notation like this:
350
351     {'x, x}
352
353 That set contains the atomic symbol `'x`, and whatever symbol value the variable `x` is bound to (which need not, but may, be the symbol `'x`). Or:
354
355     {1, 2, x}
356
357 That set contains the numbers `1` and `2`, and whatever number the variable `x` is bound to. Sets in Kapulet, like sequences, must have elements of all the same type.
358
359 OCaml and Haskell also have set values (in the `Set` and `Data.Set` libraries, respectively), but these are harder to use and can't be literally expressed. In particular, the `{ ... }` notation in these languages has different meanings. <!-- In addition to Haskell block syntax, also expressed *records* in both languages, which roughly correspond to multivalues-with-keys in Kapulet. -->
360
361
362
363
364 <a id=scheme-lists></a>
365 How does all this look in Scheme? Well, Scheme has a notion they call a (proper) `list`, and also a notion they call a `vector`. There are also what Scheme calls "improper" `list`s, with `(cons 1 'nonlist)` or `'(1 . nonlist)`, where `'nonlist` is any non-list (here it's a `symbol`) being a limiting case. Let's ignore the improper `list`s. Scheme's (proper) `list`s and `vector`s each have a claim to correspond to Kapulet's sequences / Haskell's Lists / OCaml's `list`s. But they also differ from those. The main differences are:
366
367 <a id=mlists></a>
368
369 1.  these structures in Scheme can contain heterogenously-typed elements, including further `list`s and `vector`s in some positions but not in others
370 2.  in the official Scheme standard, `list`s and `vector`s are both *mutable* containers, that is, one and the same persisting `list` structure can have different
371 elements at different stages in a program's evaluation
372
373 Many Scheme implementations also provide immutable versions of `list`s and `vector`s, more closely approximating the sequences/lists in Kapulet, Haskell, and OCaml. With some configurations, Racket even makes the immutable versions the defaults. But none of these are yet part of the official Scheme standard. Also, difference 1 is present in all Scheme implementations. This makes Scheme's `list`s and `vector`s in some ways more akin to *tuples* in the other languages (to "proper" tuples in Kapulet) (see [[below|rosetta1#tuples]]).
374
375 (OCaml does have `Array` values, and Haskell has `Data.Array.MArray` values, both of which are similar to Scheme's mutable `vector`s, at least in respect 2. But they are more difficult to use.)
376
377 <a id=writing-scheme-lists></a>
378 There are also some differences in how `list`s are specified in Scheme versus the other languages. In Scheme, one writes the empty list like this:
379
380     (list)
381
382 and lists with more elements like this:
383
384     (list 10)
385     (list 10 x)
386     (list 10 x 'alpha)
387     (list 10 x 'alpha (list 'beta 'gamma) 'delta 20)
388
389 In the preceding, the `x` is a variable and is evaluated to be whatever value it's bound to in the context where the displayed expressions are being evaluated. If one has a list specification that contains no variables, no matter how deeply embedded, then a certain shorthand becomes available, using a `'` prefix, like this:
390
391     '()                          ; same as (list)
392     '(10)                        ; same as (list 10)
393     '(10 alpha)                  ; same as (list 10 'alpha)
394     '(10 alpha (beta gamma) 20)  ; same as (list 10 'alpha (list 'beta 'gamma) 20)
395
396 Scheme can also write <code>'<em>something</em></code> as <code>(quote <em>something</em>)</code>. (The `quote` is not a function being applied to some argument; this is a special syntax that only superficially *looks* like a function application.)
397
398
399 Here are the `list` functions in Scheme corresponding to the functions listed in the other languages:
400
401     cons              ; corresponds to Kapulet's ( & ), Haskell's ( : ), OCaml's `::`
402     length
403     append            ; corresponds to Kapulet's ( && ), Haskell's ( ++ ), OCaml's ( @ )
404                       ; can be applied to one or more arguments
405     null?             ; corresponds to Kapulet's empty?, Haskell's null
406     car               ; corresponds to Haskell's head
407     cdr               ; corresponds to Kapulet's and Haskell's tail
408     (list-tail xs k)  ; corresponds to Kapulet's drop (k, xs)
409                       ; fails if the list has length < k
410     ; no official function predefined for take or split or filter or partition
411     map               ; corresponds to Kapulet's map and map2
412                       ; can take one or more list arguments
413     ; no official function predefined for unmap2 or takewhile or dropwhile
414     reverse
415     ; no official function prefefined for join/concat
416     memv, member      ; correspond to Kapulet's (mem) and Haskell's elem
417                       ; memv compares elements using eqv?, member using equal?
418     (list-ref xs k)   ; corresponds to Kapulet's `nth xs k`
419                       ; fails if the index k is out of bounds
420     ; no official function predefined for all or any
421
422 <!-- memv, member return the first tail headed by the matching element, or #f -->
423
424 All of the functions listed as missing from the official Scheme standard can be found in various add-on libraries, or you could define them yourself if you had to.
425 <!-- TODO Scheme extra list functions -->
426
427
428
429 <a id=tuples></a>
430 ### Tuples
431
432 The course notes [[already mentioned|topics/week1_kapulet_intro#lightweight]] that Kapulet has a "lightweight" notion of tuples, called multivalues and written `(10, x)`, as well as a heavier notion written `Pair (10, x)`. The latter is what corresponds to the tuples in Haskell and OCaml. They don't have any explicit notation for Kapulet's "lightweight" tuples (though they exist behind the scenes in OCaml and explain some of its otherwise puzzling behavior). There are good reasons for introducing this additional complexity in Kapulet, but this is not the place to explain them.
433
434 All of these languages have notions of zero-length tuples, as well as pairs, triples, and the like. (In Kapulet's case, there are both the 0-length multivalue `()` and heavier counterparts.)
435
436 Probably the closest approximation to tuples in Scheme is its notion of `vector`s, though in the case of pairs, Scheme's `pair`s---which it identifies with short, possibly "improper" `list`s---are arguably also contenders. The fact that these Scheme structures permit elements of heterogenous type is not a problem, because that is also true for tuples in the other languages. However, Scheme's `vector`s and `pair`s are officially mutable, but tuples in the other languages are not. (As mentioned above, many Scheme implementations do also provide immutable versions of these structures.)
437
438 <a id=void></a>
439 What corresponds to the zero-length tuples in Kapulet, OCaml, and Haskell? Perhaps the zero-length `vector`. Or perhaps a different Scheme value, called *void*. Different Scheme implementations display this value in different ways. For example, Racket and Chicken may display it as `#<void>` or as `#<unspecified>` or may just display nothing. This is the value returned, for example, by a `case` or a `cond` construction if there is no `else` clause and none of the provided clauses successfully match. In many respects, this value more closely approximates in Scheme the behavior that `()` has in Kapulet, OCaml, and Haskell.
440
441
442
443
444 <a id=chars></a>
445 ### Chars and Strings
446
447 Scheme, OCaml, and Haskell all have values they call "characters", and sequences of such characters they call "strings". Haskell and OCaml write the first character of the word "false" like this:
448
449     'f'
450
451 whereas Scheme writes it like this:
452
453     #\f
454
455 (Note the difference between the *character* `#\f` and the *boolean* `#f`.) Scheme gives special characters like `#\space` funny names.
456
457 Sequences of characters are called "strings". All of these languages write the string "false" like this:
458
459     "false"
460
461 This is not the same as the truth-value, nor is it the same as the atomic symbol `'false` (which Kapulet but not Scheme identifies with the truth-value). In Haskell, strings are strictly equivalent to Lists of `Char`s. In OCaml and Scheme, they are not equivalent to lists (nor to vectors) but merely isomorphic to them. In OCaml and Scheme, some strings are mutable, like Scheme's vectors.
462
463
464
465
466 ### Other functions
467
468 These functions are roughly the same in Kapulet, OCaml, and Haskell: `succ`, `pred`, `fst`, `snd`. The official Scheme standard doesn't include any `succ` or `pred` functions, but Racket and Chicken both have `add1` and `sub1`. Depending on what Scheme values you take to correspond to tuples in the other languages, `fst` and `snd` may correspond to Scheme's `car` and `cdr`. (These also correspond to `head` and `tail` when applied to lists.)
469
470 Kapulet's `(comp)`, `odd?`, `even?`, and `swap` are Haskell's `( . )`, `odd`, `even`, and `Data.Tuple.swap`. None of these are predefined in OCaml.
471
472 Kapulet's `dup` isn't predefined in Haskell but can be easily expressed as `\x -> (x, x)`.
473
474 These are the same in Kapulet and Haskell (modulo the differences between [[Kapulet's multivalues|topics/week1_kapulet_intro#lightweight]] or "lightweight tuples" and Haskell's tuples): `id`, `const`, `curry`, `uncurry`. Kapulet's `curried_flip` is Haskell's `flip`.  None of these are predefined in OCaml.
475
476 Kapulet and Haskell both have `( $ )`, which was explained [[in the course notes|topics/week1_kapulet_advanced#dollar]]. OCaml expresses this as `( @@ )`. (OCaml also uses `|>` to express the converse operation: `f x`, `f @@ x` and `x |> f` all mean the same.)
477
478
479
480
481 ### Case, Cond, and If ... then ...
482
483 The complex expression that's written like this in Kapulet:
484
485     # Kapulet
486     case some_expression of
487       0 then result0;
488       1 then result1;
489       x then resultx
490     end
491
492 is written very similarly in Haskell:
493
494     -- Haskell
495     case some_expression of {
496       0 -> result0;
497       1 -> result1;
498       x -> resultx
499     }
500
501 <a id=haskell-whitespace></a>
502 Unlike the other languages we're discussing, Haskell pays special attention to the whitespace/indentation of what you write. If you've got the indentation right, you can omit the `{`, `;`, and `}`s in the above. And that's how you will often see Haskell code displayed. On this website, though, I propose to always include the `{`s and so on when displaying Haskell code, because the indentation rules aren't 100% intuitive. It's easy to read properly-indented Haskell code, but until you've learned and practiced the specific rules, it's not always easy to write it.
503
504 <!-- In OCaml, separating expressions with `;` has a different meaning, concerning the sequencing of effects. To bracket a block of code in the way Haskell does with `{...; ...}`, in OCaml you'd use parentheses or `begin ... end`. -->
505
506 The `case` construction is written only a little bit differently in OCaml:
507
508     (* OCaml *)
509     match some_expression with
510       0 -> result0 |
511       1 -> result1 |
512       x -> resultx
513
514 Note there is no closing `end` or `}`. You can enclose the whole expression in parentheses if you want to, and when embedding it in some larger expressions (like another `match` expression), you may need to. Sometimes the `|` dividers are written at the start of a line, and you are allowed to include an extra one before the first line, so you could also see this written as:
515
516     (* OCaml *)
517     match some_expression with
518       | 0 -> result0
519       | 1 -> result1
520       | x -> resultx
521
522 <a id=as-patterns></a>
523 The syntax for [[guards|topics/week1_kapulet_advanced#guards]] and [[as-patterns|topics/week1_kapulet_advanced#as-patterns]] also only varies slightly between these languages:
524
525     # Kapulet
526     case some_expression of
527       pat1   when guard             then result1;
528       pat1   when different_guard   then result2;
529       ((complex_pat) as var, pat4)  then result3
530     end
531
532 <a id=haskell-guards></a>
533
534     -- Haskell
535     case some_expression of {
536       pat1 | guard              -> result1;
537            | different_guard    -> result2;
538       (var@(complex_pat), pat4) -> result3
539     }
540
541     (* OCaml *)
542     match some_expression with
543       pat1   when guard             -> result1 |
544       pat1   when different_guard   -> result2 |
545       ((complex_pat) as var, pat4   -> result3
546
547
548 The official Scheme standard only provides for a limited version of this. There is a `case` construction, available since at least "version 5" of the Scheme standard (r5rs), but it only accepts literal values as patterns, not any complex patterns containing them or any patterns containing variables. Here is how it looks:
549
550     ; Scheme
551     (case some_expression
552       ((0) 'result0)
553       ((1) 'result1)
554       ((2 3 5) 'smallprime)
555       (else 'toobig))
556
557 The results can be complex expressions; I just used bare symbols here for illustration. Note that the literal patterns in the first two clauses are surrounded by an extra pair of parentheses than you might expect. The reason is shown in the third clause, which begins `(2 3 5)`. This does not mean to match a list containing the values `2` `3` and `5`. Instead it means to match the simple value `2` *or* the simple value `3` *or* the simple value `5`. The final `else` clause is optional. If it's omitted, and none of the other clauses match, the result is Scheme's [[special void value|rosetta1#void]].
558
559 The patterns here can be any literal value (what the Scheme standards call a "datum"). Numbers are permitted, as are boolean literals (`#t` and `#f`) and symbolic atoms (`'alpha` and the like, though inside a pattern position in a `case` construction, you omit the initial `'`). You can also use the list literal `'()` (again, omit the initial `'` when writing it as a pattern). Some implementations of Scheme allow more complex list patterns, matching literal lists like `'(alpha 0 () #t)`; others don't.
560
561 There are various add-on libraries to Scheme that will permit you to pattern-match in more ambitious ways, approximating what you can do in Kapulet, OCaml, and Haskell. We will explain some of these later in the course, after we've introduced you to the notion of *datatypes*.
562
563 What programmers using standard Scheme tend to do instead is to use *predicates* that query the type and/or structure of an unknown value, and then take separate evaluation paths depending on the result. This can be done with an `if ... then ... else ...` construction, or with Scheme's more general `cond` construction. In Scheme, these two are equivalent:
564
565     ; Scheme
566     (if test1 'result1                    ; else what follows:
567               (if test2 'result2          ; else what follows:
568                         (if test3 'result3 'somethingelse)))
569
570     (cond
571       (test1 'result1)
572       (test2 'result2)
573       (test3 'result3)
574       (else  'somethingelse))
575
576 The tests tend to use predicates like `null?` (are you the empty list?), `pair?` (are you a non-empty list, whether proper or improper?), `list?` (are you a proper list, whether empty or not?), `symbol?`, `boolean?`, `number?`, `zero?` (you get the idea). The *Little Schemer* books use their own predicates they call `atom?` (are you a non-list?) and `lat?` (are you a list all of whose members are atoms?) <!-- They seem to only use `symbol`s, `number`s, and `boolean`s as atoms. -->
577
578 You can also use more complex tests you write on the spot, or your own antecedently-defined functions:
579
580     ; Scheme...in case the parens left any doubt
581     (define smallprime? (lambda (x) (if (= x 2) #t (if (= x 3) #t (if (= x 5) #t #f)))))
582
583     (cond
584       ((= x 0) 'infant)
585       ((smallprime? x) 'myfavorite)
586       ((and (> x 10) (< x 20)) 'teenaged)
587       (else 'unknown))
588
589 Remember that in Scheme, an expression doesn't have to evaluate to `#t` to be treated as "truth-like". *Every* value other than `#f` is treated as truth-like. As I [[said before|rosetta1#truth-like]] `(if 0 'zero 'nope)` evaluates to `'zero`.
590
591 You may sometimes see Scheme `cond` constructions written with this kind of clause:
592
593     (cond
594       ...
595       (test-expression => function-value)
596       ...)
597
598 That's the same as the following:
599
600     (cond
601       ...
602       (test-expression (function-value test-expression))
603       ...)
604
605 Except that it only evaluates the test-expression once.
606
607 The clauses in Scheme's `cond` expressions can contain *multiple* expressions after the test. This only becomes useful when you're working with mutable values and side-effects, which we've not gotten to yet. The `if` expressions only take a single expression for the "then" branch and a single expression for the "else" branch. You can turn a complex series of expressions, which may involve side-effects, into a single expression by wrapping it in a `(begin ...)` construction. The `(begin ...)` construction as a whole evaluates to whatever the last expression it contains does.
608
609 Scheme standards after r5rs also provide two further conditional constructions, which are for the situations where you want to perform a meaningful action only on the "then" branch, or only on the "else" branch:
610
611     (when test-expression
612        result-expression1...)
613
614     (unless test-expression
615        result-expression2...)
616
617 If the test-expression evaluates to `#f`, then the `when` expression evaluates to Scheme's [[special void value|rosetta1#void]]; mutatis mutandis for the `unless` expression. This is analogous to `()` in OCaml, Haskell, and Kapulet.
618
619 In the last three languages, the expressions in the then-branch and the else-branch of a conditional have to have the same type. You can't say `if test-expression then 0 else []`. Also, they expect the test-expression to evaluate specifically to a boolean value, not merely to `'false` versus "anything else". They are stricter about types here than Scheme is.
620
621 In the special case where an else-branch evaluate to `()` (and thus so too must the then-branch), and the else-branch does so using no complex expression but merely the literal `()`, then OCaml permits you to omit that else-branch. So in OCaml you can write this:
622
623      if test_expression then then_result
624
625 instead of
626
627      if test_expression then then_result else ()
628
629 This is similar to Scheme's `when` construction. Kapulet and Haskell have no analogue.
630
631
632
633
634 ### Lambda expressions
635
636 <a id=curried-patterns></a>
637 In Kapulet you write &lambda; expressions (sometimes called "anonymous functions") with a prefix of either &lambda; or the spelled-out `lambda`. That's followed by one or more patterns, separated by spaces, then a period, then a single expression which makes up the body of the function. When there are multiple patterns, the function expressed is *curried*, thus:
638
639     lambda (x, y) z. result
640
641 means the same as:
642
643     lambda (x, y). (lambda z. result)
644
645 The parentheses could have been omitted around `lambda z. result`; they're just there to focus your attention.
646
647 Haskell and OCaml are very similar to this, they just use some slightly different notation. In Haskell you'd write:
648
649     -- Haskell
650     \(x, y) z -> result
651
652 and in OCaml you'd write:
653
654     (* OCaml *)
655     fun (x, y) z -> result
656
657 You may sometimes see &lambda; expressions in OCaml written using `function` instead of `fun`. These overlap somewhat in their usage. The difference is that `function` only allocates a position for *one* argument pattern, so can't straightforwardly define curried functions. (You can however embed `function` expressions inside other `function` expressions.) On the other hand, `function` can take multiple *variant* patterns for that single position. Thus with `function` you can say:
658
659     (* OCaml *)
660     function []    -> result1 |
661              x::xs -> result2
662
663 whereas with `fun` you'd have to write:
664
665     (* OCaml *)
666     fun ys -> match ys with
667                 []    -> result1 |
668                 x::xs -> result2
669
670 In Scheme, lambda expressions are written like this:
671
672     ; Scheme
673     (lambda (vars...) body-expressions...)
674
675 Scheme only permits simple variables as its argument patterns, and the lambda expression can be defined to take zero or more arguments:
676
677     ; Scheme
678     (lambda () ...)
679     (lambda (x) ...)
680     (lambda (x y) ...)
681     (lambda (x y z) ...)
682
683 As I said before, we will discuss functions that "take zero arguments" a few weeks into the seminar.
684
685 There is special syntax for defining functions that may take *varying* numbers of arguments (recall `and` and `+`), where Scheme binds a single variable to a list containing all of the received arguments (or all of the arguments after the *n*th...). I won't explain that syntax here.
686
687
688
689
690 ### Let, Letrec, and Define
691
692 Kapulet has the syntax:
693
694     # Kapulet
695     let
696       pat1  match expr1;
697       pat2  match expr2;
698       pat3  match expr3
699     in result
700
701 which is equivalent to:
702
703     # Kapulet
704     let
705       pat1  match expr1
706     in let
707       pat2  match expr2
708     in let
709       pat3  match expr3
710     in result
711
712 There is also a corresponding `letrec` form. In `let`, the bindings in `pat1` are in effect for the evaluation of all of `expr2`, `expr3`, and `result` (but not any further, if this is part of a more complex expression); similarly for the bindings in `pat2` and `pat3`. In `letrec`, all of the bindings on the left-hand side are in effect for all of the right-hand side expressions, as well as for the result.
713
714 OCaml only has the second, more verbose form of this, and writes it a bit differently:
715
716     (* OCaml *)
717     let
718       pat1  = expr1
719     in let
720       pat2  = expr2
721     in let
722       pat3  = expr3
723     in result
724
725 If you want to define some mutually recursive functions with `letrec`, OCaml uses a special syntax for that, using `letrec ...` <code><em>and</em></code> `... in ...`:
726
727     (* OCaml *)
728     letrec
729       even  = fun x -> if x = 0 then true else odd x
730     and
731       odd   = fun x -> if x = 0 then false else even x
732     in ...
733
734 Haskell has both of the syntactic forms that Kapulet does, though like OCaml, it uses `=` rather than `match`. And it wraps all the binding clauses with `{ ... }` (see [[earlier remarks|rosetta1#haskell-whitespace]] about Haskell and whitespace/indentation):
735
736     -- Haskell
737     let {
738       pat1  = expr1;
739       pat2  = expr2;
740       pat3  = expr3
741     } in result
742
743 Also, in Haskell `let` always means `letrec`. There is no term in Haskell that means what simple `let` does in Kapulet and OCaml.
744
745 Haskell also has another form, roughly synonymous with its `let ... in ...`. It looks like this:
746
747     -- Haskell
748     result where {
749       pat1  = expr1;
750       pat2  = expr2;
751       pat3  = expr3
752     }
753
754 Here all the new bindings introduced for the variables in the `pat`s are in effect for the evaluation of the `expr`s (this works like `letrec` too), and also for the evaluation of `result`.
755
756 There are a few places where you can use `let ... in ...` but not `... where ...`, and a few places where the inverse is true.
757
758 <!-- (1) `let pat = expr` has a use inside do-blocks and guards; (2) `let ... in ...` is an expression, and so can occur within other expressions; (3) `where` can bind multiple guard-clauses in a `case` block: in `case expr of { pat | g1 -> e1 | g2 -> e2 where { ... }; another_pat -> ... }`, the `where` bindings govern free variables in all of `g1`, `e1`, `g2`, `e2`. -->
759
760
761 <a id=five-lets></a>
762 Scheme has *four (or five)* syntactic forms here, including `let`, `let*`, `letrec`, and `letrec*`. The difference between the last two [is subtle](http://stackoverflow.com/questions/13078165) and only arises in the presence of continuations; you can just use `letrec` for ordinary purposes. I won't try to explain the difference between `let` and `let*` here, except to say this:
763
764 1.  When there's only a single pattern-binding clause, as in `(let ((var expression)) result)`, `let` and `let*` work the same.
765 2.  When there are multiple pattern-binding clauses, as in `(let ((var1 expression1) (var2 expression2)) result)`, then they work somewhat differently and `let*` is probably the one that works like you're expecting.
766
767 The `let*` form is the one that corresponds to `let` in Kapulet. I recommend you get in the habit of just always using `let*` (or `letrec`) in Scheme, instead of `let`.
768
769 When you're at the "toplevel" of your program, or of a library/module/compilation-unit (the terminology differs), there is also another syntactic form possible. In Kapulet, you'd write:
770
771     # Kapulet
772     let
773       pat1  match expr1;
774       ...
775     end
776     ... # rest of program or library
777
778 Notice that this form ends with `end`, not with `in result`. The above is roughly equivalent to:
779
780     # Kapulet
781     let
782       pat1  match expr1;
783       ...
784     in ... # rest of program or library
785
786 That is, the bindings initiated by the clauses of the `let` construction remain in effect until the end of the program or library. They can of course be "hidden" by subsequent bindings to new variables spelled the same way. The program:
787
788     # Kapulet
789     let
790       x  match 0
791     end
792     let
793       x  match 1
794     end
795     x
796
797 evaluates to `1`, just like:
798
799     # Kapulet
800     let
801       x  match 0
802     in let
803       x  match 1
804     in x
805
806 does. There's a similar form for `letrec`.
807
808 OCaml can do the same:
809
810     let
811       x = 0 ;;
812     let
813       x = 1 ;;
814     x
815
816 The double-semicolons are hints to OCaml's "toplevel interpreter" that a syntactic unit has finished. In some contexts they're not needed, but it does no harm to include them if you're not sure.
817
818 Haskell's "toplevel interpreter" (ghci) permits a syntactic form that looks superficially quite like these:
819
820     let x = 2
821     x
822
823 but under the covers something quite different is happening. (Specifically, you're working "inside the IO Monad", except that in this special context, expressions like `x` that don't evaluate to monadic values are permitted and evaluated. We don't expect that you will understand yet what any of this means.) If you're writing *in a file* that you want Haskell to interpret or compile, on the other hand, you have to do something a bit different (which you can't easily also do at the toplevel in ghci). [[Recall|topics/week1_kapulet_advanced#funct-declarations]] the shortcut by which we permitted:
824
825     # Kapulet
826     let
827       f  match lambda pat1. body1;
828       g  match lambda pat2 pat3. body2
829     in ...
830
831 to be written more concisely as:
832
833     # Kapulet
834     let
835       f pat1      = body1;
836       g pat2 pat3 = body2
837     in ...
838
839 OCaml and Haskell permit that same shorthand. And Haskell additionally permits the bare binding clauses of such expressions (that is, without the surrounding `let` and `in`) to occur at the toplevel of files. In other words, a Haskell file can look like this:
840
841     -- Haskell file.hs
842     f pat1      = body1
843
844     g pat2 pat3 = body2
845     ...
846
847 Note there are no semicolons here. These are called "toplevel declarations" of the functions `f` and `g`. A single function name can have multiple declarations (within a single scoping context), using different patterns:
848
849     -- Haskell file.hs
850     f [] = 0
851     f (x:xs) = 1 + f xs
852
853 defines `f` as a function that returns the length of a single List argument. (You can also do that *inside* Haskell's `let` constructions, too.) This is what corresponds *in Haskell files* to `let ... end` in Kapulet.
854
855 Haskell also permits multiple declarations of this sort inside its `let` and `where` constructs, too. Moreover, these declarations can also have [[pattern guards|rosetta1#haskell-guards]], as in:
856
857     -- Haskell file.fs
858     f [] = 0
859     f (x:xs) | odd x = 1 + f xs
860              | otherwise = f xs
861
862 <a id=define></a>
863 Scheme has a version of `letrec ... end`, which it writes as `define`. Thus in Scheme this:
864
865     ; Scheme
866     (define var1 expr1)
867     ... ; rest of program
868
869 evaluates the same as this:
870
871     ; Scheme
872     (letrec ((var1 expr1))
873             ... ; rest of program
874                 )
875
876 This is what we can call Scheme's [[fifth|rosetta1#five-lets]] form of the `let` family.
877
878 Some versions of Scheme permit you also to include `define` inside some (but not all) complex expressions. Thus you can write:
879
880     (lambda (x)
881       (define var1 expr1)
882       ...)
883
884 instead of:
885
886     (lambda (x)
887       (letrec ((var1 expr1))
888       ...))
889
890 There is no analogue to this in the other languages.
891
892
893
894
895 ### Further Installments ...
896
897 We will expand these comparisons (on separate web pages) as we introduce additional ideas in the course, such as types and monads and continuations.
898
899
900
901
902 ## Offsite Readings comparing Scheme, OCaml, and Haskell ##
903
904 *   [Haskell for OCaml Programmers](http://science.raphael.poss.name/haskell-for-ocaml-programmers.pdf)
905 *   [Introduction to OCaml for Haskellers](http://foswiki.cs.uu.nl/foswiki/pub/Stc/BeyondFunctionalProgrammingInHaskell:AnIntroductionToOCaml/ocaml.pdf), [another](http://blog.ezyang.com/2010/10/ocaml-for-haskellers/)
906 *   Haskell Wiki on [OCaml](https://wiki.haskell.org/OCaml)
907 *   [ML Dialects and Haskell](http://hyperpolyglot.org/ml)
908 *   [Differences between Haskell and SML?](http://www.quora.com/What-are-the-key-differences-between-Haskell-and-Standard-ML?browse)
909 *   [Comparing SML to OCaml](http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html)
910 *   [Haskell vs Scheme](http://www.reddit.com/r/programming/comments/nq1k/haskell_and_scheme_which_one_and_why/)
911
912
913
914
915 ## Why did you name these pages "Rosetta"? ##
916
917 The [Rosetta Stone](https://en.wikipedia.org/wiki/Rosetta_Stone) is a famous slab discovered during Napoleon's invasion of Egypt, that had the same decree written in ancient Greek (which modern scholars understood) and two ancient Egyptian scripts (which they didn't). The slab enabled us to recover understanding of those Egyptian scripts; and has since come to be a symbol for the simultaneous expression of a single idea in multiple languages. A number of websites do this for various programming languages:
918
919 <table><th>
920 <td>Scheme
921 <td>OCaml
922 <td>Haskell
923 <tr>
924 <td rowspan=10>&nbsp;
925 <td><a href="http://rosettacode.org/wiki/Category:Scheme">Rosetta Code</a>
926 <td><a href="http://rosettacode.org/wiki/Category:OCaml">Rosetta Code</a>
927 <td><a href="http://rosettacode.org/wiki/Category:Haskell">Rosetta Code</a>
928 <tr>
929 <td><a href="http://pleac.sourceforge.net/pleac_guile/index.html">PLEAC</a>
930 <td><a href="http://pleac.sourceforge.net/pleac_ocaml/index.html">PLEAC</a>
931 <td><a href="http://pleac.sourceforge.net/pleac_haskell/index.html">PLEAC</a>
932 <tr>
933 <td>n/a
934 <td colspan=2 align=center><hr><a href="http://langref.org/ocaml+haskell/solved">langref.org</a>
935 <tr>
936 <td><a href="http://www.codecodex.com/wiki/Category:Scheme">code codex</a>
937 <td><a href="http://www.codecodex.com/wiki/Category:Objective_Caml">code codex</a>
938 <td><a href="http://www.codecodex.com/wiki/Category:Haskell">code codex</a>
939 <tr>
940 <td><a href="http://community.schemewiki.org/?ninety-nine-scheme-problems">99 problems</a>
941 <td><a href="http://ocaml.org/learn/tutorials/99problems.html">99 problems</a>
942 <td><a href="https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems">99 problems</a>
943 </table>
944
945 See also the [Project Euler](https://projecteuler.net/) programming challenges.