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)) ;;

Squarified Treemap Algorithm, Functionally

I'm preparing to implement the squarified treemap algorithm in an unfamiliar package, so I wanted a clear and complete description of the process. The original paper by Bruls, Huizing, and van Wijk is written procedurally and relies on global state.

I've written an extended explanation of the algorithm, but I've chosen to implement the algorithm in a functional manner. The code is in Mathematica, but should be readily adaptable to other functional languages like Schema, Scala, F#, or JavaScript/D3.

Format: PDF NB Github

Axis/Scale Boundaries

When charting unknown data, we would like to set the axis scale such that the details in the data are clear and the end points on the scale are aesthetically pleasing.

D3 and Protovis use the "nice" algorithm for linear scales (and a modification for logarithmic scales). The pull request implementing the algorithm in JavaScript is on github, but, mathematically, for an array of data containing a \(min\) and \(max\) value:

Let $$step = 10^{round(log_{10}(max - min)) - 1}$$

then,

$$scale_{min} = \lfloor\frac{min}{step}\rfloor \times step$$
$$scale_{max} = \lceil\frac{max}{step}\rceil \times step$$

If the data has a range of 0.002454 to 0.1455, the scale will extend from 0.002 to 0.015. Visually, the bounding boxes (tan and green) will look like:

Minimizing Autocorrelation of a List

As part of a graph rendering algorithm, I needed to take a list of y-values and disperse the points within a xy-range. (Within the list, the x coordinate has no meaning. I'm not re-ordering a time series.) To model the dispersion, I decided to use the autocorrelation metric. Autocorrelation measures the correlation of a list to itself. Put another way, autocorrelation measures how much the prior value can be used to predict the next value. (For this discussion, I'm using 1 as the lag parameter. Additionally, minimizing the autocorrelation is the same as minimizing the covariance.)

For example, the figure below shows a sinusoid (sampled at a regular interval). The autocorrelation of the figure is 0.994705 --- almost the maximum value of 1.

In contrast, the figure below has been modified by the autocorrelation minimization algorithm. The two figures have the same y-values, but the x-values have been changed resulting in a new correlation of -0.999955.

The Algorithm

The formula for calculating autocorrelation includes a number of terms, but the only terms that are impacted by changing the order of the list can be reduced to the sum:

$$ \Sigma(x_i - \mu)(x_{i+1} - \mu) $$

where \(\mu\) is the arithmetic mean of the list.

The approach is to maximize occurrences of large negative values.

1. Create a list terms with the values of the list minus the mean of the list.
2. Sort the list terms.
3. Initialize the merged list with the head and tail of terms.
4. While elements remain in terms,
1. Take an element from terms (either the head or tail) such that the element minus the mean multiplied by the head or tail of merged has minimal value.
5. Add the mean to each element of merged. Return that list.

I've uploaded a Python implementation of the algorithm to Gist.

Updated: Algorithm simplified

Dateinfer Updated

The dateinfer package has been updated to version 0.20.

You can get it from PyPi, Github, or install it via pip.

Release of dateinfer: v0.1.1

I have released the first version of a new Python library called dateinfer. dateinfer makes a "best guess" date format given a list of example date strings. For example:

>>> import dateinfer
>>> dateinfer.infer(['Mon Jan 13 09:52:52 MST 2014', 'Tue Jan 21 15:30:00 EST 2014'])
'%a %b %d %H:%M:%S %Z %Y'
>>>

The library is available through pypi and is hosted on github.

Access denied checking streaming input path

When I started launching my Elastic Map Reduce (EMR) jobs from within a Elastic Beanstalk EC2 instance, I was stymied by the error message:

Terminated with errors Access denied checking streaming input path: s3://bucket/key

I first opened up permissions on my S3 bucket and file, but that didn't work. I then explicitly set the IAM role for EMR and assigned a policy for full read/write rights to S3. That also did not work.

After conversing with Amazon Web Services technical support, they noted that I was making requests using temporary credentials. EMR does not support temporary credentials, so the actual request was being performed by something with no authority to access any resources.

I solved the problem by explicitly setting my credentials (AWS access key, secret access key) in my job creation code. Since I am using mrjob,  this was a matter of:

runner = EMRJobRunner(
            aws_access_key_id='xxxxx',
            aws_secret_access_key='xxxxxxx',
            ...)

Before, I was not explicitly setting the access keys, so mrjob was using the keys boto was using, which are apparently temporary credentials passed in via Elastic Beanstalk.