OCaml and Functional Programming Contest - May '14

About two weeks ago, I decided it was time for me to get experience with the ML-family of programming languages, so I installed OCaml and started writing programs. For motivation, I first followed the Functional Programming track on HackerRank and then entered this month's FP contest. (I scored 19th out of 161.) My thoughts so far on the language:

• Pattern matching is a great feature in a language. Pattern matching provides an "if-then" mechanism that can use both the input's value and the input's structure. In particular, the SKIBC translation problem from the contest decomposed marvellously into a recursive pattern match/transform function once you specify the proper data types.
• The standard library is weak. I had to write several debugging functions to print structures. Because of how Ocaml implements polymorphism and discards type information within the compiled output, it's basically impossible to write a generic 'to_string' function. It usually took more code to write the I/O routines (particularly in parsing the contest input) than to write the algorithms.
• Although I don't think there is a way to use them in HackerRank, Jane Street's OCaml library is an attempt at 'completing' the standard library and making it more competitive with other languages (e.g. Perl, Python, Ruby). It would be worth my time to study Jane Street's library.
• Performance profiling tools, at least as far as "how many times does this execute" are quite good. However, I have not seen a way to get a sense of how expensive individual operations are versus how often they are committed.

OCaml Profiling Idiom

The idiom to profile an Ocaml program is:

ocamlcp -p a program.ml -o program
cat input | ./program
ocamlprof program.ml > program.ml.prof

The file program.ml.prof will contain a source listing of program.ml but annotated with call counts.

Choosing Algorithm based on Characteristics of the Problem

I believe I first came across a reference to an algorithm that chose an algorithm to solve problems based on characteristics of that problem in a review of Fast Fourier Transform methods. In this article, Leyton-Brown et al. describe a process where they use machine learning to predict the algorithm runtime of various SAT-solvers. Practically, this meant they could write a program that selected the appropriate SAT solver from a pool and, in general, exceed the performance of competitor algorithms overall. The far more useful result, as the paper lightly addresses, would be understanding why SAT solvers do so well with problems that are, complexity-wise, NP-complete. By itself, I am doubtful a machine learning approach will yield a model susceptible to answer "why" but perhaps if the approach incorporated more performance outputs (that collectively help determine the run time) with an augmented machine learning approach as in Schmidt and Lipson?

OCaml - Return lines of text from file as list

I've started some challenges on HackerRank and, after completing several challenges using Python, decided to try them using OCaml, a functional language. I found the documentation around I/O to be a bit obtuse, so I'm sharing some sample code to facilitate completing the challenges. This code reads all lines from a channel and returns them as a list in OCaml:

let line_stream_of_channel channel =
  Stream.from
    (fun _ ->
      try Some (input_line channel) with End_of_file -> None);;

let list_of_stream stream =
  let result = ref [] in
  Stream.iter (fun value -> result := value :: !result) stream;
  List.rev !result ;;

As an example, this line calls print_string on every element read from stdin:

List.iter print_string (list_of_stream (line_stream_of_channel stdin)) ;;