search

swyxio / swyxdotio

This is the repo for swyx's blog - Blog content is created in github issues, then posted on swyx.io as blog pages! Comment/watch to follow along my blog within GitHub
https://swyx.io
MIT License
342 stars 45 forks source link

OCaml Speedrun! 🐫🐪 #269

Closed swyxio closed 2 years ago

swyxio commented 2 years ago

source: devto devToUrl: "https://dev.to/swyx/ocaml-speedrun-3f7g" devToReactions: 40 devToReadingTime: 11 devToPublishedAt: "2018-03-24T21:11:35.871Z" devToViewsCount: 694 title: OCaml Speedrun! 🐫🐪 published: true description: a guided walk through Jane Street's OCaml workshop tags: ocaml

OCaml is the basis of ReasonML which has been getting a lot of buzz as a leading compile-to-JS language. There was a free OCaml workshop in NYC offered by Jane Street today so I decided to take it and share my notes here. Jane Street has moved billions of dollars for years running an OCaml codebase so they are an extremely credible source of expertise.

Fair warning: This article is not like a normal Dev.To article in that this is a guided walkthrough of a workshop - you are expected to code along or this will be completely useless to you. But with these 24 examples (taking about 2-3 hours) you should get a solid taste of the key language features in OCaml!

And a Disclaimer: I have prior experience working with Haskell so I might have some unconscious knowledge with static typed/functional languages here.

Installing OCaml on your system

Follow this: https://github.com/janestreet/install-ocaml. We had no issues following these instructions. I went for the "reason IDE" extension in VS Code for my dev environment but vim/emacs seem well supported too. Sublime is not supported.

Basic knowledge

opam is the package manager of OCaml. If you followed the instructions above you've already used it.

As part of the above process you also install utop which Jane Street recommends as a better "toplevel" than the default. A "toplevel" is also known as a REPL.

merlin is what is used under the hood for compiling/syntax highlighting/code completion.

We are not using "raw OCaml" - we are using Jane Street's Base flavor which overrides OCaml's stdlib with some of their opinions. This is what you will see in the first line of all the problem sets:

open! Base

Module imports are all done like this. We'll see more of this later.

Going through the workshop

git clone https://github.com/janestreet/learn-ocaml-workshop

and open up /02-exercises. We're going to go through all of these!

Hello World: /01-introduction

As it says in problem.ml, just run jbuilder runtest and you should see the error:

 ✝  learn-ocaml-workshop/02-exercises/01-introduction> jbuilder runtest
Entering directory '/Users/swyx/ocaml/learn-ocaml-workshop'
         ppx 02-exercises/01-introduction/problem.pp.ml (exit 1)
(cd _build/default && ./.ppx/ppx_jane/ppx.exe --dump-ast --cookie 'library-name="problem_1"' -o 02-exercises/01-introduction/problem.pp.ml --impl 02-exercises/01-introduction/problem.ml)
File "02-exercises/01-introduction/problem.ml", line 25, characters 22-23:
Error: String literal not terminated

so if you fix line 25: let () = Stdio.printf "Hello, World!" by adding that last quote, you get

 ✝  learn-ocaml-workshop/02-exercises/01-introduction> jbuilder runtest
Entering directory '/Users/swyx/ocaml/learn-ocaml-workshop'
         run alias 02-exercises/01-introduction/runtest
Hello, World!

Joy to the world! Notice how a new .merlin file is added when you run jbuilder - this is the compiler at work.

Basic Data Types: /02-basic_types

Head to problem.ml again and give it a read. Your task is to implement the two functions on line 65 and 68:

let int_average x y = failwith "For you to implement"
(* val float_average : float -> float -> float *)
let float_average x y = failwith "For you to implement"

If you run jbuilder again you will see errors because these functions are currently implemented with "failwith". Time to get implementing!

Notice that the type signatures are commented out. This folder also has a problem.mli file. This file declares interfaces for the associated file and happens to have the signatures you need so we don't need to worried about it.

solution

