Type Inference Languages: Standard ML, OCaml, Scala, Haskell

a side-by-side reference sheet

arithmetic and logic | strings | lists and tuples | data types | functions and scope | execution control | environment and i/o
modules | objects | repl | contact

standard ml (1990) ocaml (1996) scala (2003) haskell (1990)
version used SML NJ 110.71 3.11.0 2.8 6.12.1
version SML NJ displays version on startup $ ocaml -version $ scala -version $ ghc --version
interpreter $ ocaml foo.ml $ scala foo.scala $ runghc foo.hs
shebang none #!/usr/bin/env ocaml #!/bin/sh
exec scala $0 $@
#!/usr/bin/env runghc
bytecode compiler and interpreter $ ocamlc foo.ml -o foo
$ ocamlrun foo
$ scalac Foo.scala
$ scala Foo
native compiler $ ocamlopt foo.ml -o foo
$ ./foo
none $ ghc -o foo foo.hs
$ ./foo
library which is always imported Pervasives Prelude
statement terminator ; ;; ; or sometimes newline next line has equal or less indentation, or ;
blocks ( expr ; ) ( expr ; )
begin expr ; end
{ } offside rule or { }
single line comment none none
// comment
// comment -- comment
multi-line comment (* comment
another comment
(* comment
another comment
/* comment
another comment
{- comment
another comment
hello world print "hello world\n"; print_string "hello world\n";;
print_endline "hello world";;
printfn "hello world";;
println("hello world") main = putStrLn "hello world"
value val a = 3; let a = 3;; val a = 3 a = 3
variable val a = ref 3;
a := 4;
!a + 7;
let a = ref 3;;
a := 4;;
!a + 7;;
var a = 3
a = 4
a + 7
a <- return 3
unit () () () ()
conditional expression val x = 3;
if x < 0 then ~x else x;
let x = 3;;
if x < 0 then -x else x;;
val x = -3
if (x < 0) -x else x
x = 3
if x < 0 then -x else x
branch type mismatch compilation error:
if true then "hello" else 3;
compilation error:
if true then "hello" else 3;;
expression has type Any:
if (true) { "hello" } else { 3 }
compilation error:
if True then "hello" else 3
null NONE None null Nothing
type declaration 1: Double 1 :: Double
arithmetic and logic
standard ml ocaml scala haskell
true and false true false true false true false True False
boolean type bool bool Boolean Bool
logical operators andalso orelse not && || not && || ! && || not
relational operators = <> < > <= >= = <> < > <= >= == != < > <= >= == /= < > <= >=
numeric types int real int float
other numeric types:
int32 int64 nativeint
types of numeric literals:
Int Double
other numeric types:
Byte Short Float BigInt
Integer Double
integer operators + - * div mod + - * / mod
mod is an infix operator. F# uses % instead of mod
+ - * / % + - * div rem
div and rem are functions, not infix operators
integer exponentiation none none 2 ^ 3
largest integer int: 230-1 Int: 231-1
Long: 263-1
BigInt: none
integer overflow Overflow exception modular arithmetic modular arithmetic for all types except BigInt no overflow
integer division by zero raises Division_by_zero
java.lang.ArithmeticException Exception: divide by zero
integer division, remainder, float division 7 div 3
7 mod 3
real 7 / real 3
7 / 3
7 mod 3
float 7 /. float 3
7 / 3
7 % 3
(7: Double) / 3
div 7 3
rem 7 3
7 / 3
negative integer literal ~4 -4 -4 -4
float operators + - * / +. -. *. /.
+ - * /
+ - * / + - * /
float exponentiation Math.pow (2.0,3.0); 2.0 ** 3.0;; math.pow(2.0,3.0)
scala 2.7:
2.0 ** 3.0
float functions sqrt exp log sin cos tan asin acos atan atan2 math.sqrt math.exp math.log math.sin math.cos math.tan math.asin math.acos math.atan math.atan2
use Math in scala 2.7
sqrt exp log sin cos tan asin acos atan atan2
add integer and float real 3 + 7.0; float 3 +. 7.0;; 3 + 7.0 3 + 7.0
arithmetic truncation round 3.14
trunc 3.14
floor 3.14
ceil 3.14
truncate 3.14
floor 3.14 returns float
ceil 3.14 returns float
F# has round
3.14.floor returns Double
3.14.ceil returns Double
round 3.14
truncate 3.14
floor 3.14
ceiling 3.14
min and max min 1 2
max 1 2
math.min 1 2
math.max 1 2
use Math in scala 2.7
min 1 2
max 1 2
float overflow infinity Infinity Infinity
float division by zero infinity or neg_infinity Infinity or -Infinity Infinity or -Infinity
sqrt -2.0 Math.sqrt ~2.0: nan sqrt (-2.0): nan math.sqrt(-2.0): NaN sqrt (-2.0): NaN
random integer, random float, normal float Random.int 100
Random.float 1.0
val r = new java.util.Random
import System.Random
getStdRandom (randomR (0, 99))
getStdRandom (randomR (0.0, 1.0))
bit operators 1 lsl 4
1 lsr 4
1 land 3
1 lor 3
1 lxor 3
lnot 1
1 << 4
1 >> 4
1 & 3
1 | 3
1 ^ 3
~ 1
import Data.Bits
x = 1 :: Integer
y = 3 :: Integer
shiftL x 4
shiftR x 4
x .&. y
x .|. y
xor x y
complement x
standard ml ocaml scala haskell
literal "Hello, World!" "Hello, World!" "Hello, World!" "Hello, World!"
string and char types string char string char java.lang.String Char String Char
string escapes \000 \a \b \f \n \r \t \v \040 \b \n \r \t \" \' \\ \040 \x7F \b \f \n \r \t \" \' \uhhhh \o \oo \ooo \0 \a \b \f \n \r \t \v \" \& \' \\ \x3bb \955
concatenation "Hello" ^ ", " ^ "World!" "Hello" ^ ", " ^ "World!"
"Hello" + ", " + "World!"
"Hello" + ", " + "World!" "Hello" ++ ", " ++ "World!"
length size "hello" String.length "hello"
"hello".length length "hello"
index of substring "hello".indexOf("hell")
extract substring substring ("hello",0,4) String.sub "hello" 0 4 "hello".substring(0,4) drop 0 (take 4 "hello")
number to string Int.toString 3
Real.toString 3.14
string_of int 3
string_of_float 3.14
show 3
show 3.14
string to number int_of_string "3"
float_of_string "3.14"
raises NumberFormatException if string doesn't completely parse
read "3"::Integer
read "3.14"::Double
raises exception if string doesn't completely parse
case manipulation String.uppercase "hello"
String.lowercase "HELLO"
String.capitalize "hello"
character access String.sub ("hello",0) "hello".[0] "hello"(0) "hello" !! 0
character literal #"h" 'h' 'h' 'h'
chr and ord ord #"a"
chr 97
Char.code 'a'
Char.chr 97
Char.ord 'a'
Char.chr 97
lists and tuples
standard ml ocaml scala haskell
list literal [1,2,3] [1;2;3] List(1,2,3) [1,2,3]
list element access List.nth ([1,2,3],0) List.nth [1;2;3] 0 List(1,2,3)(0) [1,2,3] !! 0
list head List.hd [1,2,3] List.hd [1;2;3]
List.head [1;2;3]
List(1,2,3).head head [1,2,3]
list tail List.tl [1,2,3] List.tl [1;2;3]
List.tail [1;2;3]
List(1,2,3).tail tail [1,2,3]
cons 1::[2,3] 1::[2;3] 1 :: List(2,3) 1 : [2,3]
reverse List.rev [1,2,3] List.rev [1;2;3] List(1,2,3).reverse reverse [1,2,3]
sort List.sort min [1;3;2;4]
List.sort max [1;3;2;4]
List.sort [1,3,2,4]
append [1,2] @ [3,4] [1;2] @ [3;4]
List.append [1;2] [3;4]
List(1,2) ::: List(3,4)
List(1,2) ++ List(3,4)
[1,2] ++ [3,4]
concatenate list of lists List.concat [[1,2],[3,4]] List.concat [[1;2];[3;4]] List(List(1,2), List(3,4)).flatten
length List.length [1,2,3] List.length [1;2;3] List(1,2,3).length length [1,2,3]
each fun f i = print ((Int.toString i) ^ "\n");
List.app f [1,2,3];
let f i = print_endline (string_of_int i);;
List.iter f [1;2;3];;
List(1,2,3).foreach(i=>println(i)) mapM_ print [1,2,3]
map List.map (fn (x) => x + 2) [1,2,3]; List.map (( * ) 2) [1;2;3];; List(1,2,3).map(x=>2*x)
map (\x -> x * x) [1,2,3]
filter List.filter (fn (x) => x > 2) [1,2,3]; List.filter ((<) 2) [1;2;3];; List(1,2,3).filter(x=>x>2) filter (\x -> x > 2) [1,2,3]
fold left List.foldl (op +) 0 [1,2,3]; List.fold_left (+) 0 [1;2;3];;
List.fold (-) 0 [1;2;3];;
foldl (+) 0 [1,2,3]
fold right List.foldr (op -) 0 [1,2,3]; List.fold_right (-) [1;2;3] 0;; List(1,2,3).foldRight(0)(_-_) foldr (-) 0 [1,2,3]
tuple (1,"hello",true) (1,"hello",true) (1,"hello",true) (1,"hello",True)
tuple element access #1 (1,"hello",true) match (1,"hello",true) with _,x,_ -> x (1,"hello",true)._1 (\(a, _, _) -> a) (1,"hello",True)
pair element access #1 (12,"December")
#2 (12,"December")
fst (12, "December")
snd (12, "December")
(12, "December")._1
(12, "December")._2
fst (12, "December")
snd (12, "December")
data types
standard ml ocaml scala haskell
algebraic sum type datatype color = Red | Green | Blue type color = Red | Green | Blue abstract class Color
case object Red extends Color
case object Blue extends Color
case object Green extends Color
data Color = Red | Green | Blue
algebraic product type type customer = {id:int, name:string, address:string} type customer = {id:int; name:string; address:string} case class Customer(id: Int, name: String, address: String) data CustomerType = Customer {
  customerId :: Integer,
  name :: String,
  address :: String }
algebraic product literal {id=7, name="John", address="Topeka,KS"} {id=7; name="John"; address="Topeka,KS"} Customer(7,"John","Topeka,KS")
scala 2.8:
Customer(id=7, name="John", address="Topeka,KS")
Customer {
  address="Topeka, KS" }
type synonym type name = string type name = string type Name = String type Name = String
type constructor with argument datatype special_int = SpecialInt of int;
val x = SpecialInt 7;
type special_int = SpecialInt of int;;
let x = SpecialInt 7;;
class SpecialInt(x: Int)
val x = new SpecialInt(7)
data SpecialIntType = SpecialInt Integer
x = SpecialInt 7
type constructor with tuple argument datatype int_pair = IntPair of int * int;
val y = IntPair (7,11);
type int_pair = IntPair of int * int;;
let y = IntPair ( 7, 11 );;
class IntPair(a: Int, b: Int)
val x = new IntPair(7,11)
data IntPairType = IntPair Integer Integer
y = IntPair 7 11
parametric type constructor datatype ('a,'b) twosome = Twosome of 'a * 'b;
val z = Twosome ("pi",3.14);
type ('a,'b) twosome = Twosome of 'a * 'b;;
let z = Twosome ("pi",3.14);;
class Twosome[A,B](a: A, b: B)
val p = new Twosome("pi",3.14)
data TwosomeType a b = Twosome a b
z = Twosome ("pi", 3.14)
recursive type datatype binary_tree = Leaf of int | Tree of binary_tree * binary_tree; type binary_tree = Leaf of int | Tree of binary_tree * binary_tree;; abstract class BinaryTree
case class Tree(left: BinaryTree, right: BinaryTree) extends BinaryTree
case class Leaf(x: Int) extends BinaryTree
data BinaryTree = Leaf Integer | Tree BinaryTree BinaryTree
match/with case/of val c = Red;
case c of Red => "red" | Blue => "blue" | Green => "green";
let c = Red;;
match c with Red -> "red" | Blue -> "blue" | Green -> "green";;
val c:Color = Red;
c match { case Red => "red"; case Green => "green"; case Blue => "blue" }
c = Red
case c of Red -> "red"
  Green -> "green"
  Blue -> "blue"
match guard none, use if match i with j when i < 0 -> -j | j -> j;; match { case i: Int if i < 0 => - i; case i: Int => i } none, use if or piecewise function definition
match catchall fun to_s c = case c of Red => "red" | _ => "not red"; let to_s c = match c with Red -> "red" | _ -> "not red";;
to_s Green;;
val c : Color = Green
c match { case Red => "red"; case _ => "not red" }
c = Green
case c of Red -> "red"; _ -> "not red"
null type type list_option_int = int option list;
val list = [SOME 3,NONE, SOME ~4];
type list_option_int = int option list;;
let list = [Some 3; None; Some (-4)];;
val list = List(Some(3),null,Some(-4)) list = [Just(3),Nothing,Just(-4)]
functions and scope
standard ml ocaml scala haskell
let ... in ... val z =
  val x = 3.0
  val y = 2.0 * x
  x * y
let z =
let x = 3.0 in
let y = 2.0 *. x in
x *. y;;
val z = {
        val x = 3.0
        val y = 2.0 * x
        x * y
z = let x = 3.0
      y = 2.0 * x
  in x * y
where none none none z = x * y
  where x = 3.0
        y = 2.0 * x
function fun average a b = ( a + b ) / 2.0; let average a b = ( a +. b ) /. 2.0;; def average(a: Double,b: Double) = (a + b) / 2.0
if body not an expression or if return type not inferable:
def average(a: Double,b: Double): Double = { (a + b) / 2.0 }
average a b = (a + b) / 2.0
lambda fn x => fn y => (x+y) / 2.0 fun x -> fun y -> (x +. y) /. 2.0 (x:Double, y:Double) => (x+y) / 2.0 \x y -> (x+y) / 2.0
piecewise defined function val to_s = fn Red => "red"
  | Green => "green"
  | Blue => "blue";
let to_s = function Red -> "red"
  | Green -> "green"
  | Blue -> "blue";;
none to_s Red = "red"
to_s Green = "green"
to_s Blue = "blue"
recursive function fun range a b =
if a > b then []
else a :: range (a+1) b;
let rec range a b =
if a > b then []
else a :: range (a+1) b;;
def range(a:Int, b:Int): List[Int] = if (a > b) List() else a :: range(a+1,b) range a b = if a > b then [] else a : range (a+1) b
mutually-recursive-functions let rec even n = if n = 0 then true else odd (n-1)
and odd n = if n = 0 then false else even (n-1);;
named parameter let subtract ~m ~s = m - s;;
subtract ~s: 3 ~m: 7;;
scala 2.8:
def subtract(m: Int, s: Int) = m - s
subtract(s=3, m=7)
named parameter default value let logarithm ?(base = (exp 1.0)) x = log x /. (log base);;
logarithm 2.718;;
logarithm ~base: 2.0 10.0;;
scala 2.8:
def logarithm( x: Double, base: Double = math.exp(1)) = math.log(x) / math.log(base)
logarithm(10, base=2)
infix operator in prefix position (op * ) (3,4) ( * ) 3 4;; none ( * ) 3 4
function in infix position none unary methods can be used as binary operators add x y = x + y
3 `add` 4
currying fun plus x y = x + y;
val plus2 = plus 2;
plus2 7;
let plus2 = (+) 2;; def plus(x: Int)(y: Int) = x + y
def plus2 = plus(2) _
plus2 = (+) 2
composition f x = x + 2
g x = x * 3
(f . g ) 4
function composition operator fun double x = 2 * x;
val quadruple = double o double;
none none double x = 2 * x
quadruple x = double . double
lazy evaluation let first_arg x y = x;;
first_arg 7 (lazy (1/0) );;
def first_arg(x: => Double, y: => Double): Double = x
first_arg(7, 1/0)
lazy evaluation is default:
first_arg x y = x
first_arg 7 (error "bam!")
strict evaluation first_arg x y = seq y x
first_arg 7 (error "bam!")
execution control
standard ml ocaml scala haskell
if if x > 0 then
  print "pos\n"
if x > 0 then
  print_string "pos\n";;
if ( x > 0 )
if x > 0
  then putStrLn "pos"
  else return ()
if else-if else if x > 0 then print "pos" else if x < 0 then print "neg" else print "zero"; if x > 0 then
  print_string "pos"
else if x < 0 then
  print_string "neg"
  print_string "zero";;
if (x > 0)
else if (x < 0)
if x > 0
  then putStrLn "pos"
  else if x < 0
    then putStrLn "neg"
    else putStrLn "zero"
sequencing print_string "one\n";
print_string "two\n";
print_string "three\n"
  putStrLn "one"
  putStrLn "two"
  putStrLn "three"
while let i = ref 0;;
while !i < 10 do
  print_string (string_of_int !i);
  i := !i + 1
var i = 0
while (i<10) {
  printf("%d\n", i)
  i = i+1
for for i = 1 to 10 do
  let s = string_of_int i in
  print_string (s ^ "\n")
for (i <- 1 to 10)
for in reverse for i = 10 downto 1 do
  let s = string_of_int i in
  print_string (s ^ "\n")
none none
list iteration none for (i <- List.range(1, 11).reverse)
loop let rec loop i =
  if i <= 10 then begin
    print_endline (string_of_int i);
    loop (i+1)
  end in
loop 0;;
none none
raise error raise (Failure "bam!");;
failwith "bam!";;
throw new Exception("bam!") error "bam!"
handle error let x = try 1 / 0 with Division_by_zero -> 0;; import java.lang._
val x = try {
  1 / 0
} catch {
  case e: ArithmeticException => 0
type of exceptions exn
user defined exception exception Foo of string;;
raise (Foo "invalid input");;
standard exceptions Division_by_zero
Failure string
Invalid_argument string
Match_failure (string, int, int)
Assert_failure (string, int, int)
assert assert(1 = 0);; assert(1==0)
environment and i/o
standard ml ocaml scala haskell
command line args for i = 0 to Array.length Sys.argv - 1 do
  print_endline i Sys.argv.(i)
object Test {
  def main(args: Array[String]) {
    for (arg <- args)
import System
printArgs args = do
  if length args == 0
    then return ()
    else do
      putStrLn (head args)
      printArgs (tail args)
main = do
  a <- getArgs
  printArgs a
read from file fun displayFile(file: string) =
    val f = TextIO.openIn file
    fun iter(s: string option) =
    case s of
    NONE =>
      (TextIO.closeIn f)
    | SOME(line) =>
      (print line;
      iter(TextIO.inputLine f))
    iter(TextIO.inputLine f)
let ic = open_in "/etc/passwd" in
let line = input_line ic in
print_endline line;;
import scala.io.Source
val src = Source.fromFile("/etc/passwd")
for (line <- src.getLines)
import IO
readAndPrintLines h = do
  eof <- hIsEOF h
  if eof
    then return ()
    else do
      line <- hGetLine h
      putStrLn line
      readAndPrintLines h
main = do
  h <- openFile "/etc/passwd" ReadMode
  readAndPrintLines h
write to file val file = "/tmp/test-sml";
val f = TextIO.openOut file;
TextIO.output(f, "hello out\n");
TextIO.closeOut f;
open Printf
let oc = open_out "/tmp/test-ocaml" in
fprintf oc "hello out\n";
close_out oc;;
val out = new java.io.FileWriter("/tmp/test-scala")
out.write("hello out\n")
s = "hello out\n"
f = "/tmp/test-haskell"
main = writeFile f s
standard ml ocaml scala haskell
module example Baz.scala
package Foo.Bar;
class Baz {
  def say() { println("hello"); }

import Foo.Bar.Baz;
object Main {
  def main(args : Array[String]) {
    val baz = new Baz;

to compile and run
$ scalac Baz.scala
$ scalac Main.scala
$ scala Main
module Foo.Bar where
  data Baz = Baz
  say Baz = putStrLn "hello"

module Main where
import Foo.Bar
baz = Baz
main = say baz

to compile and run
$ ghc -c Foo/Bar.hs
$ ghc Main.hs
$ ./Main
namespaces values, constructors, type variables, type constructors, type classes, modules
file name restrictions module Foo.Bar must be in Foo.ml none module Foo.Bar must be in Foo/Bar.hs
import open Graphics;; import Data.Bytestring
module creation put code in file MODULE_NAME.ml
module alias module Gr = Graphics;; import qualified Data.Bytestring as B
module separator . .
submodule in A.ml:
module B =
  val display_instruction : unit -> unit
end =
  let msg = "attack"
  let display_instruction () = print_endline msg
in client source:
inspect module module M = List;;
standard ml ocaml scala haskell
class definition class counter = object
  val mutable n = 0
  method incr = n <- n+1
  method get = n
class Counter {
  private var n = 0
  def incr(): Unit = { n = n+1 }
  def get(): Int = { n }
object creation let c = new counter;; val c = new Counter
method invocation c#incr;;
field access none
standard ml ocaml scala haskell
repl $ sml $ ocaml
to start F# repl, highlight code in visual studio and press ALT+ENTER
$ scala $ ghci
repl limitations Must use let to define values and functions; when defining functions with multiple equations the equations must be separated by semicolons; the clauses of case/of statements must be separated by semicolons; it is not possible to define data types.
repl last value it none
res0, res1, … it
help none :help :?
inspect type repl displays the type of any expression entered repl displays the type of any expression entered let a = 3
:type a
load source file use "hello.ml"; #use "hello";; :edit hello.hs
:load hello
search path #directory "libdir";;
set search path on command line ocaml -Ilibdir
__________________________________________ __________________________________________ __________________________________________ __________________________________________

version used

Versions used to test the code samples in the cheat sheet.


How to get the version.


How to run the interpreter on a file of source code.


Scala can be run "Perl style" like this:

scala foo.scala

or "Java style" like this:

scala Foo

When the code is run "Java style", the code to be executed must be in the main method of an object with the same name as the file. When the code is run "Perl style" the statements o be executed should be at the top level outside of any object, class, or method.


How to use the interpreter in a shebang.


To use scala as a shebang, it is necessary to terminate the shell script portion of the script with !#

exec scala $0 $@
println("hello world")

bytecode compiler and interpreter

How to compile source to bytecode and run it.


It is not necessary to invoke ocamlrun on the bytecode; the bytecode can be executed directly because the bytecode compiler puts a shebang invocation at the top of the file.

native compiler

How to compile source to native code and run it.

library which is always imported

The name of the library containing the types and functions which are always available.

statement terminator


;; is the ocaml statement separator. It is not necessary at the end of the line if the following line starts with an open or let keyword or at the end of the file.


Scala infers the existence of a semicolon at the end of a newline terminated line if none of the following conditions hold:

  • the line ends with a infix operator, including a period
  • the following line begins with a word that is not legal at the start of a statement
  • the line ends inside parens or square brackets, neither of which can contain multiple statements


single line comment

multi-line comment


(* *) style comments can be nested.

hello world


In order for a scala program to be compiled and run, there must be a top level object with a main method:

object Hello {
  def main(args: Array[String]) {
    println("hello world")





Arithmetic and Logic

true and false

boolean type

logical operators

relational operators


Comparisons between reals with = and <> are not permitted in SML/NJ, but are permitted in Alice.

numeric types


Arithmetic operators can be used on values of type Char, which then behaves as a 16 bit unsigned integer. Integer literals are of type Int unless suffixed with L:

scala> 9223372036854775807L
res24: Long = 9223372036854775807

scala> 9223372036854775807 
<console>:1: error: integer number too large

integer operators

integer exponentiation


How to define a function which computes the power of an integer:

let integer_exponent b e =
  let rec aux x i =
    if i = e then x else aux (x * b) (i + 1)
  aux 1 0;;

largest integer


The largest integers are available in the constants Int.MaxValue and Long.MaxValue.

integer overflow

integer division by zero

integer division, remainder, float division

negative integer literal

float operators

float exponentiation

float functions

add integer and float


OCaml also can convert a integer to float with float_of_int.

[arithmetic truncation]

arithmetic truncation

min and max

float overflow

float division by zero

sqrt -2.0

random integer, uniform float, normal float


The scala native math (named Math before Scala 2.8) library has a function for returning a random double in uniform distribution on the unit interval:


bit operators


Also has operators which perform arithmetic shift: asl and asr. When performing an arithmetic shift, the sign of the integer is preserved.


Haskell does not assign a default size or type to numeric literals. Hence numeric literals must have their type declared for bit operations to be performed on them.





F# supports (with a warning) the ^ operator for compatibility with OCaml.

string escapes


Unicode escapes might not work when scala is installed on a Mac because the encoding is set by default to MacRoman:

scala> System.getProperty("file.encoding")
res0: java.lang.String = MacRoman

This can be fixed by passing the following flag to java in the scala shell script:


Lists and Tuples

list literal

list element element

list head


Supports List.hd (with a warning) to be compatible with OCaml.


Supports List.tl (with a warning) to be compatible with OCaml.


tuple element

Data Types

algebraic sum type

algebraic product type

type synonym

Functions and Scope

let … in …

How to define local variables.


OCaml uses let to define a value and let with in to define values in a local scope. OCaml follows the usage of the original dialect of ML in this respect.

OCaml can define multiple values with a single let and in by conjoining the definitions with and. The defintiions are performed in parallel, so later definitions cannot use the earlier definitions:

let z = 
let x = 3
and y = 4 in
x * y;;


Blocks can be used in Scala exclusively to define scope. Furthermore blocks are expressions and evaluate to their last statement.


Haskell uses let with in to define local scope. In addition, ghci uses let without in to define values.


How to define local variables with definitions after the expression that uses them.


How to define a function.


Recursive functions must have their return type declared because the Scala compiler cannot infer it.


How to define an anonymous function.

piecewise defined function

How to define a function with multiple equations and matching on the arguments.

recursive function

How to define a recursive function.

mutually recursive functions

How to define two functions which call each other. Mutual recursion can be eliminated by inlining the second function inside the first function. The first function is then recursive and can be defined independently of the second function.

named parameter

How to define and invoke a function with named parameters.


Multiple parameters can share a name. In the function definition colons are used to rename the parameters for use in the function body.

let add_xs ~x:x1 ~x:x2 = x1 + x2;;
add_xs ~x:3 ~x:7;;

named parameter default value

How to make named parameters optional by providing a default value in the definition.


For a named parameter to be optional, it must be following by an unnamed parameter in the definition. This permits the parser to unambiguously determine if the optional parameter has been provided or not. If the optional parameter is not followed by an unnamed parameter in the definition, then named parameter is not optional. If the function is invoked without the parameter, it returns a curried version of the function which expects the missing named parameter as an argument.

infix operator in prefix position

How to invoke an infix operator in prefix position.

function in infix position

How to invoke a function in infix position.


How to create a curried function by providing values for some of the arguments of a function.


Functions can only be curried if they are defined with special syntax. Functions defined with this syntax must be invoked with a pair of parens for each argument.

function composition operator

An operator which takes two functions as arguments and returns a function constructed from them by composition.

lazy evaluation

How to evaluate the arguments to a function in a lazy manner.

standard ml:

Alice provides the lazy function. It is up to the caller to specify that the argument is to be evaluated lazily.


OCaml provides the lazy function. It is up to the caller to specify that the argument is to evaluated lazily.


Functions can be defined to evaluate their arugments lazily by putting a => operator between the colon and the type of the parameter in the function signature.


Haskell evaluates arguments lazily by default.

strict evaluation


The seq function evaluates its first argument and then returns the second argument.

Execution Control


if else-if else




There is no break or continue statement. In addition to using references, it is possible to use exceptions to break out of a while loop.


How to loop over a range of integers.


How to define a for loop in SML:

datatype for = to of int * int
             | downto of int * int

infix to downto

val for =
    fn lo to up =>
       (fn f => let fun loop lo = if lo > up then ()
                                  else (f lo; loop (lo+1))
                in loop lo end)
     | up downto lo =>
       (fn f => let fun loop up = if up < lo then ()
                                  else (f up; loop (up-1))
                in loop up end)

How to use the for loop:

for (1 to 9)
    (fn i => print (Int.toString i))

for (9 downto 1)
    (fn i => print (Int.toString i))

for in reverse

How to iterate over a reversed range of integers.

list iteration

How to iterate over the members of a list.


An infinite loop.

raise error

How to raise an error.

handle error

How to handle an error.

Environment and I/O


module example


file name restrictions


module creation

module alias

module separator


inspect module




repl limitations

repl last value



The OCaml top level provides these directives:

#cd "DIRNAME";;
#directory "DIRNAME";;
#install_printer PRINTER_NAME;;
#label BOOL;;
#load "FILENAME";;
#print_depth N;;
#print_length N;;
#remove_printer PRINTER_NAME;;
#untrace FUNCTION_NAME;;
#use "FILENAME";;
#warnings "WARNINGS_LIST";;

inspect type

load source file

search path

set search path on command line


Programming in Standard ML '97
Standard ML Basis Library
Notes on Programmming in SML/NJ (pdf)
Syntax Across Languages: SML
MLton Documentation
Alice Homepage


The Objective-Caml system, release 3.11
Objective CAML Tutorial
Introduction to Objective Caml (pdf) Hickey
Standard ML and Objective Caml, Side by Side
Caml Programming Guidelines
Syntax Across Languages: OCaml
The F# Survival Guide


The Scala Language Specification (pdf)
Scala 2.7.7 API
Java 1.6 API


Haskell 98 Language and Libraries

What follows is an explanation of traits which make Haskell different from OCaml and Scala.

lazy evaluation of arguments by default

In Haskell as in most languages it is possible to provide expressions as arguments to a function when it is invoked. In most other languages the expressions are evaluated before the invoked function is executed. In Haskell the expressions are wrapped in closures called thunks and passed to the executed function which evaluates them as needed. As a result the following Haskell code runs and evaluates to 7, whereas the equivalent code in most other language would raise a division by zero error:

first_arg x y = x
first_arg 7 (1/0)

In Lisp terminology, a functions which evaluates its arguments lazily is called an expr or a fexpr. A function which performs strict evaluation is called a subr or a fsubr. exprs and fexprs were used in old Lisp dialects to implement conditional expressions such as if and cond. The terminology is still encoutered, though in modern Lisp dialects if and cond are implemented with macros.

type system identifies pure functions

The Haskell type system distinguishes between pure and impure functions. Impure functions are called actions and usually have a type of the form IO t where t is a type variable. The main routine has type IO ().

no loops

OCaml, Scala, and Haskell all perform tail call optimization so that loops can be replaced with equally efficient code that performs recursion. Actually, in the case of Haskell, loops must be replaced with recursion because Haskell doesn't provide any functions or keywords to implement loops.

indentation defines blocks

main function marks initial execution point


Lambda Calculus

An Introduction to Lambda Calculus (pdf) Barendregt 1994

Developed by Alonzo Church in the 1930s, the lambda calculus is a model of computation. Church used it in 1936 to show that arithmetic as formalized by a Peano system is undecidable; that is, there are theorems which are true, but which cannot be shown to be true using the axioms of arithmetic.

As a model of computation, the lambda calculus is equal in expressive power to Turing machines. No computational models have been discovered which have greater expressive power than the lambda calculus or Turing machines. The unprovable Church-Turing thesis states that there are none.

Statements in the lambda calculus are built up with two operations: abstraction and application. Abstraction can be interpreted as defining a mathematical function, and application can be interpreted as use of a mathematical function.

Turing machines, in contrast, consist of a tape, a head, a table of instructions, and a state register. These concepts correspond to the memory, the address of the next instruction to execute, the set of machine instructions, and the registers of a computer with the von Neumann architecture.

The lambda caculus can treat functions as data. Indeed, in pure lambda calculus, functions are the only kind of data there is. The lambda calculus can nevertheless model the natural numbers by assigning a function to represent each natural number. These functions are the Church numerals. Functions can also be assigned to represent the values true and false, and the logical operators and, or, and not; these functions are the Church booleans.

The Kleene-Rosser paradox, obtaining by defining k=(λ x.~(xx)) and then applying k to itself, shows that the lambda calculus cannot be used as a basis for mathematics in a manner similar to first order predicate logic and the Zermelo axioms of set theory. Typed systems of lambda calculus attempt to address this deficiency by assigning types to functions and data and forbidding application of a function to a datum if the types do not match. Although typed systems can avoid the Kleene-Rosser paradox, they are not as expressive as the untyped lambda calculus.

Assigning a type to a function in the lambda calculus is comparable to assigning a type to a variable or a region of memory in a C program. In the case of the C program, the type remembers that the memory contains data that should be interpreted as, say, an integer and not a floating point number or string data. Assigning types to memory thus prevents programming errors that would result in nonsense. Types can also prevent programs from being written that would crash because of incorrect use of memory containing the address of another memory location.

Typed lambda calculi are central to the Curry-Howard correspondence, which is a one-to-one relationship between mathematical proofs and a class of computer programs.

Functional Programming

The Next 700 Programming Languages (pdf) Landin 1966

Landin's 1966 article introduces a theoretical core for future languages called ISWIM. Languages built on this core would have a "functional" subset of features, and portions of the program written entirely in the functional subset could be reasoned about in the same manner that mathematicians reason about algebraic equations. In particular, the principle of substitution holds: when two different expressions yield the same value, one expression can be substituted for the other with no change in result.

Landin's article shows that computer scientists were already distinguishing between imperative programming and functional programming. Landin isolates two features of imperative languages which invalidate the applicability of substitution: jumps and assignment.

TODO: referential transparency. In algebraic equations. In lambda calculus. Order of calculuation not significant.

Functional programming got its start with Algol, which introduced lexical scope, and Lisp 1.5, which put an emphasis on programming with expressions instead of statements. ISWIM employs the let and where keywords for lexical scope, where differing from let in that it places the definitions after the expression that uses them. The language CPL, described in 1963 and unimplemented as of 1966, was already using where in this manner. The language BASIC developed at Dartmouth in 1964 used let for dynamic assignment. let was adoped by future dialects of Lisp.

Landin notes that many Algol programmers were making it a practice to eliminate jumps or the goto statement where possible. In 1968 Dijkstra would write an influential letter to the ACM entitled "GOTO considered harmful".

Landin uses let rec and where rec for defining recursive functions. This notation persists in OCaml but not SML. Landin also proposed using indentation, the so-called off-sides rule, for defining blocks, a practice that was picked up by Haskell but not the ML dialects.

TODO: the development of Scheme

ML History

Edinburgh LCF Milner 1978
How ML Evolved (pdf) Milner 1982

Milner etal. began work on a theorem proving assistant called LCF at Stanford in 1971. Work continued at Edinburgh in 1974. Milner needed a language which supported higher order functions; i.e. functions which accept functions as values. He chose ISWIM as the basis for his language. Milner needed the language to be typed so that theorems being proved could be distinguished from the tactics for proving theorems.

Typed, higher order functions have complex declarations, and Milner developed and described Algorithm W in 1978 for the inference of type. Milner later learned that some of his results had already been arrived at by Hindley and Church.

ML was initally implemented in the Stanford dialect of Lisp. Luca Cardelli implemented a compiled version of ML in 1981. Specifically, a compiler implemented in Pascal took the ML source and converted it to an intermediate form which could be executed on an abstract machine implemented in assembler. The compiler and abstract machine were available for VAX machines running Unix. All type checks took place in the compiler.

Standard ML History

Hope: an Experimental Applicative Language (pdf) Burstall MacQueen Sannella 1980
The Definition of Standard ML (Revised) Milner etal 1997
SML '97 Conversion Guide MacQueeen 1999

The original version of ML was somewhat vaguely specified, and Cardelli's Pascal implementation introduced some changes and improvements. Furthermore, another statically typed functional language called Hope appeared in 1980 which introduced algebraic data types and pattern matching. Milner realized that ML had value independent of its role in the theorem proving assistant LCF, and that it would benefit from additions and standardization.

Hence Milner published "A Proposal for Standard ML" in December 1983. The article was followed by a three day conference in June 1984. Numerous changes were made to the language, and MacQueen designed a module system for ML. The formal description of Standard ML was published in book form in 1990 and a revision published in book form in 1997.

Polymorphism Newsletter

The Polymorphism Newsletter was edited by Cardelli and MacQueen, at the time both working at Bell Labs.

Polymorphism I.0 (pdf) Cardelli and MacQueen, Nov 1982

  • Known VAX-ML System Locations

Polymorphism I.1 (pdf) Cardelli and MacQueen, Jan 1983

  • How ML Evolved, Milner
  • Unambiguous Syntax for ML, Sethi
  • The Functional Abstract Machine, Cardelli
  • SERC ML/LCF/Hope Meeting at Rutherford Labs

Polymorphism I.2 (pdf), Cardelli and MacQueen, Apr 1983

  • Poly Report, Matthews
  • Introduction to Poly, Matthews
  • Ponder and its Type System, Fairbairn
  • Recent Developments in LCF: Examples of Structural Induction, Paulson
  • Rewriting in Cambridge LCF, Paulson
  • A Revised Logic PPLambda: A Reference Manual, Paulson
  • ML Under Eunice, Kitchen and Linch

Polymorphism I.3 (pdf) Cardelli and MacQueen, Dec 1983

  • A Proposal for Standard ML, Milner
  • ML under Unix, Cardelli
  • Modules for ML, MacQueen
  • Stream Input/Output, Cardelli

Polymorphism II.1 (pdf) Cardelli and MacQueen, Jan 1985

  • Report on the Standard ML Meeting, MacQueen
  • Basic Polymorphic Type Checking, Cardelli
  • Annotated Bibliography on LCF, Paulson

Polymorphism II.2 (pdf) MacQueen, Oct 1985

  • The Standard ML Core Language, Milner
  • Modules for ML, MacQueen
  • Standard ML Input/Output, Harper

SML Implementations

Standard ML of New Jersey

Standard ML of New Jersey
Rabbit: A Compiler for Scheme Steele 1978
Caml Trading Talk at CMU (video) Minsky 2009, opinions on SML implementations at 51:10
Compiling with Continuations Appel 1991

MacQueen and Appel started work on SMLNJ in 1986, and they spent over five years developing a complete programming environment for SML. The SMLNJ compiler reduces SML source code to an intermediate representation which uses continuation passing style (CPS). CPS was first used for a Scheme compiler written by Steele in 1978, and since CPS can be expressed in Scheme, the intermediate representation used by the Scheme compiler was a subset of Scheme. SMLNJ uses ML data types to represent CPS expressions, which provide type safety not available to a Scheme IR.

SMLNJ provides both a compiler and an interpreter. It is still actively being worked on; the version 110.72 was releases in February 2010.


MLton Performance Compared to Other ML Compilers

MLton is an SML to C compiler. Work was initiated by Stephen Weeks in 1997, and MLton was first released in 1999. MLton is a "whole program compiler". By 2002 the ability to generate native code had been added.

MLton appears to be the fastest SML compiler. The most recent release (as of May 2010) was in August 2007.





Moscow ML

Moscow ML

Caml History

A brief History of Caml
Categorical Abstract Machine (CAM)

INRIA became interested in the ML language as early as 1980. The first version of Caml was released in 1987. The name refers to the Categorical Abstract Machine, a model of computation of interest to the researchers at INRIA. The first version of Caml, retroactively known as Caml Heavy, compiled to the LLM3 virtual machine used by Le Lisp. In 1991 Xavier Leroy released Caml Light which had a bytecode interpreter written in C. In 1996 OCaml was released. The name referred to the object system which was added to Caml; the release included a native code compiler.

Don Syme worked on the generics for C# which were introduced in Visual Studio 2005. F# has been available as a download since 2007 and is included with Visual Studio 2010. F# is close to OCaml; it had been preceded by an attempt to bring Haskell to .NET which was put aside because too much monadic code was required to interact with the .NET libraries. F# was also preceded by an SML port to .NET.

Scala History

The Origins of Scala Odersky 2009
Scala Version History: 2.5 thru 2.7
Scala Version History: 1.0 thru 2.4

Martin Odersky and Phil Wadler developed a functional language called Pizza for the JVM in 1996. Pizza has generics — what would eventually become the generics in Java 5 — as well as higher order functions and pattern matching. Odersky next developed a JVM language called Funnel which is based on the join-calculus.

Odersky's third language was Scala; the first version was released in 2003. The Scala compiler was rewritten in Scala in 2006.

Haskell History

A History of Haskell (pdf) Hudak Hughes Jones Wadler 2007
Notions of computations and monads (pdf) Moggi 1991
Comprehending Mondas (pdf) Wadler 1992
Arrows wikipedia

David Turner implemented a pure version of ISWIM in 1972, and he made the language (called SASL) non-strict or lazy in 1976. He followed this language up with KRC (1981) which contained pattern matching, guards, and list comprehensions. This in turn was followed by Miranda (1985), which had polymorphic types in the manner of ML.

Miranda is closed source. The FP community resolved to design an open source lazy functional language in 1987, and the new language was specified in the Haskell Report (1990) and the Haskell 98 Report (1999). The Glasgow Haskell Compiler was first available as a beta version in 1991.

A notable distinction between Miranda and Haskell is the use of category theory, in particular monads, in the type system to distinguish pure and impure functions. Arrows are a generalization of monads.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License