1 ## Can you summarize the differences between your made-up language and Scheme, OCaml, and Haskell? ##
3 The made-up language we wet our toes in in week 1 is called Kapulet. (I'll tell you the story behind its name 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.
5 Also, if you want to read code written outside this class, or have others read your code, for these reasons too you'll need to make the shift over to one of the established languages.
7 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.)
11 ** *This page is still being written!* **
17 ... # this is a comment in Kapulet, that goes until the end of the line
19 ... ; this is a comment in Scheme, that goes until the end of the line
21 ... -- this is a comment in Haskell, that goes until the end of the line
23 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.
25 OCaml doesn't have comments of that sort. It only has "block" comments like this:
29 which may last for several lines. These comments *nest*, so that:
31 (* ... (* inner *) ... *)
35 Haskell also has block comments, though it `{- writes them differently -}`.
36 Haskell's block comments also nest.
38 Racket and Scheme also have block comments, though they `#| write them differently |#`.
39 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 aren't part of the official Scheme standard, but they are widely implemented.)
45 % Haskell's division into letter-based vs operators. Each can be "flagged" to temporarily behave as though it belonged to the other syntactic category (see below).
49 ### Infix operators and parentheses
52 Kapulet, OCaml, and Haskell all understand some expressions like `+` to be infix operators. So you would write:
60 Although 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 λ `(x, y). x + y`, whereas in OCaml and Haskell it's a *curried* function, which we can write (in Kapulet syntax) as λ `x y. x + y`.
62 Kapulet and OCaml have some operators 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 begin with letters will only be 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 letter-based function name to behave like an infix operator, by enclosing it in `` ` `` marks. Thus in Haskell you can write:
66 But without the `` ` ``, you'd have to write: `mod 3 2`.
68 Scheme has no infix operators. It ruthlessly demands that all functions that are to be applied to arguments come at the start of a list of expressions, regardless of whether those functions are spelled using letters, punctuation symbols, or a mix of the two. Thus in Scheme one always writes:
72 and the like. Moreover, in Scheme parentheses are never optional and never redundant. In contexts like this, 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:
76 what that would mean would be 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 ()`.) Scheme helpfully defines the result of applying `+` to zero arguments to be `0`. So then `((+) 3 2)` would evaluate to whatever `(0 3 2)` does, and that's an error, because `0` is not a function.
78 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 `'`.)
80 In Scheme, you can also do `(+ 3 2 10)`, and so on. You only have to write `(+ (+ 3 2) 10)` if you really want to.
82 % Parentheses have other roles in Scheme, too.
84 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:
87 let add = fun x y -> x + y in
94 In Scheme, the default would be to define `add` like this:
96 (define add (lambda (x y) (+ x y)))
98 Then 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:
100 (define curried_add (lambda (x) (lambda (y) (+ x y))))
101 (define add2 (curried_add 2))
104 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.
106 OCaml and Haskell also permit defining functions in uncurried form:
109 let add = fun (x, y) -> x + y in
110 let add2 = fun add 2 in ...
112 Here the last displayed line will fail, because `add` expects as its argument a tuple of two numbers.
114 Kapulet is close to OCaml and Haskell; though for pedagogical reasons I started out introducing uncurried definitions.
116 As we mentioned, in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
120 ten_minus match lambda x. 10 - x;
121 and_ys match lambda x. x & ys
122 in (ten_minus, and_ys)
128 ten_minus match (10 - );
130 in (ten_minus, and_ys)
132 There are just minor differences between these languages. First, OCaml doesn't have the `( + 10)` or `(10 + )` forms, but only the `( + )`. Second, as a special case, OCaml doesn't permit you to do this with its list-consing operator `::`. You have to write `fun x xs -> x :: xs`, not `( :: )`. Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its sequence-consing operator `&`; and in Haskell, `( : )`, `(x : )`, and `( : xs)` are the same.
134 Thirdly, in Kapulet, `( - 10)` also expresses λ `x. x - 10` (consistently with `(10 - )`), but Haskell (and OCaml) treat this form differently, and interpret it as meaning the integer `- 10`. Here's how to express some things in Kapulet:
138 ( - 2) # ( - 2) 10 == 8
143 and here are their translations into Haskell:
147 (subtract 2) -- subtract 2 10 == 8
148 negate -- (0 - ) also works
151 OCaml expresses `(0 - )` or `negate` as `~-`. You can write `3 * (0 - 2)` in OCaml as either `3 * ( -2 )` or as `3 * ~-2`.
153 I know all these languages fairly well, and I still find this last issue difficult to keep track of. You may be starting to understand why I spoke of "warts."
156 ### Equality and Booleans
158 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 notion is written `!=` in Kapulet, `/=` in Haskell, and `<>` in OCaml. (Again, `!=` means something else in OCaml.)
160 The relations that are written `and`, `or`, and `not` are written in Haskell and OCaml as `&&`, `||`, and `not`. (Haskell uses `and` and `or` to express functions that form the 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 `&&`.)
164 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`. They're 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-ish", like `0` and the empty list. Thus `(if 0 'yes 'no)` will evaluate to `'yes`.
166 Scheme recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "true-ish" value, like all of its other values that aren't `#f`.
170 ### Sequences, Lists, and Tuples
172 In Kapulet, we have a notion I called a "sequence" which has the empty element `[]` and the cons-ing operator `&`, so that:
180 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 `:`, but it uses it to deal with types, and Haskell in turn also uses `::`, but that's what *it* uses to deal with types. Grr.)
182 Kapulet writes the operator that concatenates or appends sequences as `&&`. Thus:
187 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:
192 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:
195 [1; 2] @ [3; 4; 5] ;;
198 evaluate to `[1; 2; 3; 4; 5]` and `"overdue"`. Note that OCaml separates its `list` items 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)]`.
200 Here are some list functions in Kapulet:
204 # following were defined in homework
214 # following were defined in extra credit
220 concat # converts [[10, 20], [30], [], [40, 50]] to [10, 20, 30, 40, 50] (only merging a single layer of []s)
221 (mem) # infix syntax, 2 mem [1, 2, 3] == 'true
222 nth # nth [10, 20, 30] 1 == 20, because first element is at position 0, fails if index is out of bounds
223 all? p xs # all? odd? [1, 3, 5] == 'true
224 any? p xs # any? even? [1, 3, 5] == 'false
228 Here are the corresponding functions in Haskell:
233 tail -- compare head, which fails on []
234 drop -- but these are curried functions, so you write `drop n xs`, not `drop (n, xs)` as in Kaupulet
240 zipWith {- zip handles the special case where f is the function that forms ordered pairs
241 both zipWith and zip stop with the shortest list -}
242 unzip -- doesn't take an f argument, assumes (\(x, y) -> (x, y))
247 elem -- not infix syntax, but often written as: 2 `elem` [1, 2, 3]
248 (!!) -- infix syntax: [10, 20, 30] !! 1 == 20; fails if index is out of bounds
254 Here they are in OCaml:
257 (@) (* or List.append *)
258 (* no function corresponding to empty? *)
259 List.tl (* compare List.hd, which fails on [] *)
260 (* no function corresponding to drop or take *)
261 (* no function corresponding to split; OCaml uses List.split to mean something else *)
262 List.filter (* also List.find_all *)
265 List.map2 (* compare List.combine, like Haskell's zip
266 both map2 and combine fail if the lists are different lengths *)
267 List.split (* like Haskell's unzip, doesn't take an f argument *)
268 (* no function corresponding to takewhile or dropwhile *)
270 List.concat (* also List.flatten, which still only merges a single layer of []s *)
271 List.mem (* not infix syntax *)
272 List.nth (* List.nth [10; 20; 30] 1 = 20; fails if index is out of bounds *)
277 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 special case. Let's ignore the improper `list`s. Scheme's (proper) `list`s and `vector`s each has a claim to correspond to Kapulet's sequences, Haskell's Lists, and OCaml's `list`s. Each if also somewhat different. The dominant differences are:
279 1. these structures in Scheme can contain heterogenously-typed elements, including further `list`s and `vector`s in some positions but not in others
280 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
281 elements at different stages in a program's evaluation
283 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).
285 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:
289 and lists with more elements like this:
294 (list 10 x 'alpha (list 'beta 'gamma) 'delta 20)
296 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:
299 '(10) ; same as (list 10)
300 '(10 alpha) ; same as (list 10 'alpha)
301 '(10 alpha (beta gamma) 20) ; same as (list 10 'alpha (list 'beta 'gamma) 20)
303 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.)
306 Here are the `list` functions in Scheme corresponding to the functions listed in the other languages:
308 cons ; corresponds to Kaupulet's ( & ), Haskell's ( : ), OCaml's `::`
310 append ; corresponds to Kapulet's ( && ), Haskell's ( ++ ), OCaml's ( @ )
311 ; can be applied to one or more arguments
312 null? ; corresponds to Kapulet's empty?, Haskell's null
313 car ; corresponds to Haskell's head
314 cdr ; corresponds to Kapulet's and Haskell's tail
315 (list-tail xs k) ; corresponds to Kapulet's drop (k, xs); fails if out-of-bounds
316 ; no official function corresponding to take or split or filter or partition
317 map ; corresponds to Kapulet's map and map2
318 ; can take one or more list arguments
319 ; no official function corresponding to unmap2 or takewhile or dropwhile
321 ; no official function corresponding to concat
322 member ; corresponds to Kapulet's (mem) and Haskell's elem
323 (list-ref xs k) ; corresponds to Kapulet's `nth xs k`
324 ; no official function corresponding to all or any
326 All of the functions listed as missing from the official Scheme standard can be found it various add-on libraries, or you could define them yourself if you had to.
350 Same in all: `succ`, `pred`, `fst`, `snd`.
352 Same in Kapulet and Haskell (modulo the differences between multivalues and tuples), aren't predefined in OCaml: `id`, `const`, `flip`, `curry`, `uncurry`.
354 Kapulet's `(comp)` is Haskell's `( . )`; isn't predefined in OCaml.
356 Kapulet and Haskell both have `( $ )`; OCaml expresses as `( @@ )`. (OCaml also has `|>` to express the converse operation: `f x`, `f @@ x` and `x |> f` all mean the same.)
358 Kapulet's `odd?` and `even?` are Haskell's `odd`, `even`; aren't predefined in OCaml.
360 Kapulet's `swap` (defined in homework) is Haskell's `Data.Tuple.swap`.
362 Kapulet's `dup` isn't predefined in Haskell but can be easily expressed as `\x -> (x, x)`.
371 (This page is being worked on...)
374 ## Offsite Readings comparing Scheme, OCaml, and Haskell ##
378 * [Haskell for OCaml Programmers](http://science.raphael.poss.name/haskell-for-ocaml-programmers.pdf)
379 * [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/)
380 * Haskell Wiki on [OCaml](https://wiki.haskell.org/OCaml)
381 * [ML Dialects and Haskell](http://hyperpolyglot.org/ml)
382 * [Differences between Haskell and SML?](http://www.quora.com/What-are-the-key-differences-between-Haskell-and-Standard-ML?browse)
383 * [Comparing SML to OCaml](http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html)
387 ** *This page is still being written!* **
390 ## Can you summarize the differences between your made-up language and Scheme, OCaml, and Haskell? ##
392 The made-up language we wet our toes in in week 1 is called Kapulet. (I'll tell you the story behind its name 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.
394 Also, if you want to read code written outside this class, or have others read your code, for these reasons too you'll need to make the shift over to one of the established languages.
396 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.)
400 ... # this is a comment in Kapulet, that goes until the end of the line
402 ... ; this is a comment in Scheme, that goes until the end of the line
404 ... -- this is a comment in Haskell, that goes until the end of the line
406 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.
408 OCaml doesn't have comments of that sort. It only has "block" comments like this:
412 which may last for several lines. These comments *nest*, so that:
414 (* ... (* inner *) ... *)
418 Haskell also has block comments, though it `{- writes them differently -}`.
419 Haskell's block comments also nest.
421 Racket and Scheme also have block comments, though they `#| write them differently |#`.
422 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 aren't part of the official Scheme standard, but they are widely implemented.)
428 % Haskell's division into letter-based vs operators. Each can be "flagged" to temporarily behave as though it belonged to the other syntactic category (see below).
432 ### Infix operators and parentheses
435 Kapulet, OCaml, and Haskell all understand some expressions like `+` to be infix operators. So you would write:
443 Although 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 λ `(x, y). x + y`, whereas in OCaml and Haskell it's a *curried* function, which we can write (in Kapulet syntax) as λ `x y. x + y`.
445 Kapulet and OCaml have some operators 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 letter-made function term to behave like an infix operator, by enclosing it in `` ` `` marks. Thus in Haskell you can write:
449 But without the `` ` ``, you'd have to write: `mod 3 2`.
451 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 those functions are spelled using letters, punctuation symbols, or a mix of the two. Thus in Scheme one always writes:
455 and the like. Moreover, in Scheme parentheses are never optional and never redundant. In contexts like this, 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:
459 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 ()`.) 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.
461 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 `'`.)
463 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.
465 % Parentheses have other roles in Scheme, too.
467 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:
470 let add = fun x y -> x + y in
477 In Scheme, the default would be to define `add` like this:
479 (define add (lambda (x y) (+ x y)))
481 Then 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:
483 (define curried_add (lambda (x) (lambda (y) (+ x y))))
484 (define add2 (curried_add 2))
487 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.
489 OCaml and Haskell also permit defining functions in uncurried form:
492 let add = fun (x, y) -> x + y in
493 let add2 = fun add 2 in ...
495 Here the last displayed line will fail, because `add` expects as its argument a tuple of two numbers.
497 Kapulet essentially works like OCaml and Haskell; though for pedagogical reasons I started out by introducing uncurried definitions, rather than the *curried* definitions those other languages predominantly use.
499 As we mentioned, in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
503 ten_minus match lambda x. 10 - x;
504 and_ys match lambda x. x & ys
505 in (ten_minus, and_ys)
511 ten_minus match (10 - );
513 in (ten_minus, and_ys)
515 There are just minor differences between these languages. First, OCaml doesn't have the `( + 10)` or `(10 + )` forms, but only the `( + )`. Second, as a special case, OCaml doesn't permit you to do this with its list-consing operator `::`. You have to write `fun x xs -> x :: xs`, not `( :: )`. Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its sequence-consing operator `&`; and in Haskell, `( : )`, `(x : )`, and `( : xs)` are the same.
517 Thirdly, in Kapulet, `( - 10)` also expresses λ `x. x - 10` (consistently with `(10 - )`), but Haskell (and OCaml) treat this form differently, and interpret it as meaning the integer `- 10`. Here's how to express some things in Kapulet:
521 ( - 2) # ( - 2) 10 == 8
526 and here are their translations into Haskell:
530 (subtract 2) -- subtract 2 10 == 8
531 negate -- (0 - ) also works
534 OCaml expresses `(0 - )` or `negate` as `~-`. You can write `3 * (0 - 2)` in OCaml as either `3 * ( -2 )` or as `3 * ~-2`.
536 I know all these languages fairly well, and I still find this last issue difficult to keep track of. You may be starting to understand why I spoke of "warts."
539 ### Equality and Booleans
541 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 notion is written `!=` in Kapulet, `/=` in Haskell, and `<>` in OCaml. (Again, `!=` means something else in OCaml.)
543 The relations that are written `and`, `or`, and `not` are written in Haskell and OCaml as `&&`, `||`, and `not`. (Haskell uses `and` and `or` to express functions that form the 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 `&&`.)
547 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`. They're 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-ish", like `0` and the empty list. Thus `(if 0 'yes 'no)` will evaluate to `'yes`.
549 Scheme recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "true-ish" value, like all of its other values that aren't `#f`.
553 ### Sequences, Lists, and Tuples
555 In Kapulet, we have a notion I called a "sequence" which has an empty form `[]` and a cons-ing operator `&`, so that:
563 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 `:`, but it uses it to deal with types, and Haskell in turn also uses `::`, but that's what *it* uses to deal with types. Grr.)
565 Kapulet writes the operator that concatenates or appends sequences as `&&`. Thus:
570 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:
575 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:
578 [1; 2] @ [3; 4; 5] ;;
581 evaluate to `[1; 2; 3; 4; 5]` and `"overdue"`. Note that OCaml separates its `list` items 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)]`.
583 Here are some list functions in Kapulet:
587 # the following were defined in homework
597 # the following were defined in extra credit
603 concat # converts [[10, 20], [30], [], [40, 50]]
604 # to [10, 20, 30, 40, 50] (only merging a single layer of []s)
605 (mem) # infix syntax, 2 mem [1, 2, 3] == 'true
606 nth # nth [10, 20, 30] 1 == 20, because the first element
607 # is at position 0; fails if index is out of bounds
608 all? p xs # all? odd? [1, 3, 5] == 'true
609 any? p xs # any? even? [1, 3, 5] == 'false
613 Here are the corresponding functions in Haskell:
618 tail -- compare head, which fails on []
619 drop {- but these are curried functions, so you write `drop n xs`
620 not `drop (n, xs)` as in Kapulet -}
626 zipWith {- zip handles the special case where f is the function that forms ordered pairs
627 both zipWith and zip stop with the shortest list -}
628 unzip -- doesn't take an f argument, assumes (\(x, y) -> (x, y))
633 elem -- not infix syntax, but often written as: 2 `elem` [1, 2, 3]
634 (!!) -- infix syntax: [10, 20, 30] !! 1 == 20; fails if index is out of bounds
640 Here they are in OCaml:
643 (@) (* or List.append *)
644 (* no function corresponding to empty? *)
645 List.tl (* compare List.hd, which fails on [] *)
646 (* no function corresponding to drop or take *)
647 (* no function corresponding to split; OCaml uses List.split to mean something else *)
648 List.filter (* also List.find_all *)
651 List.map2 (* compare List.combine, like Haskell's zip
652 both map2 and combine fail if the lists are different lengths *)
653 List.split (* like Haskell's unzip, doesn't take an f argument *)
654 (* no function corresponding to takewhile or dropwhile *)
656 List.concat (* also List.flatten, which still only merges a single layer of []s *)
657 List.mem (* not infix syntax *)
658 List.nth (* List.nth [10; 20; 30] 1 = 20; fails if index is out of bounds *)
663 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 special case. Let's ignore the improper `list`s. Scheme's (proper) `list`s and `vector`s each has a claim to correspond to Kapulet's sequences, Haskell's Lists, and OCaml's `list`s. Each is also somewhat different. The dominant differences are:
665 1. these structures in Scheme can contain heterogenously-typed elements, including further `list`s and `vector`s in some positions but not in others
666 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
667 elements at different stages in a program's evaluation
669 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).
671 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:
675 and lists with more elements like this:
680 (list 10 x 'alpha (list 'beta 'gamma) 'delta 20)
682 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:
685 '(10) ; same as (list 10)
686 '(10 alpha) ; same as (list 10 'alpha)
687 '(10 alpha (beta gamma) 20) ; same as (list 10 'alpha (list 'beta 'gamma) 20)
689 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.)
692 Here are the `list` functions in Scheme corresponding to the functions listed in the other languages:
694 cons ; corresponds to Kapulet's ( & ), Haskell's ( : ), OCaml's `::`
696 append ; corresponds to Kapulet's ( && ), Haskell's ( ++ ), OCaml's ( @ )
697 ; can be applied to one or more arguments
698 null? ; corresponds to Kapulet's empty?, Haskell's null
699 car ; corresponds to Haskell's head
700 cdr ; corresponds to Kapulet's and Haskell's tail
701 (list-tail xs k) ; corresponds to Kapulet's drop (k, xs); fails if out-of-bounds
702 ; no official function corresponding to take or split or filter or partition
703 map ; corresponds to Kapulet's map and map2
704 ; can take one or more list arguments
705 ; no official function corresponding to unmap2 or takewhile or dropwhile
707 ; no official function corresponding to concat
708 member ; corresponds to Kapulet's (mem) and Haskell's elem
709 (list-ref xs k) ; corresponds to Kapulet's `nth xs k`
710 ; no official function corresponding to all or any
712 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.
722 characters: #\c #\xff #\space #\newline
729 Same in all: `succ`, `pred`, `fst`, `snd`.
731 Same in Kapulet and Haskell (modulo the differences between multivalues and tuples), aren't predefined in OCaml: `id`, `const`, `flip`, `curry`, `uncurry`.
733 Kapulet's `(comp)` is Haskell's `( . )`; isn't predefined in OCaml.
735 Kapulet and Haskell both have `( $ )`; OCaml expresses as `( @@ )`. (OCaml also has `|>` to express the converse operation: `f x`, `f @@ x` and `x |> f` all mean the same.)
737 Kapulet's `odd?` and `even?` are Haskell's `odd`, `even`; aren't predefined in OCaml.
739 Kapulet's `swap` (defined in homework) is Haskell's `Data.Tuple.swap`.
741 Kapulet's `dup` isn't predefined in Haskell but can be easily expressed as `\x -> (x, x)`.
749 (This page is being worked on...)
754 ## Offsite Readings comparing Scheme, OCaml, and Haskell ##
757 * [Haskell for OCaml Programmers](http://science.raphael.poss.name/haskell-for-ocaml-programmers.pdf)
758 * [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/)
759 * Haskell Wiki on [OCaml](https://wiki.haskell.org/OCaml)
760 * [ML Dialects and Haskell](http://hyperpolyglot.org/ml)
761 * [Differences between Haskell and SML?](http://www.quora.com/What-are-the-key-differences-between-Haskell-and-Standard-ML?browse)
762 * [Comparing SML to OCaml](http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html)
767 ## Why did you name these pages "Rosetta"? ##
769 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:
776 <td rowspan=10>
777 <td><a href="http://rosettacode.org/wiki/Category:Scheme">Rosetta Code</a>
778 <td><a href="http://rosettacode.org/wiki/Category:OCaml">Rosetta Code</a>
779 <td><a href="http://rosettacode.org/wiki/Category:Haskell">Rosetta Code</a>
781 <td><a href="http://pleac.sourceforge.net/pleac_guile/index.html">PLEAC</a>
782 <td><a href="http://pleac.sourceforge.net/pleac_ocaml/index.html">PLEAC</a>
783 <td><a href="http://pleac.sourceforge.net/pleac_haskell/index.html">PLEAC</a>
786 <td colspan=2 align=center><hr><a href="http://langref.org/ocaml+haskell/solved">langref.org</a>
788 <td><a href="http://www.codecodex.com/wiki/Category:Scheme">code codex</a>
789 <td><a href="http://www.codecodex.com/wiki/Category:Objective_Caml">code codex</a>
790 <td><a href="http://www.codecodex.com/wiki/Category:Haskell">code codex</a>
792 <td><a href="http://community.schemewiki.org/?ninety-nine-scheme-problems">99 problems</a>
793 <td><a href="http://ocaml.org/learn/tutorials/99problems.html">99 problems</a>
794 <td><a href="https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems">99 problems</a>
797 See also the [Project Euler](https://projecteuler.net/) programming challenges.