int_average can be solved with: let int_average x y = (x + y) / 2 which makes sense. but float_average needs the float specific operators (this is different from Haskell) or you will get this error:

File "02-exercises/02-basic_types/problem.ml", line 163, characters 27-29:
Error: This expression has type float but an expression was expected of type
         Base__Int.t = int

Notice how if you actually go to line 163 you can see the test that generated that error. You solve this with the float specific operators (mentioned in line 13-15):

let float_average x y = (x +. y) /. 2.

Defining Functions: /03-define_functions

This one is pretty straight forward. I did like the fact that

In OCaml, outside of strings, whitespace and newlines are the same.

solution

let plus x y   = x + y

let times x y  = x * y

let minus x y  = x - y

let divide x y = x / y

Calling Functions: /04-call_functions

Average of two numbers is adding and then halving.

solution

let average x y = half (add x y)

Playing around with the multiline syntax and implicit return , this also works:

let average x y =
  let res = add x y in
  half res

and so does this:

let average x y =
  let res = add
    x
    y in
  half
    res

Functions as arguments: /05-twice

Functions as a first class citizen are a pretty well accepted concept everywhere now, I feel like.

solution

let add1 x = x + 1
let square x = x * x
let twice f x = f (f x)
let add2 = twice add1
let raise_to_the_fourth = twice square

Pattern matching: /06-pattern-matching

Another familiar pattern from Haskell and is being proposed in Javascript. But needs a special keyword match _ with

solution

let non_zero x =
  match x with
  | 0 -> false
  | _ -> true

Recursion: /07-simple_recursion

See: Recursion. recursive functions need to be declared with let rec

solution

