Generics / templates

Java has generics and C++ has templates. These language features are only half of a functor, since they only act on types, not functions. In JavaScript we can do better.

// Stack interface
var stackOf = function (t, u) {
  u = u || t;
  func(t); func(u);
  return makeInterface({
    push: hom(t, id),
    // pop returns either [0, []] or [1, value]
    pop: hom([], makeCoproduct([terminal, u])), 
    size: hom([], nat32)
  });
};

// Stack implementation
var makeStack = function (t, u) {
  var state = [];
  return stackOf(t, u)({
    push: function (val) {
      state.push(val);
    },
    pop: function () {
      return state.length ?
          [1, state.pop()] :
          [0, []];
    },
    size: function () {
      return state.length;
    }
  };
};

// Create a stack of strings.
var myStack = makeStack(str);

This definition of stack is a little odd because it has the option of taking two contracts instead of just one. A functor like arrOf is both a contract and the map function. If we think of stackOf as a kind of map, then what does it do?

In arrOf, the contract or function gets applied to each element of the array. In stackOf, one contract or function gets applied before pushing and the other gets applied after popping. Given an associative array obj and a stackOf(str) object myStack, we could write

var myLookupStack = stackOf(
    id, 
    function (s) { return obj[s]; })(myStack);

and get a stack object where you push strings but pop values of obj.

A stack homomorphism from an implementation stackOf(t)(x) to stackOf(u)(y) is a function f: t -> u such that stack(f, u)(y) gives the same result as stack(t, f)(x). This notion of a stack homomorphism hasn’t appeared in the literature (at least not under the name “stack homomorphism”) even though it’s very natural from a category theory perspective. I believe Java and C++ developers didn’t come up with it just because generics and templates deal only with types rather than both types and functions between them.

Advertisements

6 Comments to “Generics / templates”

  1. Small typo: I think line 22 should end in a colon “:”

  2. Could you expand on the limitation of C++ templates to only being half of a functor? C++ has function templates as well as class templates — would that help?

  3. OK; here’s a version that uses for_each instead of for loop, and uses const refs where appropriate:

    #include <functional>
    #include <algorithm>
    #include <iostream>
    #include <vector>
    
    template <typename A, typename B>
    std::function<std::vector<B>(const std::vector<A>&)> map(std::function<B(const A&)> f)
    {
        return [f](const std::vector<A>& as) -> std::vector<B> {
            std::vector<B> bs;
            std::for_each(as.begin(), as.end(), [f, &bs](A a) {bs.push_back(f(a));});
            return bs;
        };
    }
    
    std::function<float(const int&)> iOver10 = [](const int& i){return (float)i/10.0f;};
    
    template <typename T>
    void print_collection(const T& t)
    {
        std::for_each(t.begin(), t.end(),
                      [](const typename T::value_type& t){std::cout << t << ", ";});
        std::cout << "\n";
    }
    
    int main(int argc, const char * argv[])
    {
    
        std::vector<int> is = {1, 2, 3, 4, 5};
        std::vector<float> fs;
        fs = map(iOver10)(is);
        print_collection(fs);
        return 0;
        // Prints: "0.1, 0.2, 0.3, 0.4, 0.5,"
    }
    

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: