Haskell in ES6: Part 2

[mateogianolio]

Originally posted 2015-11-17.

Read the first part here.

This is the second post dedicated to implementing native versions of Haskell functions according to JavaScript ES6 standards. You can see the full source code with unit tests in this GitHub repo.

Thanks for all the contributions! I have set up an email address, casualjavascript@gmail.com, for feedback or post suggestions.

Infinite lists

Trying to replicate the behaviour of Haskell's infinite lists, we can use ES6 proxies. They allow us to hook to a getter function which will execute every time one of the proxy's properties are accessed.

A setback with proxies is that regular JavaScript array operations will not work. To (kind of) mitigate this, we will return Infinity for any property that is not an index. That way, when we check for the length property, we will get Infinity and we know that we are handling an infinite array.

iterate f x returns an infinite list of repeated applications of f to x.

repeat x is an infinite list, with x the value of every element.

cycle ties a finite list into a circular one, or equivalently, the infinite repetition of the original list. It is the identity on infinite lists.

iterate :: (a -> a) -> a -> [a]
repeat :: a -> [a]
cycle :: [a] -> [a]

/**
 * Returns an infinite list of repeated applications of f to x
 * @param f function to iterate with
 * @param x initial value
 **/
export function iterate (f, x) {
  return Proxy.create({
    get: (_, property) => {
      if (isNaN(property))
        return Infinity;

      var r = x;
      for (var i = 0; i < property; i++)
        r = f(r);
      return r;
    }
  });
}

/**
 * Returns an infinite list, with x the value of every element
 * @param x value
 **/
export function repeat (x) {
  return Proxy.create({
    get: (_, property) =>
      isNaN(property) ?
        Infinity : x
  });
}

/**
 * Ties a finite list into a circular one, or equivalently,
 * the infinite repetition of the original list
 * @param xs list to be cycled
 **/
export function cycle (xs) {
  return Proxy.create({
    get: (_, property) =>
      isNaN(property) ?
        Infinity : xs[property % xs.length]
  });
}

Examples

var iterate = ƒ.iterate(x => x * 2, 1),
    repeat = ƒ.repeat(10),
    cycle = ƒ.cycle([0, 1, 2]);

iterate[0]; // => 1
iterate[1]; // => 2
iterate[4]; // => 16
iterate[7]; // => 128

repeat[0]; // => 10
repeat[10]; // => 10
repeat[9999]; // => 10

cycle[1]; // => 1
cycle[3]; // => 0
cycle[4]; // => 1
cycle[5]; // => 2

Sublists

The following sublist functions have been constructed to work with the above implementation of infinite lists.

take n xs, returns the prefix of xs of length n, or xs itself if n > length xs.

drop n xs returns the suffix of xs after the first n elements, or [] if n > length xs.

splitAt n xs returns a tuple where first element is xs prefix of length n and second element is the remainder of the list.

takeWhile, applied to a predicate p and a list xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p.

dropWhile p xs returns the suffix remaining after takeWhile p xs.

take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
splitAt :: Int -> [a] -> ([a], [a])
takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]

/**
 * Applied to a list xs, returns the prefix of xs of length n
 * @param n number of elements to take
 * @param xs list to take from
 **/
export function take (n, xs) {
  if (n <= 0)         return [];
  if (n >= xs.length) return xs;

  var r = [];
  for (var i = 0; i < n; i++)
    r.push(xs[i]);

  return r;
}

/**
 * Returns the suffix of xs after the first n elements
 * @param n number of elements to drop
 * @param xs list to drop from
 **/
export function drop (n, xs) {
  if (n <= 0)         return xs;
  if (n >= xs.length) return [];

  if (xs.length === Infinity)
    return Proxy.create({
      get: (_, property) =>
        isNaN(property) ?
          Infinity : xs[property + n]
    });

  var r = [];
  for (var i = n; i < xs.length; i++)
    r.push(xs[i]);

  return r;
}

/**
 * Returns a tuple where first element is xs prefix of length n and
 * second element is the remainder of the list
 * @param n index to split at
 * @param xs list to split
 **/
export function splitAt (n, xs) {
  return [take(n, xs), drop(n, xs)];
}

/**
 * Applied to a predicate f and a list xs, returns the longest
 * prefix (possibly empty) of xs of elements that satisfy f
 * @param f predicate to satisfy
 * @param xs list to take from
 **/
export function takeWhile (f, xs) {
  var r = [];
  for (var i = 0; i < xs.length; i++) {
    if (!f(xs[i]))
      return r;
    r.push(xs[i]);
  }

  return r;
}

/**
 * Returns the suffix remaining after takeWhile
 * @param f predicate to satisfy
 * @param xs list to drop from
 **/
export function dropWhile (f, xs) {
  return drop(takeWhile(f, xs).length, xs);
}

Examples

var list = [0, 1, 2, 3],
    infiniteList = ƒ.cycle(list);

ƒ.take(3, list); // => [0, 1, 2]
ƒ.take(6, infiniteList); // => [0, 1, 2, 3, 0, 1]

ƒ.drop(3, list); // => [3]
ƒ.drop(5, infiniteList)[0]; // => 1

ƒ.splitAt(2, list); // => [[0, 1], [2, 3]]
ƒ.splitAt(3, list); // => [[0, 1, 2], [3]]

ƒ.takeWhile(x => x < 2, list); // => [0, 1]
ƒ.takeWhile(x => x < 2, infiniteList); // => [0, 1]

ƒ.dropWhile(x => x < 2, list); // => [2, 3]
ƒ.dropWhile(x => x < 2, infiniteList)[0]; // => 2

Happy hacking.