+[[!toc]]
+
The functional programming literature tends to use one of four languages: Scheme, OCaml, Standard ML (SML), or Haskell. With experience, you'll grow comfortable switching between these. At the beginning, though, it can be confusing.
-The easiest translations are between OCaml and SML. These languages are both derived from a common ancestor, ML. For the most part, the differences between them are only superficial. [Here's a translatio nmanual](http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html).
+The easiest translations are between OCaml and SML. These languages are both derived from a common ancestor, ML. For the most part, the differences between them are only superficial. [Here's a translation manual](http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html).
In some respects these languages are closer to Scheme than to Haskell: Scheme, OCaml and SML all default to call-by-value evaluation order, and all three have native syntax for mutation and other imperative idioms (though that's not central to their design). Haskell is different in both respects: the default evaluation order is call-by-name (strictly speaking, it's "call-by-need", which is a more efficient cousin), and the only way to have mutation or the like is through the use of monads.
Additionally, the syntax of OCaml and SML is superficially much closer to Haskell's than to Scheme's.
-##Comments, Whitespace, and Brackets##
+#Comments, Whitespace, and Brackets#
-- this is a single line comment in Haskell
* In Haskell, a block of code can be bracketed with `{` and `}`, with different expressions separated by `;`. But usually one would use line-breaks and proper indentation instead. In OCaml, separating expressions with `;` has a different meaning, having to do with how side-effects are sequenced. Instead, one can bracket a block of code with `(` and `)` or with `begin` and `end`. In Scheme, of course, every parentheses is significant.
-##Scheme and OCaml##
+#Scheme and OCaml#
* You can [try Scheme in your web browser](http://tryscheme.sourceforge.net/). This is useful if you don't have Racket or another Scheme implementation installed---but don't expect it to have all the bells and whistles of a mature implementation!
* **Type Variants and Pattern Matching** If you want to reproduce this kind of OCaml code:
- type lambda_expression = Var of char | Lam of char * lambda_expression | App of lambda_expression * lambda_expression;;
+ # type lambda_expression = Var of char | Lam of char * lambda_expression | App of lambda_expression * lambda_expression;;
- let rec free_vars (expr : lambda_expression) : char list =
+ # let rec free_vars (expr : lambda_expression) : char list =
match expr with
| Var label -> [label]
| Lam (label, body) -> remove label (free_vars body)
| App (left, right) -> merge (free_vars left) (free_vars right);;
+ # free_vars (Lam ('x', (App (Var 'x', Var 'y'))));;
+ - : char list = ['y']
+
in Scheme, you have two choices. First, the quick hack:
; we use the symbols 'var and 'lam as tags, and assume
Second, you can create real datatypes and pattern-match on them. There are several tools for doing this. I'll describe the `define-datatype` and `cases` forms developed for the book *Essentials of Programming Languages* (EoPL) by Friedman and Wand.
- (Alternatives include the `struct` form in Racket, see <http://docs.racket-lang.org/guide/define-struct.html>. Also `define-record-type` from srfi-9 and srfi-57; see also <http://docs.racket-lang.org/r6rs-lib-std/r6rs-lib-Z-H-7.html>.)
+ (Alternatives include [the `struct` form in Racket](http://docs.racket-lang.org/guide/define-struct.html). Also `define-record-type` from srfi-9 and srfi-57; see also [the r6rs libs](http://docs.racket-lang.org/r6rs-lib-std/r6rs-lib-Z-H-7.html).)
Here is how the tools from EoPL work. You must begin your file either with `#lang eopl` or with the first two lines below:
(lam (label body) (remove label (free-vars body)))
(app (left right) (remove-duplicates (append (free-vars left) (free-vars right))))))
+ (free-vars (lam 'x (app (var 'x) (var 'y))))
+ ; evaluates to '(y)
-* Scheme has excellent support for working with implicit or "first-class" **continuations**, using either `call/cc` or any of various delimited continuation operators. See <http://docs.racket-lang.org/reference/cont.html?q=shift&q=do#%28part._.Classical_.Control_.Operators%29>.
+* Scheme has excellent support for working with implicit or "first-class" **continuations**, using either `call/cc` or any of various delimited continuation operators. See [the Racket docs](http://docs.racket-lang.org/reference/cont.html?q=shift&q=do#%28part._.Classical_.Control_.Operators%29).
In Scheme you can use these forms by default (they're equivalent):
But assuming you do manage to compile and install Oleg's library, here's how you'd use it in an OCaml session:
#require "delimcc";; (* loading Oleg's library this way requires the findlib package *)
+ (* if you don't have findlib, you'll need to start ocaml like
+ * this instead: ocaml -I /path/to/directory/containing/delimcc delimcc.cma
+ *)
open Delimcc;; (* this lets you say e.g. new_prompt instead of Delimcc.new_prompt *)
let p = new_prompt ();;
let prompt thunk = push_prompt p thunk;;
There is also a library for using *undelimited* continuations in OCaml, but it's shakier than Oleg's delimited continuation library.
-We won't say any more about translating to and from Scheme.
+There are some more hints about Scheme [here](/assignment8/) and [here](/week1/). We won't say any more here.
+
-##Haskell and OCaml##
+#Haskell and OCaml#
We will however try to give some general advice about how to translate between OCaml and Haskell.
* Again, it may sometimes be useful to [try Haskell in your web browser](http://tryhaskell.org/)
-* There are many Haskell tutorials and textbooks available. This is probably the most actively developed: [Haskell Wikibook](http://en.wikibooks.org/wiki/Haskell)
-* [Yet Another Haskell Tutorial](http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf) (much of this excellent book has supposedly been integrated into the Haskell Wikibook)
-* All About Monads has supposedly also been integrated into the Haskell Wikibook
+* There are many Haskell tutorials and textbooks available. This is probably the most actively developed: [Haskell wikibook](http://en.wikibooks.org/wiki/Haskell)
+* [Yet Another Haskell Tutorial](http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf) (much of this excellent book has supposedly been integrated into the Haskell wikibook)
+* All About Monads has supposedly also been integrated into the Haskell wikibook
* (A not-so-)[Gentle Introduction to Haskell](http://web.archive.org/web/http://www.haskell.org/tutorial/) (archived)
* [Learn You a Haskell for Great Good](http://learnyouahaskell.com/)
+* [Another page comparing Haskell and OCaml](http://blog.ezyang.com/2010/10/ocaml-for-haskellers/)
-
-#Type expressions#
+##Type expressions##
* In Haskell, you say a value has a certain type with: `value :: type`. You express the operation of prepending a new `int` to a list of `int`s with `1 : other_numbers`. In OCaml it's the reverse: you say `value : type` and `1 :: other_numbers`.
-* In Haskell, type names and constructors both begin with capital letters, and type variables always appear after their constructors, in Curried form. And the primary term for declaring a new type is `data` (short for "abstract datatype").
-So we have:
+* In Haskell, type names and constructors both begin with capital letters, and type variables always appear after their constructors, in Curried form. And the primary term for declaring a new type is `data` (short for [[!wikipedia algebraic data type]]). So we have:
data Either a b = Left a | Right b;
data FooType a b = Foo_constructor1 a b | Foo_constructor2 a b;
type Weight = Integer
type Person = (Name, Address) -- supposing types Name and Address to be declared elsewhere
- then you can use a value of type `Integer` wherever a `Weight` is expected, and vice versa. `newtype` and `data` on the other hand, create genuinely new types. `newtype` is basically just an efficient version of `data` that you can use in special circumstances. `newtype` must always take one type argument and have one value constructor. For example:
+ then you can use a value of type `Integer` wherever a `Weight` is expected, and vice versa. <!-- `type` is allowed to be parameterized -->
+
+ `newtype` and `data` on the other hand, create genuinely new types. `newtype` is basically just an efficient version of `data` that you can use in special circumstances. `newtype` must always take one type argument and have one value constructor. For example:
newtype PersonalData a = PD a
You could also say:
- data PersonalData a = PD a
+ data PersonalData2 a = PD2 a
- And `data` also allows multiple type arguments, and multiple variants and value constructors.
+ And `data` also allows multiple type arguments, and multiple variants and value constructors. <!-- Subtle difference: whereas `PersonalData a` is isomorphic to `a`, `PersonalData2 a` has an additional value, namely `PD2 _|_`. In a strict language, this is an additional type an expression can have, but it would not be a value. -->
OCaml just uses the one keyword `type` for all of these purposes:
type person = name * address;;
type 'a personal_data = PD of 'a;;
+* When a type only has a single variant, as with PersonalData, Haskell programmers will often use the same name for both the type and the value constructor, like this:
+
+ data PersonalData3 a = PersonalData3 a
+
+ The interpreter can always tell from the context when you're using the type name and when you're using the value constructor.
+
* The type constructors discussed above took simple types as arguments. In Haskell, types are also allowed to take *type constructors* as arguments:
data BarType t = Bint (t Integer) | Bstring (t string)
class Eq a where
(==) :: a -> a -> Bool
- This declares the type-class `Eq`; in order to belong to this class, a type `a` will have to supply its own implementation of the function ==, with the type a -> a -> Bool. Here is how the `Integer` class signs up to join the type-class:
+ This declares the type-class `Eq`; in order to belong to this class, a type `a` will have to supply its own implementation of the function `==`, with the type `a -> a -> Bool`. Here is how the `Integer` class signs up to join this type-class:
instance Eq Integer where
- x == y = ...
+ x == y = ... some definition for the Integer-specific version of that function here ...
Type expressions can be conditional on some of their parameters belonging to certain type-classes. For example:
says that if `a` belongs to the typeclass `Eq`, then so too does `Tree a`, and in such cases here is the implementation of `==` for `Tree a`...
-* OCaml doesn't have type-classes. You can do soemthing similar with OCaml modules that take are parameterized on other modules. Again, [see here](/code/tree_monadize.ml) for an example.
+* OCaml doesn't have type-classes. You can do something similar with OCaml modules that take are parameterized on other modules. Again, [see here](/code/tree_monadize.ml) for an example.
* Some specific differences in how certain types are expressed. This block in Haskell:
Prelude> let x = () :: ()
Prelude> let x = (1, True) :: (Int, Bool)
-corresponds to this block in OCaml:
+ corresponds to this block in OCaml:
# type 'a option = None | Some of 'a;;
type 'a option = None | Some of 'a
* We'll discuss differences between Haskell's and OCaml's record types below.
-#Lists, Tuples, Unit, Booleans#
+##Lists, Tuples, Unit, Booleans##
* As noted above, Haskell describes the type of a list of `Int`s as `[Int]`. OCaml describes it as `int list`. Haskell describes the type of a pair of `Int`s as `(Int, Int)`. OCaml describes it as `int * int`. Finally, Haskell uses `()` to express both the unit type and a value of that type. In OCaml, one uses `()` for the value and `unit` for the type.
In OCaml, there is no predefined `null` or `isempty` function. One can still test whether a list is empty using the comparison `lst = []`.
-* In Haskell, the expression [1..5] is the same as [1,2,3,4,5], and the expression [0..] is a infinite lazily-evaluated stream of the natural numbers. In OCaml, there is no [1..5] shortcut, lists must be finite, and they are eagerly evaluated. It is possible to create lazy streams in OCaml, even infinite ones, but you have to use other techniques than the native list type.
+* In Haskell, the expression `[1..5]` is the same as `[1,2,3,4,5]`, and the expression `[0..]` is a infinite lazily-evaluated stream of the natural numbers. In OCaml, there is no `[1..5]` shortcut, lists must be finite, and they are eagerly evaluated. It is possible to create lazy streams in OCaml, even infinite ones, but you have to use other techniques than the native list type.
* Haskell has *list comprehensions*:
List.map (fun x -> x * x) (List.filter odd [1..10]);;
-* In Haskell, the expressions "abc" and ['a','b','c'] are equivalent. (Strings are just lists of chars. In OCaml, these expressions have two different types.
+* In Haskell, the expressions `"abc"` and `['a','b','c']` are equivalent. (Strings are just lists of `char`s.) In OCaml, these expressions have two different types.
Haskell uses the operator `++` for appending both strings and lists (since Haskell strings are just one kind of list). OCaml uses different operators:
- "string1" ^ "string2"
- ['s';'t'] @ ['r';'i';'n';'g']
- (* or equivalently *)
- List.append ['s';'t'] ['r';'i';'n';'g']
+ # "string1" ^ "string2";;
+ - : string = "string1string2"
+ # ['s';'t'] @ ['r';'i';'n';'g'];;
+ - : char list = ['s'; 't'; 'r'; 'i'; 'n'; 'g']
+ # (* or equivalently *)
+ List.append ['s';'t'] ['r';'i';'n';'g'];;
+ - : char list = ['s'; 't'; 'r'; 'i'; 'n'; 'g']
-#Let and Where#
+##Let and Where##
* Haskell permits both:
in let result2 = x + 1
in result1 + result2;;
-#Patterns#
+##Patterns##
* In OCaml:
[] -> result4
-#Records#
+##Records##
+
+Haskell and OCaml both have `records`, which are essentially just tuples with a pretty interface. We introduced these in the wiki notes [here](/coroutines_and_aborts/).
-Haskell and OCaml both have `records`, which are essentially just tuples with a pretty interface. The syntax for declaring and using these is a little bit different in the two languages.
+The syntax for declaring and using these is a little bit different in the two languages.
* In Haskell one says:
-- declare a record type
- data Color = C { red, green, blue :: Int }
+ data Color = Col { red, green, blue :: Int }
-- create a value of that type
- let c = C { red = 0, green = 127, blue = 255 }
+ let c = Col { red = 0, green = 127, blue = 255 }
In OCaml one says instead:
- type color = { red : int; green : int; blue : int};;
+ type color = { red : int; green : int; blue : int };;
let c = { red = 0; green = 127; blue = 255 }
- Notice that OCaml doesn't use any value constructor `C`. The record syntax `{ red = ...; green = ...; blue = ... }` is by itself the constructor. The record labels `red`, `green`, and `blue` cannot be re-used for any other record type.
+ Notice that OCaml doesn't use any value constructor `Col`. The record syntax `{ red = ...; green = ...; blue = ... }` is by itself the constructor. The record labels `red`, `green`, and `blue` cannot be re-used for any other record type.
* In Haskell, one may have multiple constructors for a single record type, and one may re-use record labels within that type, so long as the labels go with fields of the same type:
data FooType = Constructor1 {f :: Int, g :: Float} | Constructor2 {f :: Int, h :: Bool}
-* In Haskell, one can extract the field of a record like this:
+* In Haskell, one can extract a single field of a record like this:
- let c = C { red = 0, green = 127, blue = 255 }
+ let c = Col { red = 0, green = 127, blue = 255 }
in red c -- evaluates to 0
- In OCaml:
+ In OCaml one says:
let c = { red = 0; green = 127; blue = 255 }
in c.red (* evaluates to 0 *)
* In both languages, there is a special syntax for creating a copy of an existing record, with some specified fields altered. In Haskell:
let c2 = c { green = 50, blue = 50 }
- -- evaluates to C { red = red c, green = 50, blue = 50 }
+ -- evaluates to Col { red = red c, green = 50, blue = 50 }
In OCaml:
* One pattern matches on records in similar ways. In Haskell:
- let C { red = r, green = g } = c
+ let Col { red = r, green = g } = c
in r
In OCaml:
- let { red = r; green = g } = c
+ let { red = r; green = g; _ } = c
in r
In Haskell:
- makegray c@(C { red = r} ) = c { green = r, blue = r }
+ makegray c@(Col { red = r } ) = c { green = r, blue = r }
is equivalent to:
- makegray c = let C { red = r } = c
+ makegray c = let Col { red = r } = c
in { red = r, green = r, blue = r }
In OCaml it's:
- # let makegray ({red = r} as c) = { c with green=r; blue=r };;
+ # let makegray ({ red = r; _ } as c) = { c with green=r; blue=r };;
val makegray : color -> color = <fun>
# makegray { red = 0; green = 127; blue = 255 };;
- : color = {red = 0; green = 0; blue = 0}
+* Records just give your types a pretty interface; they're entirely dispensable. Instead of:
+
+ type color = { red : int; green : int; blue : int };;
+ let c = { red = 0; green = 127; blue = 255 };;
+ let r = c.red;;
-#Functions#
+ You could instead just use a more familiar data constructor:
+
+ type color = Color of (int * int * int);;
+ let c = Color (0, 127, 255);;
+
+ and then extract the field you want using pattern-matching:
+
+ let Color (r, _, _) = c;;
+ (* or *)
+ match c with Color (r, _, _) -> ...
+
+ (Or you could just use bare tuples, without the `Color` data constructor.)
+
+ The record syntax only exists because programmers sometimes find it more convenient to say:
+
+ ... c.red ...
+
+ than to reach for those pattern-matching constructions.
+
+
+
+##Functions##
* In Haskell functions are assumed to be recursive, and their types and applications to values matching different patterns are each declared on different lines. So we have:
| x' when x' = 0 -> 0
| _ -> -1
-* In Haskell the equality comparison operator is `==`, and the non-equality operator is `/=`. In OCaml, `==` expresses "physical identity", which has no analogue in Haskell because Haskell has no mutable types. See our discussion of "Four grades of mutable involvement" in the [[Week9]] notes. In OCaml the operator corresponding to Haskell's `==` is just `=`, and the corresponding non-equality operator is `<>`.
+* In Haskell the equality comparison operator is `==`, and the non-equality operator is `/=`. In OCaml, `==` expresses "physical identity", which has no analogue in Haskell because Haskell has no mutable types. See our discussion of "Four grades of mutation involvement" in the [[Week9]] notes. In OCaml the operator corresponding to Haskell's `==` is just `=`, and the corresponding non-equality operator is `<>`.
* In both Haskell and OCaml, one can use many infix operators as prefix functions by parenthesizing them. So for instance:
will work in both languages. One notable exception is that in OCaml you can't do this with the list constructor `::`:
- # (::) 1 [1;2];;
- Error: Syntax error
- # (fun x xs -> x :: xs) 1 [1; 2];;
- - : int list = [1; 1; 2]
+ # (::) 1 [1;2];;
+ Error: Syntax error
+ # (fun x xs -> x :: xs) 1 [1; 2];;
+ - : int list = [1; 1; 2]
* Haskell also permits two further shortcuts here that OCaml has no analogue for. In Haskell, in addition to writing:
you can also write either of:
- (1 >) 2
- (> 2) 1
+ (2 >) 1
+ (> 1) 2
In OCaml one has to write these out longhand:
- (fun y -> 1 > y) 2;;
- (fun x -> x > 2) 1;;
+ (fun y -> 2 > y) 1;;
+ (fun x -> x > 1) 2;;
- Also, in Haskell, there's a special syntax for using what are ordinarily prefix functions into infix operators:
+ Also, in Haskell, there's a special syntax for using what are ordinarily prefix functions as infix operators:
Prelude> elem 1 [1, 2]
True
* Some functions are predefined in Haskell but not in OCaml. Here are OCaml definitions for some common ones:
- let id x = x;;
- let const x _ = x;;
- let flip f x y = f y x;;
- let curry (f : ('a, 'b) -> 'c) = fun x y -> f (x, y);;
- let uncurry (f : 'a -> 'b -> 'c) = fun (x, y) -> f x y;;
- let null lst = lst = [];;
+ let id x = x;;
+ let const x _ = x;;
+ let flip f x y = f y x;;
+ let curry (f : ('a, 'b) -> 'c) = fun x y -> f (x, y);;
+ let uncurry (f : 'a -> 'b -> 'c) = fun (x, y) -> f x y;;
+ let null lst = lst = [];;
- `fst` and `snd` (defined only on pairs) are provided in both languages. Haskell has `head` and `tail` for lists; these will raise an exception if applied to []. In OCaml the corresponding functions are `List.hd` and `List.tl`. Many other Haskell list functions like `length` are available in OCaml as `List.length`, but OCaml's standard libraries are leaner that Haskell's.
+ `fst` and `snd` (defined only on pairs) are provided in both languages. Haskell has `head` and `tail` for lists; these will raise an exception if applied to `[]`. In OCaml the corresponding functions are `List.hd` and `List.tl`. Many other Haskell list functions like `length` are available in OCaml as `List.length`, but OCaml's standard libraries are leaner that Haskell's.
* The `until` function in Haskell is used like this:
This can be defined in OCaml as:
- let rec until test f z =
- if test z then z else until test f (f z)
+ let rec until test f z =
+ if test z then z else until test f (f z)
-#Lazy or Eager#
+##Lazy or Eager##
* As we've mentioned several times, Haskell's evaluation is by default *lazy* or "call-by-need" (that's an efficient version of "call-by-name" that avoids computing the same results again and again). In some places Haskell will force evaluation to be *eager* or "strict". This is done in several different ways; the symbols `!` and `seq` are signs that it's being used.
# eval_later3;;
- : int lazy_t = lazy 1
- Notice in the last line the value is reported as being `lazy 1` instead of `<lazy>`. Since the value has once been forced, it won't ever need to be recomputed. The thunks are less efficient in this respect. Even though OCaml will now remember that `eval_later3` should be forced to, `eval_later3` is still type distinct from a plain `int`.
+ Notice in the last line the value is reported as being `lazy 1` instead of `<lazy>`. Since the value has once been forced, it won't ever need to be recomputed. The thunks are less efficient in this respect. Even though OCaml will now remember what `eval_later3` should be forced to, `eval_later3` is still type-distinct from a plain `int`.
-#Monads#
+##Monads##
Haskell has more built-in support for monads, but one can define the monads one needs in OCaml.
-* In our seminar, we've been calling one monadic operation `unit`, in Haskell the same operation is called `return`. We've been calling another monadic operation `bind`, used in prefix form, like this:
+* In our seminar, we've been calling one monadic operation `unit`; in Haskell the same operation is called `return`. We've been calling another monadic operation `bind`, used in prefix form, like this:
bind u f
u >>= f
- If you like this Haskell convention, you can define (>>=) in OCaml like this:
+ If you like this Haskell convention, you can define `>>=` in OCaml like this:
let (>>=) = bind;;
* Haskell also uses the operator `>>`, where `u >> v` means the same as `u >>= \_ -> v`.
-* In Haskell, one can generally just use plain `return` and `>>=` and the compiler will infer what monad you must be talking about from the surrounding type constraints. In OCaml, you generally need to be specific about which monad you're using. So in these notes, when mutiple monads are on the table, we've defined operations as `reader_unit` and `reader_bind`.
+* In Haskell, one can generally just use plain `return` and `>>=` and the interpreter will infer what monad you must be talking about from the surrounding type constraints. In OCaml, you generally need to be specific about which monad you're using. So in these notes, when mutiple monads are on the table, we've defined operations as `reader_unit` and `reader_bind`, and so on.
* Haskell has a special syntax for working conveniently with monads. It looks like this. Assume `u` `v` and `w` are values of some monadic type `M a`. Then `x` `y` and `z` will be variables of type `a`:
v >>= \ y ->
w >>= \ _ ->
let z = foo x y
- in unit z
+ in return z
which can be translated straightforwardly into OCaml.
+ For more details, see:
+
+ * [Haskell wikibook on do-notation](http://en.wikibooks.org/wiki/Haskell/do_Notation)
+ * [Yet Another Haskell Tutorial on do-notation](http://en.wikibooks.org/wiki/Haskell/YAHT/Monads#Do_Notation)
+ * [Do-notation considered harmful](http://www.haskell.org/haskellwiki/Do_notation_considered_harmful)
+
* If you like the Haskell do-notation, there's [a library](http://www.cas.mcmaster.ca/~carette/pa_monad/) you can compile and install to let you use something similar in OCaml.
* In order to do any printing, Haskell has to use a special `IO` monad. So programs will look like this: