用函数实现Map

Map是个映射嘛，函数是映射嘛，所以实现很简单（除去类型签名就是3行）：

type Map k v = (k -> Maybe v)

insert :: Eq k => k -> v -> Map k v -> Map k v
insert k v m = \a -> if k == a then Just v else m a

empty :: t -> Maybe a
empty = \_ -> Nothing

lookup :: Eq k => k -> Map k v -> Maybe v
lookup k m = m k

当练习，用javascript实现一个：

function empty() {return function(k){return null};}

function insert(k, v, m) {
    return function(a) {
	if (a == k) {
	    return v;
	} else {
	    return m(a)
	}
    }
}

function lookup(k, m) {
    return m(k);
}

用起来是这样的

m = empty();
m = insert(1, 2, m);
m = insert(2, 3, m);
lookup(1, m);

不OO啊，所以又实现了一个：

function Map(){}

Map.prototype = {
    _map: function(k) {return null},

    lookup: function(k) {return this._map(k)},

    insert: function(k, v) {
    	var old_map = this._map;
    	this._map = function(a) {
    	    if (k == a) {
    		return v;
    	    } else {
    		return old_map(a);
    	    }
    	}
    }
}

没想象中复杂，但是对javascript不熟，this各种坑。性能差、内存泄露，这东西只能当练习用。