let rec add_every_number_up_to x =
  (* make sure we don't call this on negative numbers! *)
  assert (x >= 0);
  match x with
  | 0 -> 0
  | _ -> x + (add_every_number_up_to (x-1))

(* Let's write a function to multiply every number up to x. Remember: [factorial 0] is 1 *)
let rec factorial x =
  assert (x >= 0);
  match x with
  | 0 -> 1
  | 1 -> 1
  | _ -> x * (factorial (x-1))

Data Type: Linked Lists: /08-list_intro

This exercise pairs arrays with pattern matching and recursion. The tricky new bit here is immediately destructuring the list that you are matching, which tripped me up a bit. But the provided length example is instructive if you look at it carefully.

solution

let rec sum lst =
  match lst with
  | [] -> 0
  | hd :: tl -> hd + (sum(tl))

Building Lists: /09-list_range

this is another recursive answer again. you want to make the range function recursive and then call itself all the way until from equals to_. i initially tried this:

let rec range from to_ =
  match from with
  | to_ -> []
  | _ -> (from :: (range (from + 1) to_))

and this didnt work because the matching assigns to the to_ instead of compares with it which is annoying.

solution

let rec range from to_ =
  match from = to_ with
  | true -> []
  | false -> (from :: (range (from + 1) to_))

the single = here is an "infix equality" operator which works fine for ints, which is why we use it here. but notice how they had to use a "PPX Rewriter" (see Extra Knowledge section) to implement the list comparison [%compare.equal: int list] in this same problem set.

Recursing through a List: /10-list_product

this one is pretty much the same as exercise 8 where you did the sum of the list.

solution

let rec product xs =
  match xs with
  | [] -> 1
  | a :: b -> a * product(b)

Abstracting functions: /11-sum_product

This is a pretty tricky one. We are creating a function that creates a function, abstracting repeated behavior. From line 5-36 they walk you through an example of how it is done, and then from 47 onward you are expected to do this for a similar but different pattern of behavior. Good luck and pay attention to the patterns that are being used!

solution

let rec every answer combine xs =
  match xs with
  | [] -> answer
  | x :: ys -> combine x (every answer combine ys)

(* Now let's rewrite sum and product in just one line each using every *)
let simpler_sum xs     = every 0 plus xs
let simpler_product xs = every 1 times xs

pretty neat! You can also pass the infix operator as a function (let simpler_sum xs = every 0 (+) xs) but you can't do this for the * operator because (*) collides with commenting in OCaml.

Float functions: /12-list_min

We encounter Float.max, Float.min, Float.infinity and Float.neg_infinity for the first time. pretty straight forward.

solution

let rec smallest xs =
  match xs with
  | [] -> Float.infinity
  | x :: ys -> Float.min x (smallest ys)

Abstractions and Float functions: /13-largest_smallest

Combining the last two exercises - abstracting functions again and using the Float functions.

solution

let simpler_largest  xs = every Float.neg_infinity Float.max xs
let simpler_smallest xs = every Float.infinity Float.min xs

Data Type: Variant Types aka Enums /14-variants

Variants kind of work like Enums except that they can actually carry data:

type card_value =
  | Ace
  | King
  | Queen
  | Jack
  | Number of int

let one_card_value : card_value = Queen
let another_card_value : card_value = Number 8

and this is nice :)

solution

let card_value_to_score card_value =
  match card_value with
  | Ace      -> 11
  | King     -> 10
  | Queen    -> 10
  | Jack     -> 10
  | Number i -> i

this also works for the "or" matching

let card_value_to_score card_value =
  match card_value with
  | Ace      -> 11
  | King
  | Queen
  | Jack     -> 10
  | Number i -> i

Data Type: Tuples and Parameterized Types /15-tuples

Tuples are what they are in other languages, but their typedefs look a little weird

type int_and_string_and_char = int * string * char
let example : int_and_string_and_char = (5, "hello", 'A')

Functions dont have to define their types before hand. they can return the same types of things that are passed to them: 

type 'a pair = 'a * 'a`

solution

you can destructure within the funciton definition:

(* this works *)
(* let add coord1 coord2 =
  let (a, b) = coord1 in
  let (c, d) = coord2 in
  (a+c, b+d) *)

(* this also works *)
let add (a, b) (c, d) = (a+c, b+d)

and again 

(* this works *)
(* let first pair =
  let (a, _) = pair in
  a *)
(* this too *)
let first (a, _) = a
(* this *)
let second (_,b) = b

the inbuilt functions fst and snd also do the same things these do.

Labelled arguments /16-labelled_arguments

labelling arguments...

val divide : dividend:int -> divisor:int -> int
let divide ~dividend ~divisor = dividend / divisor

Labelled arguments can be passed in in any order (!)

solution

let modulo ~dividend ~divisor = dividend - (divisor * divide ~dividend ~divisor)

Data Type: Options /17-options

An ['a option] is either [None], meaning absence of data, or [Some x] meaning the data exists, and that data specifically is [x].

solution

let safe_divide ~dividend ~divisor =
  match divisor = 0 with
  | true -> None
  | false -> Some (dividend / divisor)

Anonymous functions /18-anonymous_functions

lambda functions! defined with the fun keyword. eg the double function:

(fun i -> 2 * i)

ironically the question doesnt test this knowledge at all.

solution

let apply_if_nonzero f i =
  match i = 0 with
  | true -> 0
  | false -> f i

List operations /19-list_operations

Now were being introduced to List operations: List.map, List.iter, List.fold_left, List.find, List.find_exn.

solution

This was my first gnarly answer:

let divide dividend divisor  = dividend / divisor
let modulo ~dividend ~divisor = dividend - (divisor * divide dividend divisor)
let mod2 x = modulo x 2
let ifEven x =
  match mod2 x with
  | 0 -> 1
  | _ -> 0
let num_even_ints ints =
  let first = List.map
    ~f:(fun x -> ifEven x)
    ints in
  sum_of_my_ints first

but Jane Street's Core apparently has a filter and a count function:

Core.List.count ~f:(fun x -> x mod 2 = 0)

Type Definitions! /20-reading_sigs

So far we havent had any practice writing our own type definitions so this is going to be tricky. we have to write our own typedefs in line 80-ish. There are two things to be careful of here:

  1. we have to return the abstract type t instead of hardcoding it to int even though the test is int
  2. labelled arguments make it into the typedef too!

Here you also see the module import syntax. We import prelude.ml by adding open! Prelude (note the capital first letter) at the start.

We also start defining scoped modules here with the module keyword, with a sig/end pair for types, and then struct/end pair for code:

module Example : sig
  (*  type defs *)
end = struct
  (*  code *)
end

solutions

  val create: numerator:int -> denominator:int -> t
  val value: t -> float

Folding cardio /21-writing_list_operations

a bunch of exercises here. i failed the first time because the straight append method a :: [b] was appending things in the wrong order, so I needed to use List.append to switch the order around because [b] :: a is not valid syntax. (you can also use List.fold_right)

solutions

  let map f lst = List.fold_left
    lst
    ~init:[]
    ~f:(fun acc x ->  List.append acc [f(x)])

  let iter f lst = List.fold_left
    lst
    ~init:()
    ~f:(fun acc x -> f(x))

  let filter f lst = List.fold_left
    lst
    ~init:[]
    ~f:(fun acc x ->
      match f(x) with
      | true -> List.append acc [x]
      | _ -> acc
    )

Data Type: Immutable Records /22-records

new data type! and making a function that returns records.

solutions

let modify_person (person : person) =
  match person.first_name with
  | "Jan" -> {person with age = 30}
  | _ -> {person with number_of_cars = person.number_of_cars + 6}

Data Type: Mutable Records /23-mutable_records

Mutable records are declared with:

type color =
  | Red
  | Yellow
  | Green [@@deriving compare]

type stoplight =
  { location      : string (* stoplights don't usually move *)
  ; mutable color : color  (* but they often change color *)
  } [@@deriving compare]

and modified with:

let set_color stoplight color =
  stoplight.color <- color

solutions

let advance_color stoplight =
  match stoplight.color with
  | Red -> set_color stoplight Green
  | Yellow -> set_color stoplight Red
  | Green -> set_color stoplight Yellow

Data Type: refs /24-refs

they are declared with:

let x = ref 0

and modified with:

let () =
  x := !x + 1

this solution works without a ref:

let take op a b =
  match op a b with
  | true -> a
  | false -> b

let min_and_max lst =
  List.fold_left
    lst
    ~init:(Int.max_value, Int.min_value)
    ~f:(fun (curmin, curmax) x ->
      (take (<) curmin x, take (>) curmax x)
    )

solutions

some notes on using a ref:

let take op a b =
  match op a b with
  | true -> a
  | false -> b

let min_and_max lst =
  let min = ref Int.max_value in
  let max = ref Int.min_value in
  List.iter
    ~f:(fun x ->
      min := take (<) !min x;
      max := take (>) !max x;
      )
    lst;
  (!min, !max)

note: see Christophe's solution in the comments as well

THAT'S ALL FOLKS!

Wasn't too bad was it? You can try tackling their "froggy" example next, but it is a lot of implementation specific stuff using the Js_of_ocaml library.

Extra knowledge

PPX Rewriters extend the base OCaml language with new syntax that will compile to raw ocaml. They are the "Babel" of OCaml. for example

assert([%compare.equal: int list]
        (5 : :[1;8;4])
        [5;1;8;4])

let goes with in, and the ;; trick

lets that aren't paired with in can bleed to the next line of code which could be unrelated. you can trap errors by adding double semicolons so that the compiler knows you are done with a toplevel definition.

let min_and_max lst =
  let min = ref Int.max_value in
  let max = ref Int.min_value in
  List.iter
    ~f:(fun x ->
      min := take (<) !min x;
      max := take (>) !max x;
      )
    lst;
  (!min, !max)
;;

Four ways to compare things

These are basically things that were broken in our test run of the workshop; you shouldn't encounter these but these are useful references for ways to invoke the OCaml syntax (not just for comparing)


  assert ([%compare.equal: string] s "hello");
  assert (String.equal s "hello");
  assert (String.(=) s "hello");
  assert String.(s = "hello");