Skip to content

Instantly share code, notes, and snippets.

@friedbrice
Last active August 14, 2019 18:34
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save friedbrice/945444b478bac077f7592ff0c932e0e6 to your computer and use it in GitHub Desktop.
Save friedbrice/945444b478bac077f7592ff0c932e0e6 to your computer and use it in GitHub Desktop.
A specification for maps (the abstract data type) as a free category. And a short demo of property testing. (JSVerify source available at https://github.com/jsverify/jsverify)
// The MIT License (MIT)
//
// JSVerify is Copyright (c) 2013-2015 Oleg Grenrus
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
!function(r){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=r();else if("function"==typeof define&&define.amd)define([],r);else{("undefined"!=typeof window?window:"undefined"!=typeof global?global:"undefined"!=typeof self?self:this).jsc=r()}}(function(){return function r(t,n,e){function i(s,u){if(!n[s]){if(!t[s]){var a="function"==typeof require&&require;if(!u&&a)return a(s,!0);if(o)return o(s,!0);var c=new Error("Cannot find module '"+s+"'");throw c.code="MODULE_NOT_FOUND",c}var f=n[s]={exports:{}};t[s][0].call(f.exports,function(r){var n=t[s][1][r];return i(n||r)},f,f.exports,r,t,n,e)}return n[s].exports}for(var o="function"==typeof require&&require,s=0;s<e.length;s++)i(e[s]);return i}({1:[function(r,t,n){"use strict";var e,i=r("./arbitrary.js"),o=r("./bless.js"),s=r("./dict.js"),u=r("./generator.js"),a=r("./json.js"),c=r("./primitive.js"),f=r("./record.js"),p=r("./recordWithEnv.js"),l=r("./shrink.js"),h=r("./small.js"),y=r("./string.js"),g={arbitrary:{small:h.arbitrary,bless:o,record:p,nonshrink:i.nonshrink,pair:i.pair,either:i.either,unit:i.unit,dict:i.dict,json:i.json,nearray:i.nearray,array:i.array,tuple:i.tuple,sum:i.sum,oneof:i.oneof,recursive:i.recursive,letrec:i.letrec},generator:{dict:s.generator,json:a.json.generator,small:h.generator,record:f.generator},shrink:{record:f.shrink}};for(e in c)g.arbitrary[e]=c[e];for(e in y)g.arbitrary[e]=y[e];for(e in l)g.shrink[e]=l[e];for(e in u)g.generator[e]=u[e];t.exports=g},{"./arbitrary.js":2,"./bless.js":6,"./dict.js":7,"./generator.js":13,"./json.js":14,"./primitive.js":17,"./record.js":19,"./recordWithEnv.js":20,"./shrink.js":22,"./small.js":23,"./string.js":24}],2:[function(r,t,n){"use strict";var e=r("./arbitraryAssert.js"),i=r("./arbitraryBless.js"),o=r("./array.js"),s=r("assert"),u=r("./dict.js"),a=r("./generator.js"),c=r("./json.js"),f=r("./pair.js"),p=r("./show.js"),l=r("./shrink.js"),h=r("./utils.js");var y=i({generator:a.unit,shrink:l.noop,show:p.def});var g=c.json;t.exports={nonshrink:function(r){return r=h.force(r),i({generator:r.generator,shrink:l.noop,show:r.show})},pair:function(r,t){return f.pair(r||c.json,t||c.json)},either:function(r,t){return r=h.force(r||c.json),t=h.force(t||c.json),e(r),e(t),i({generator:a.either(r.generator,t.generator),shrink:l.either(r.shrink,t.shrink),show:p.either(r.show,t.show)})},unit:y,dict:function(r){return u.arbitrary(r||c.json)},json:g,nearray:function(r){return o.nearray(r||c.json)},array:function(r){return o.array(r||c.json)},tuple:function(r){return r=r.map(h.force),i({generator:a.tuple(h.pluck(r,"generator")),shrink:l.tuple(h.pluck(r,"shrink")),show:p.tuple(h.pluck(r,"show"))})},sum:function(r){return r=r.map(h.force),i({generator:a.sum(h.pluck(r,"generator")),shrink:l.sum(h.pluck(r,"shrink")),show:p.sum(h.pluck(r,"show"))})},oneof:function(){s(0!==arguments.length,"oneof: at least one parameter expected");for(var r=[],t=function(t){r.push(h.force(t).generator)},n=0;n<arguments.length;n++){var e=arguments[n];h.isArray(e)?e.forEach(t):t(e)}return i({generator:a.oneof(r),shrink:l.noop,show:p.def})},recursive:function(r,t){var n=r.generator,e=a.recursive(n,function(r){var n=i({generator:r,shrink:l.noop,show:p.def});return t(n).generator});return i({generator:e,shrink:l.noop,show:p.def})},letrec:function(r){var t={},n=r(function(r){var n;return t.hasOwnProperty(r)||(t[r]=((n={}).generator=a.bless(function(r){return n.strict.generator(r)}),n.shrink=l.noop,n.show=p.def,n=i(n))),t[r]});return Object.keys(t).forEach(function(r){var e=n[r];if(!e)throw new Error("undefined lazy arbitrary: "+r);t[r].strict=e}),n}}},{"./arbitraryAssert.js":3,"./arbitraryBless.js":4,"./array.js":5,"./dict.js":7,"./generator.js":13,"./json.js":14,"./pair.js":16,"./show.js":21,"./shrink.js":22,"./utils.js":28,assert:29}],3:[function(r,t,n){"use strict";var e=r("assert");t.exports=function(r){e(null!=r&&"object"==typeof r,"arb should be an object"),e("function"==typeof r.generator&&"function"==typeof r.generator.map,"arb.generator should be a function"),e("function"==typeof r.shrink&&"function"==typeof r.shrink.smap,"arb.shrink should be a function"),e("function"==typeof r.show,"arb.show should be a function"),e("function"==typeof r.smap,"arb.smap should be a function")}},{assert:29}],4:[function(r,t,n){"use strict";var e=r("./show.js");function i(r,t,n){return o({generator:this.generator.map(r),shrink:this.shrink.smap(r,t),show:n||e.def})}function o(r){return r.smap=i,r}t.exports=o},{"./show.js":21}],5:[function(r,t,n){"use strict";var e=r("./arbitraryAssert.js"),i=r("./arbitraryBless.js"),o=r("./generator.js"),s=r("./show.js"),u=r("./shrink.js"),a=r("./utils.js");function c(r){return function(t){return t=a.force(t),e(t),i({generator:o[r](t.generator),shrink:u[r](t.shrink),show:s.array(t.show)})}}var f=c("array"),p=c("nearray");t.exports={array:f,nearray:p}},{"./arbitraryAssert.js":3,"./arbitraryBless.js":4,"./generator.js":13,"./show.js":21,"./shrink.js":22,"./utils.js":28}],6:[function(r,t,n){"use strict";var e=r("assert"),i=r("./arbitraryBless.js"),o=r("./generator.js"),s=r("./show.js"),u=r("./shrink.js");t.exports=function(r){return e(null!==r&&"object"==typeof r,"bless: arb should be an object"),e("function"==typeof r.generator,"bless: arb.generator should be a function"),"function"!=typeof r.shrink&&(r.shrink=u.noop),"function"!=typeof r.show&&(r.show=s.def),o.bless(r.generator),u.bless(r.shrink),i(r),r}},{"./arbitraryBless.js":4,"./generator.js":13,"./show.js":21,"./shrink.js":22,assert:29}],7:[function(r,t,n){"use strict";var e=r("./arbitraryAssert.js"),i=r("./array.js"),o=r("./generator.js"),s=r("./pair.js"),u=r("./string.js"),a=r("./utils.js");t.exports={arbitrary:function(r){r=a.force(r),e(r);var t,n=s.pair(u.string,r);return i.array(n).smap(a.pairArrayToDict,a.dictToPairArray,(t=r.show,function(r){return"{"+Object.keys(r).map(function(n){return n+": "+t(r[n])}).join(", ")+"}"}))},generator:function(r){var t=o.pair(u.string.generator,r),n=o.array(t).map(a.pairArrayToDict);return a.curried2(n,arguments)}}},{"./arbitraryAssert.js":3,"./array.js":5,"./generator.js":13,"./pair.js":16,"./string.js":24,"./utils.js":28}],8:[function(r,t,n){"use strict";var e=r("assert");function i(r){this.value=r}function o(r){this.value=r}i.prototype.either=function(r){return r(this.value)},o.prototype.either=function(r,t){return t(this.value)},i.prototype.isEqual=function(r){return e(r instanceof i||r instanceof o,"isEqual: `other` parameter should be either"),r instanceof i&&this.value===r.value},o.prototype.isEqual=function(r){return e(r instanceof i||r instanceof o,"isEqual: `other` parameter should be either"),r instanceof o&&this.value===r.value},i.prototype.bimap=function(r){return new i(r(this.value))},o.prototype.bimap=function(r,t){return new o(t(this.value))},i.prototype.first=function(r){return new i(r(this.value))},o.prototype.first=function(){return this},i.prototype.second=function(){return this},o.prototype.second=function(r){return new o(r(this.value))},t.exports={left:function(r){return new i(r)},right:function(r){return new o(r)}}},{assert:29}],9:[function(r,t,n){"use strict";var e=r("./arbitrary.js"),i=r("./fn.js"),o=r("./primitive.js"),s=r("./small.js"),u=r("./string.js"),a=r("./utils.js").merge(o,u,{pair:e.pair,unit:e.unit,either:e.either,dict:e.dict,array:e.array,nearray:e.nearray,json:e.json,fn:i.fn,fun:i.fn,nonshrink:e.nonshrink,small:s.arbitrary});t.exports=a},{"./arbitrary.js":2,"./fn.js":11,"./primitive.js":17,"./small.js":23,"./string.js":24,"./utils.js":28}],10:[function(r,t,n){"use strict";var e=r("./utils.js");function i(r){this.eq=r||e.isEqual,this.data=[]}i.prototype.contains=function(r){for(var t=0;t<this.data.length;t++)if(this.eq(this.data[t][0],r))return!0;return!1},i.prototype.insert=function(r,t){for(var n=0;n<this.data.length;n++)if(this.eq(this.data[n][0],r))return void(this.data[n]=[r,t]);this.data.push([r,t])},i.prototype.get=function(r){for(var t=0;t<this.data.length;t++)if(this.eq(this.data[t][0],r))return this.data[t][1]},t.exports=i},{"./utils.js":28}],11:[function(r,t,n){"use strict";var e=r("./arbitraryBless.js"),i=r("./generator.js"),o=r("./finitemap.js"),s=r("./json.js"),u=r("./shrink.js"),a=r("./utils.js");function c(r){return r=a.force(r||s.json),e({generator:i.bless(function(t){var n=new o,e=function(e){if(!n.contains(e)){var i=r.generator(t);n.insert(e,i)}return n.get(e)};return e.internalMap=n,e}),shrink:u.noop,show:function(t){return"["+t.internalMap.data.map(function(t){return t[0]+": "+r.show(t[1])}).join(", ")+"]"}})}t.exports={fn:c,fun:c}},{"./arbitraryBless.js":4,"./finitemap.js":10,"./generator.js":13,"./json.js":14,"./shrink.js":22,"./utils.js":28}],12:[function(r,t,n){"use strict";var e=r("trampa");function i(r){return new Object(r)===r&&"function"==typeof r.then}t.exports={isPromise:i,map:function r(t,n){return i(t)?t.then(function(t){return r(t,n)}):e.isTrampoline(t)?t.jump(function(t){return r(t,n)}):n(t)},pure:function(r){return i(r)?r:e.wrap(r)},bind:function(r,t,n){var e,o;try{e=r.apply(void 0,t)}catch(r){e=!1,o=r}return i(e)?e.then(n,function(r){return n(!1,r)}):n(e,o)},run:function r(t){return i(t)?t.then(r):e.isTrampoline(t)?r(t.run()):t}}},{trampa:32}],13:[function(r,t,n){"use strict";var e=r("assert"),i=r("./either.js"),o=r("./random.js"),s=r("./sum.js"),u=r("./utils.js");function a(r){var t=this;return f(t),p(function(n){return r(t(n))})}function c(r){var t=this;return f(t),p(function(n){return r(t(n))(n)})}function f(r){e("function"==typeof r,"generator should be a function"),e(r.map===a,"generator.map should be a function"),e(r.flatmap===c,"generator.flatmap should be a function"),e(r.flatMap===c,"generator.flatMap should be a function")}function p(r){return r.map=a,r.flatmap=c,r.flatMap=c,r}function l(r){return Math.max(Math.round(Math.log(r+1)/Math.log(2),0))}var h=p(function(){return[]});t.exports={pair:function(r,t){var n=p(function(n){return[r(n),t(n)]});return u.curried3(n,arguments)},either:function(r,t){var n=p(function(n){switch(o(0,1)){case 0:return i.left(r(n));case 1:return i.right(t(n))}});return u.curried3(n,arguments)},unit:h,tuple:function(r){var t=r.length,n=p(function(n){for(var e=[],i=0;i<t;i++)e[i]=r[i](n);return e});return u.curried2(n,arguments)},sum:function(r){var t=r.length,n=p(function(n){var e=o(0,t-1);return s.addend(e,t,r[e](n))});return u.curried2(n,arguments)},array:function(r){var t=p(function(t){for(var n=o(0,l(t)),e=new Array(n),i=0;i<n;i++)e[i]=r(t);return e});return u.curried2(t,arguments)},nearray:function(r){var t=p(function(t){for(var n=o(1,Math.max(l(t),1)),e=new Array(n),i=0;i<n;i++)e[i]=r(t);return e});return u.curried2(t,arguments)},oneof:function(r){r.forEach(function(r){e("function"==typeof r)});var t=p(function(t){var n=o(0,r.length-1);return(0,r[n])(t)});return u.curried2(t,arguments)},constant:function(r){return p(function(){return r})},bless:p,combine:function(){var r=Array.prototype.slice.call(arguments,0,-1),t=arguments[arguments.length-1];return p(function(n){var e=r.map(function(r){return r(n)});return t.apply(void 0,e)})},recursive:function(r,t){return p(function(n){return function n(e,i){return e<=0||0===o(0,3)?r(i):t(p(function(r){return n(e-1,r)}))(i)}(l(n),n)})}}},{"./either.js":8,"./random.js":18,"./sum.js":26,"./utils.js":28,assert:29}],14:[function(r,t,n){"use strict";var e,i,o,s=r("assert"),u=r("./arbitraryBless.js"),a=r("./dict.js"),c=r("./generator.js"),f=r("./primitive.js"),p=r("./show.js"),l=r("./shrink.js"),h=r("./string.js"),y=r("./utils.js"),g=f.constant(null),d=f.integer.generator,v=f.number.generator,j=f.bool.generator,m=h.string.generator,b=g.generator,w=c.recursive(c.oneof([d,v,j,m,b]),function(r){return c.oneof([c.array(r),a.generator(r)])});i=l.bless(function(r){if(s("function"!=typeof r),null===r)return g.shrink(r);switch(typeof r){case"boolean":return f.bool.shrink(r);case"number":return f.number.shrink(r);case"string":return h.string.shrink(r);default:return function(r){return Array.isArray(r)?l.array(i,r):e(r)}(r)}}),o=l.pair(h.string.shrink,i),e=l.array(o).smap(y.pairArrayToDict,y.dictToPairArray);var k=u({generator:w,shrink:i,show:p.def});t.exports={json:k}},{"./arbitraryBless.js":4,"./dict.js":7,"./generator.js":13,"./primitive.js":17,"./show.js":21,"./shrink.js":22,"./string.js":24,"./utils.js":28,assert:29}],15:[function(r,t,n){"use strict";var e=r("assert"),i=r("lazy-seq"),o=r("./api.js"),s=r("./either.js"),u=r("./environment.js"),a=r("./finitemap.js"),c=r("./fn.js"),f=r("./functor.js"),p=r("./random.js"),l=r("./show.js"),h=r("./shrink.js"),y=r("./suchthat.js"),g=r("./sum.js"),d=r("./typify.js"),v=r("./utils.js");function j(r,t,n,o,s,u,a){e(r.length===t.length,"shrinkResult: arbs and x has to be of same size"),e("number"==typeof o,"shrinkResult: size should be number"),e("number"==typeof s,"shrinkResult: shrinkN should be number");var c=v.pluck(r,"shrink"),p=v.pluck(r,"show"),y=h.tuple(c,t),g=i.fold(y,!0,function(r,t){var e=n(o,r,s+1);return f.map(e,function(r){return!0!==r?r:t()})});return f.map(g,function(r){if(!0===r){var n={counterexample:t,counterexamplestr:l.tuple(p,t),shrinks:s,exc:u};return a(n)}return r})}function m(){var r,t,n=Array.prototype.slice.call(arguments),i=n.slice(0,-1),o=n[n.length-1],s=i[i.length-1];function a(r,t,n){return e(Array.isArray(t),"generators results should be always tuple"),f.bind(o,t,function(e,o){if(!0===e)return!0;if("function"==typeof e){var s=e(r);return f.map(s,function(e){return!0===e||j(i,t,a,r,n,o,function(r){return{counterexample:r.counterexample.concat(e.counterexample),counterexamplestr:r.counterexamplestr,shrinks:r.shrinks,exc:r.exc||e.exc}})})}return j(i,t,a,r,n,o||e,v.identity)})}return("object"!=typeof(t=s)&&"function"!=typeof t||"function"!=typeof t.generator||"function"!=typeof t.shrink||"function"!=typeof t.show)&&"string"!=typeof s?(r=v.merge(u,s),i=i.slice(0,-1)):r=u,e(i.length>0,"forall requires at least single generator"),i=i.map(function(t){return t="string"==typeof t?d.parseTypify(r,t):t,v.force(t)}),e("function"==typeof o,"property should be a function"),function(r){var t=i.map(function(t){return t.generator(r)});return a(r,t,0)}}function b(r,t,n){var e="Failed after "+r.tests+" tests and "+r.shrinks+" shrinks. ";return e+="rngState: "+(r.rngState||t)+"; ",e+="Counterexample: "+r.counterexamplestr+"; ",r.exc&&(r.exc instanceof Error?(e+="Exception: "+r.exc.message,n&&(e+="\nStack trace: "+r.exc.stack)):e+="Error: "+r.exc),e}function w(r,t){var n;if((t=t||{}).size=t.size||50,t.tests=t.tests||100,t.quiet=t.quiet||!1,e("function"==typeof r,"property should be a function"),t.rngState)p.setStateString(t.rngState);else if("undefined"!=typeof process){var i=function(r){for(var t=0;t<r.length-1;t++)if("--jsverifyRngState"===r[t])return r[t+1]}(process.argv);i&&p.setStateString(i)}return f.run(f.map(function e(i){if(n=p.currentStateString(),i>t.tests)return!0;var o=p(0,t.size),s=f.pure(r(o));return f.map(s,function(r){return!0===r?e(i+1):(r.tests=i,t.quiet||console.error(b(r,n,!0),r.counterexample),r)})}(1),function(r){return!0===r?t.quiet||console.info("OK, passed "+t.tests+" tests"):r.rngState=n,r}))}function k(r,t){return void 0===(t=t||{}).quiet&&(t.quiet=!0),f.run(f.map(w(r,t),function(r){if(!0!==r)throw r.exc instanceof Error?(r.exc.message=b(r),r.exc):new Error(b(r))}))}var x={forall:m,check:w,assert:k,assertForall:function(){return k(m.apply(null,arguments))},checkForall:function(){return w(m.apply(null,arguments))},property:function(r){var t=Array.prototype.slice.call(arguments,1);if(1===t.length)it(r,function(){return f.run(f.map(t[0](),function(t){if("function"==typeof t)return k(t);if(!0!==t)throw new Error(r+" doesn't hold")}))});else{var n=m.apply(void 0,t);it(r,function(){return k(n)})}},sampler:function(r,t){return t="number"==typeof t?Math.abs(t):10,function(n){if("number"==typeof n){var e=[];n=Math.abs(n);for(var i=0;i<n;i++)e.push(r.generator(t));return e}return r.generator(t)}},throws:function(r,t,n){e(void 0===t||"function"==typeof t,"throws: error parameter must be a constructor"),e(void 0===n||"string"==typeof n,"throws: message parameter must be a string");try{return r(),!1}catch(r){return void 0===t||r instanceof t&&(void 0===n||r.message===n)}},fn:c.fn,fun:c.fn,suchthat:y.suchthat,left:s.left,right:s.right,addend:g.addend,compile:function(r,t){return t=t?v.merge(u,t):u,d.parseTypify(t,r)},generator:o.generator,shrink:o.shrink,random:p,show:l,utils:v,_:{FMap:a}};for(var E in o.arbitrary)x[E]=o.arbitrary[E];t.exports=x},{"./api.js":1,"./either.js":8,"./environment.js":9,"./finitemap.js":10,"./fn.js":11,"./functor.js":12,"./random.js":18,"./show.js":21,"./shrink.js":22,"./suchthat.js":25,"./sum.js":26,"./typify.js":27,"./utils.js":28,assert:29,"lazy-seq":30}],16:[function(r,t,n){"use strict";var e=r("./arbitraryAssert.js"),i=r("./arbitraryBless.js"),o=r("./generator.js"),s=r("./show.js"),u=r("./shrink.js"),a=r("./utils.js");t.exports={pair:function(r,t){return r=a.force(r),t=a.force(t),e(r),e(t),i({generator:o.pair(r.generator,t.generator),shrink:u.pair(r.shrink,t.shrink),show:s.pair(r.show,t.show)})}}},{"./arbitraryAssert.js":3,"./arbitraryBless.js":4,"./generator.js":13,"./show.js":21,"./shrink.js":22,"./utils.js":28}],17:[function(r,t,n){"use strict";var e=r("./arbitraryBless"),i=r("assert"),o=r("./generator.js"),s=r("./random.js"),u=r("./show.js"),a=r("./shrink.js"),c=r("./utils.js");function f(r){var t=r();r.generator=t.generator,r.shrink=t.shrink,r.show=t.show,r.smap=t.smap}function p(r){return function(t,n){if(2===arguments.length){return e(r(n-t)).smap(function(r){return Math.abs(r)+t},function(r){return r-t})}return 1===arguments.length?e(r(t)):e(r())}}var l=p(function(r){return{generator:o.bless(function(t){return s(-(t=void 0===r?t:r),t)}),shrink:a.bless(function(r){if(i("number"==typeof r,"integer.shrink have to be a number"),0===(r=Math.abs(r)))return[];for(var t=[0],n=c.div2(r),e=Math.max(n,1);n<r;)t.push(n),t.push(-n),n+=e=Math.max(c.div2(e),1);return t}),show:u.def}});function h(r){return e({generator:o.bless(function(t){return s(0,t=void 0===r?t:r)}),shrink:a.bless(function(r){i("number"==typeof r,"nat.shrink have to be a number");for(var t=[],n=c.div2(r),e=Math.max(n,1);n<r;)t.push(n),n+=e=Math.max(c.div2(e),1);return t}),show:u.def})}f(l),f(h);var y=p(function(r){return{generator:o.bless(function(t){return t=void 0===r?t:r,s.number(-t,t)}),shrink:a.bless(function(r){return i("number"==typeof r,"number.shrink have to be a number"),Math.abs(r)>1e-6?[0,r/2,-r/2]:[]}),show:u.def}});f(y);var g=h(255),d=h(65535),v=h(4294967295),j=l(-128,127),m=l(-32768,32767),b=l(-2147483648,2147483647),w=e({generator:o.bless(function(){return 1===s(0,1)}),shrink:a.bless(function(r){return i(!0===r||!1===r,"bool.shrink excepts true or false"),!0===r?[!1]:[]}),show:u.def}),k=1416499879495;function x(r,t){var n,i;return 2===arguments.length?(n=function(r){return new Date(r)},r=(i=function(r){return r.getTime()})(r),t=i(t),y(r,t).smap(n,i)):(n=function(r){return new Date(768e6*r+k)},e({generator:y.generator.map(n),shrink:a.noop,show:u.def}))}function E(r){return i(0!==r.length,"elements: at least one parameter expected"),e({generator:o.bless(function(){var t=s(0,r.length-1);return r[t]}),shrink:a.bless(function(t){var n=r.indexOf(t);return n<=0?[]:r.slice(0,n)}),show:u.def})}f(x);var A=E([!1,null,void 0,"",0,NaN]);A.show=function(r){return r!=r?"falsy: NaN":""===r?"falsy: empty string":void 0===r?"falsy: undefined":"falsy: "+r},t.exports={integer:l,nat:h,int8:j,int16:m,int32:b,uint8:g,uint16:d,uint32:v,number:y,elements:E,bool:w,falsy:A,constant:function(r){return e({generator:o.constant(r),shrink:a.noop,show:u.def})},datetime:x}},{"./arbitraryBless":4,"./generator.js":13,"./random.js":18,"./show.js":21,"./shrink.js":22,"./utils.js":28,assert:29}],18:[function(r,t,n){"use strict";var e=new(r("rc4").RC4small);function i(r,t){return e.random(r,t)}i.integer=i,i.number=function(r,t){return e.randomFloat()*(t-r)+r},i.currentStateString=e.currentStateString.bind(e),i.setStateString=e.setStateString.bind(e),t.exports=i},{rc4:31}],19:[function(r,t,n){"use strict";var e=r("./arbitraryBless.js"),i=r("./generator.js"),o=r("./utils.js"),s=r("./shrink.js");function u(r){var t=Object.keys(r),n=i.bless(function(n){var e={};return t.forEach(function(t){e[t]=r[t](n)}),e});return o.curried2(n,arguments)}function a(r){var t=Object.keys(r),n=t.map(function(t){return r[t]}),e=s.bless(function(r){var e=t.map(function(t){return r[t]});return s.tuple(n,e).map(function(r){var n={};return t.forEach(function(t,e){n[t]=r[e]}),n})});return o.curried2(e,arguments)}t.exports={generator:u,arbitrary:function(r){var t={},n={},i={};return Object.keys(r).forEach(function(e){var s=o.force(r[e]);t[e]=s.generator,n[e]=s.shrink,i[e]=s.show}),e({generator:u(t),shrink:a(n),show:function(r){return"{"+Object.keys(r).map(function(t){return t+": "+i[t](r[t])}).join(", ")+"}"}})},shrink:a}},{"./arbitraryBless.js":4,"./generator.js":13,"./shrink.js":22,"./utils.js":28}],20:[function(r,t,n){"use strict";var e=r("./environment.js"),i=r("./record.js"),o=r("./typify.js"),s=r("./utils.js");t.exports=function(r,t){var n=t?s.merge(e,t):e,u={};return Object.keys(r).forEach(function(t){var e=r[t];u[t]="string"==typeof e?o.parseTypify(n,e):e}),i.arbitrary(u)}},{"./environment.js":9,"./record.js":19,"./typify.js":27,"./utils.js":28}],21:[function(r,t,n){"use strict";var e=r("./utils.js");t.exports={def:function(r){return JSON.stringify(r)},pair:function(r,t){return e.curried3(function(n){return"("+r(n[0])+", "+t(n[1])+")"},arguments)},either:function(r,t){function n(t){return"Left("+r(t)+")"}function i(r){return"Right("+t(r)+")"}return e.curried3(function(r){return r.either(n,i)},arguments)},tuple:function(r){return e.curried2(function(t){for(var n=[],e=0;e<r.length;e++)n.push(r[e](t[e]));return n.join("; ")},arguments)},sum:function(r){return e.curried2(function(t){return t.fold(function(t,n,e){return"Sum("+t+"/"+n+": "+r[t](e)+")"})},arguments)},array:function(r){return e.curried2(function(t){return"["+t.map(r).join(", ")+"]"},arguments)}}},{"./utils.js":28}],22:[function(r,t,n){"use strict";var e=r("assert"),i=r("./either.js"),o=r("lazy-seq"),s=r("./sum.js"),u=r("./utils.js");function a(r,t){var n=this;return c(function(e){return n(t(e)).map(r)})}function c(r){return r.smap=a,r}var f=c(function(){return[]});function p(r,t){var n=c(function(n){e(2===n.length,"shrinkPair: pair should be an Array of length 2");var i=n[0],s=n[1],u=r(i),a=t(s),c=u.map(function(r){return[r,s]});return Array.isArray(c)&&(c=o.fromArray(c)),c.append(function(){return a.map(function(r){return[i,r]})})});return u.curried3(n,arguments)}function l(r){return e(1===r.length||2===r.length,"linked list must be either [] or [x, linkedlist]"),1===r.length?[r[0]]:[r[0]].concat(l(r[1]))}function h(r){return e(Array.isArray(r)&&r.length>0,"toLinkedList expects non-empty array"),1===r.length?[r[0]]:[r[0],h(r.slice(1))]}function y(r){return[r]}function g(r){return r[0]}function d(r){return function t(n){var i=c(function(i){if(e(Array.isArray(i),"shrinkArrayImpl() expects array, got: "+i),i.length<=r)return o.nil;var s=i[0],u=i.slice(1);return o.cons(u,o.nil).append(n(s).map(function(r){return[r].concat(u)})).append(t(n,u).map(function(r){return[s].concat(r)}))});return u.curried2(i,arguments)}}var v=d(0),j=d(1);t.exports={noop:f,pair:p,either:function(r,t){function n(t){return r(t).map(i.left)}function e(r){return t(r).map(i.right)}var o=c(function(r){return r.either(n,e)});return u.curried3(o,arguments)},tuple:function(r){e(r.length>0,"shrinkTuple needs > 0 values");var t=function r(t){return 1===t.length?t[0].smap(y,g):p(t[0],r(t[1]))}(h(r)),n=c(function(n){e(n.length===r.length,"shrinkTuple: not-matching params");var i=h(n);return t(i).map(l)});return u.curried2(n,arguments)},sum:function(r){e(r.length>0,"shrinkTuple needs > 0 values");var t=c(function(t){return t.fold(function(t,n,i){return e(n===r.length,"shrinkSum: not-matching params"),r[t](i).map(function(r){return s.addend(t,n,r)})})});return u.curried2(t,arguments)},array:v,nearray:j,bless:c}},{"./either.js":8,"./sum.js":26,"./utils.js":28,assert:29,"lazy-seq":30}],23:[function(r,t,n){"use strict";var e=r("./generator.js"),i=r("./arbitraryBless.js"),o=r("./arbitraryAssert.js"),s=r("./utils.js");function u(r){return e.bless(function(t){return r(s.ilog2(t))})}function a(r){return o(r),i({generator:u(r.generator),shrink:r.shrink,show:r.show})}t.exports={generator:u,arbitrary:function(r){return"function"==typeof r?function(){return a(r.apply(r,arguments))}:a(r)}}},{"./arbitraryAssert.js":3,"./arbitraryBless.js":4,"./generator.js":13,"./utils.js":28}],24:[function(r,t,n){"use strict";var e=r("./array.js"),i=r("./primitive.js"),o=r("./utils.js");function s(r){return String.fromCharCode(r)}function u(r){return r.charCodeAt(0)}var a=i.nat(255).smap(s,u),c=i.integer(32,126).smap(s,u),f=e.array(a).smap(o.charArrayToString,o.stringToCharArray),p=e.nearray(a).smap(o.charArrayToString,o.stringToCharArray),l=e.array(c).smap(o.charArrayToString,o.stringToCharArray),h=e.nearray(c).smap(o.charArrayToString,o.stringToCharArray);t.exports={char:a,asciichar:c,string:f,nestring:p,asciistring:l,asciinestring:h}},{"./array.js":5,"./primitive.js":17,"./utils.js":28}],25:[function(r,t,n){"use strict";var e=r("./environment.js"),i=r("./typify.js"),o=r("./utils.js"),s=r("./generator.js"),u=r("./shrink.js"),a=r("./arbitraryBless.js");t.exports={suchthat:function(r,t,n){var c;return 2===arguments.length?(n=t,c=e):c=o.merge(e,t),r="string"==typeof r?i.parseTypify(c,r):r,r=o.force(r),a({generator:s.bless(function(t){for(var e=0;;e++){e>5&&(e=0,t+=1);var i=r.generator(t);if(n(i))return i}}),shrink:u.bless(function(t){return r.shrink(t).filter(n)}),show:r.show})}}},{"./arbitraryBless.js":4,"./environment.js":9,"./generator.js":13,"./shrink.js":22,"./typify.js":27,"./utils.js":28}],26:[function(r,t,n){"use strict";var e=r("assert");function i(r,t,n){e(t>0,"Addend: 0 < len"),e(r>=0&&r<t,"Addend: 0 <= idx < len"),this.idx=r,this.len=t,this.value=n}i.prototype.fold=function(r){return r(this.idx,this.len,this.value)},t.exports={addend:function(r,t,n){return new i(r,t,n)}}},{assert:29}],27:[function(r,t,n){"use strict";var e,i,o=r("./arbitrary.js"),s=r("assert"),u=r("./record.js"),a=r("./array.js"),c=r("./fn.js"),f=r("typify-parser"),p=r("./utils.js");e=function(r,t){switch(t.type){case"ident":return function(r,t){var n=r[t.value];if(!n)throw new Error("Unknown arbitrary: "+t.value);return n}(r,t);case"application":return function(r,t){var n=e(r,t.callee),o=i(r,t.args);return n.apply(void 0,o)}(r,t);case"function":return function(r,t){var n=e(r,t.result);return c.fn(n)}(r,t);case"brackets":return function(r,t){var n=e(r,t.arg);return a.array(n)}(r,t);case"disjunction":return function(r,t){var n=i(r,t.args);return o.sum(n)}(r,t);case"conjunction":return function(r,t){var n=i(r,t.args);return o.tuple(n)}(r,t);case"record":return function(r,t){var n={};return Object.keys(t.fields).forEach(function(i){n[i]=e(r,t.fields[i])}),u.arbitrary(n)}(r,t);case"number":return t.value;case"recursive":return function(r,t){s("disjunction"===t.arg.type,"recursive type's argument should be disjunction");var n=t.name,i=p.partition(t.arg.args,function(r){return-1===f.freeVars(r).indexOf(n)})[0];if(0===i.length)throw new Error("Recursive type without non-recursive branch");var u=e(r,{type:"disjunction",args:i});return o.recursive(u,function(i){var o={};o[n]=i;var s=p.merge(r,o);return e(s,t.arg)})}(r,t);default:throw new Error("Unsupported typify ast type: "+t.type)}},i=function(r,t){return t.map(function(t){return e(r,t)})},t.exports={parseTypify:function(r,t){var n=f(t);return e(r,n)}}},{"./arbitrary.js":2,"./array.js":5,"./fn.js":11,"./record.js":19,"./utils.js":28,assert:29,"typify-parser":33}],28:[function(r,t,n){"use strict";var e=Array.isArray;function i(r){return new Object(r)===r}function o(r){return"number"==typeof r&&r!=r}function s(r){var t=r.slice();return t.sort(),t}function u(r){var t=r-1;return function(n,e){return e.length===r?n(e[t]):n}}var a=u(2),c=u(3);t.exports={isArray:e,isObject:i,isEqual:function r(t,n){var u;if(o(t)&&o(n))return!0;if(t===n)return!0;if(e(t)&&e(n)&&t.length===n.length){for(u=0;u<t.length;u++)if(!r(t[u],n[u]))return!1;return!0}if(i(t)&&i(n)&&!e(t)&&!e(n)){var a=Object.keys(t),c=Object.keys(n);if(!r(s(a),s(c)))return!1;for(u=0;u<a.length;u++)if(!r(t[a[u]],n[a[u]]))return!1;return!0}return!1},isApproxEqual:function(r,t,n){var u=!1!==(n=n||{}).fnEqual,a=n.depth||5,c=[];return function r(t,n,f){if(o(t)&&o(n))return!0;if(t===n)return!0;if(f>=a)return!0;var p;for(p=0;p<c.length;p++)if(c[p][0]===t&&c[p][1]===n)return!0;if(c.push([t,n]),"function"==typeof t&&"function"==typeof n)return u;if(e(t)&&e(n)&&t.length===n.length){for(p=0;p<t.length;p++)if(!r(t[p],n[p],f+1))return!1;return!0}if(i(t)&&i(n)&&!e(t)&&!e(n)){var l=Object.keys(t),h=Object.keys(n);if(!r(s(l),s(h),f+1))return!1;for(p=0;p<l.length;p++)if(!r(t[l[p]],n[l[p]],f+1))return!1;return!0}return!1}(r,t,0)},identity:function(r){return r},pluck:function(r,t){return r.map(function(r){return r[t]})},force:function(r){return"function"==typeof r?r():r},merge:function(){for(var r={},t=0;t<arguments.length;t++)for(var n=arguments[t],e=Object.keys(n),i=0;i<e.length;i++){var o=e[i];r[o]=n[o]}return r},div2:function(r){return Math.floor(r/2)},ilog2:function(r){return r<=0?0:Math.floor(function(r){return Math.log(r)/Math.log(2)}(r))},curried2:a,curried3:c,charArrayToString:function(r){return r.join("")},stringToCharArray:function(r){return r.split("")},pairArrayToDict:function(r){var t={};return r.forEach(function(r){t[r[0]]=r[1]}),t},dictToPairArray:function(r){var t=[];return Object.keys(r).forEach(function(n){t.push([n,r[n]])}),t},partition:function(r,t){for(var n=[],e=[],i=0;i<r.length;i++){var o=r[i];t(o)?n.push(o):e.push(o)}return[n,e]}}},{}],29:[function(r,t,n){"use strict";function e(r,t){if(r===t)return 0;for(var n=r.length,e=t.length,i=0,o=Math.min(n,e);i<o;++i)if(r[i]!==t[i]){n=r[i],e=t[i];break}return n<e?-1:e<n?1:0}function i(r){return global.Buffer&&"function"==typeof global.Buffer.isBuffer?global.Buffer.isBuffer(r):!(null==r||!r._isBuffer)}var o=r("util/"),s=Object.prototype.hasOwnProperty,u=Array.prototype.slice,a="foo"===function(){}.name;function c(r){return Object.prototype.toString.call(r)}function f(r){return!i(r)&&("function"==typeof global.ArrayBuffer&&("function"==typeof ArrayBuffer.isView?ArrayBuffer.isView(r):!!r&&(r instanceof DataView||!!(r.buffer&&r.buffer instanceof ArrayBuffer))))}var p=t.exports=v,l=/\s*function\s+([^\(\s]*)\s*/;function h(r){if(o.isFunction(r)){if(a)return r.name;var t=r.toString().match(l);return t&&t[1]}}function y(r,t){return"string"==typeof r?r.length<t?r:r.slice(0,t):r}function g(r){if(a||!o.isFunction(r))return o.inspect(r);var t=h(r);return"[Function"+(t?": "+t:"")+"]"}function d(r,t,n,e,i){throw new p.AssertionError({message:n,actual:r,expected:t,operator:e,stackStartFunction:i})}function v(r,t){r||d(r,!0,t,"==",p.ok)}function j(r,t,n,s){if(r===t)return!0;if(i(r)&&i(t))return 0===e(r,t);if(o.isDate(r)&&o.isDate(t))return r.getTime()===t.getTime();if(o.isRegExp(r)&&o.isRegExp(t))return r.source===t.source&&r.global===t.global&&r.multiline===t.multiline&&r.lastIndex===t.lastIndex&&r.ignoreCase===t.ignoreCase;if(null!==r&&"object"==typeof r||null!==t&&"object"==typeof t){if(f(r)&&f(t)&&c(r)===c(t)&&!(r instanceof Float32Array||r instanceof Float64Array))return 0===e(new Uint8Array(r.buffer),new Uint8Array(t.buffer));if(i(r)!==i(t))return!1;var a=(s=s||{actual:[],expected:[]}).actual.indexOf(r);return-1!==a&&a===s.expected.indexOf(t)||(s.actual.push(r),s.expected.push(t),function(r,t,n,e){if(null==r||null==t)return!1;if(o.isPrimitive(r)||o.isPrimitive(t))return r===t;if(n&&Object.getPrototypeOf(r)!==Object.getPrototypeOf(t))return!1;var i=m(r),s=m(t);if(i&&!s||!i&&s)return!1;if(i)return r=u.call(r),t=u.call(t),j(r,t,n);var a,c,f=k(r),p=k(t);if(f.length!==p.length)return!1;for(f.sort(),p.sort(),c=f.length-1;c>=0;c--)if(f[c]!==p[c])return!1;for(c=f.length-1;c>=0;c--)if(a=f[c],!j(r[a],t[a],n,e))return!1;return!0}(r,t,n,s))}return n?r===t:r==t}function m(r){return"[object Arguments]"==Object.prototype.toString.call(r)}function b(r,t){if(!r||!t)return!1;if("[object RegExp]"==Object.prototype.toString.call(t))return t.test(r);try{if(r instanceof t)return!0}catch(r){}return!Error.isPrototypeOf(t)&&!0===t.call({},r)}function w(r,t,n,e){var i;if("function"!=typeof t)throw new TypeError('"block" argument must be a function');"string"==typeof n&&(e=n,n=null),i=function(r){var t;try{r()}catch(r){t=r}return t}(t),e=(n&&n.name?" ("+n.name+").":".")+(e?" "+e:"."),r&&!i&&d(i,n,"Missing expected exception"+e);var s="string"==typeof e,u=!r&&i&&!n;if((!r&&o.isError(i)&&s&&b(i,n)||u)&&d(i,n,"Got unwanted exception"+e),r&&i&&n&&!b(i,n)||!r&&i)throw i}p.AssertionError=function(r){var t;this.name="AssertionError",this.actual=r.actual,this.expected=r.expected,this.operator=r.operator,r.message?(this.message=r.message,this.generatedMessage=!1):(this.message=y(g((t=this).actual),128)+" "+t.operator+" "+y(g(t.expected),128),this.generatedMessage=!0);var n=r.stackStartFunction||d;if(Error.captureStackTrace)Error.captureStackTrace(this,n);else{var e=new Error;if(e.stack){var i=e.stack,o=h(n),s=i.indexOf("\n"+o);if(s>=0){var u=i.indexOf("\n",s+1);i=i.substring(u+1)}this.stack=i}}},o.inherits(p.AssertionError,Error),p.fail=d,p.ok=v,p.equal=function(r,t,n){r!=t&&d(r,t,n,"==",p.equal)},p.notEqual=function(r,t,n){r==t&&d(r,t,n,"!=",p.notEqual)},p.deepEqual=function(r,t,n){j(r,t,!1)||d(r,t,n,"deepEqual",p.deepEqual)},p.deepStrictEqual=function(r,t,n){j(r,t,!0)||d(r,t,n,"deepStrictEqual",p.deepStrictEqual)},p.notDeepEqual=function(r,t,n){j(r,t,!1)&&d(r,t,n,"notDeepEqual",p.notDeepEqual)},p.notDeepStrictEqual=function r(t,n,e){j(t,n,!0)&&d(t,n,e,"notDeepStrictEqual",r)},p.strictEqual=function(r,t,n){r!==t&&d(r,t,n,"===",p.strictEqual)},p.notStrictEqual=function(r,t,n){r===t&&d(r,t,n,"!==",p.notStrictEqual)},p.throws=function(r,t,n){w(!0,r,t,n)},p.doesNotThrow=function(r,t,n){w(!1,r,t,n)},p.ifError=function(r){if(r)throw r};var k=Object.keys||function(r){var t=[];for(var n in r)s.call(r,n)&&t.push(n);return t}},{"util/":36}],30:[function(r,t,n){"use strict";var e=r("assert"),i={};function o(r,t){this.headValue=r,this.tailValue=t}function s(){var r=this.tailFn();return this.tailValue=Array.isArray(r)?f(r):r,delete this.tail,delete this.force,this}function u(){return this.force(),this.tailValue}function a(r,t){return e("function"==typeof t),r.tailFn=t,r.tail=u,r.force=s,r}function c(r,t){return"function"==typeof t?a(new o(r),t):Array.isArray(t)?a(c(r),function(){return f(t)}):new o(r,t)}function f(r){return e(Array.isArray(r)),function r(t,n){return n<t.length?c(t[n],function(){return r(t,n+1)}):i}(r,0)}i.isNil=!0,i.toString=function(){return"nil"},i.length=function(){return 0},i.toArray=function(){return[]},i.fold=function(r){return r},i.head=function(){throw new Error("nil.head")},i.tail=function(){return i},i.nth=function(r){throw e("number"==typeof r),new Error("Can't get "+r+"th value of the nil")},i.take=function(r){return e("number"==typeof r),i},i.drop=function(r){return e("number"==typeof r),i},i.map=function(r){return e("function"==typeof r),i},i.append=function(r){return"function"==typeof r&&(r=r()),Array.isArray(r)?f(r):r},i.filter=function(){return i},i.every=function(){return!0},i.some=function(){return!1},i.contains=function(){return!1},i.containsNot=function(){return!0},o.prototype.isNil=!1,o.prototype.toString=function(){return"Cons("+this.headValue+", "+this.tailValue+")"},o.prototype.length=function(){return 1+this.tail().length()},o.prototype.toArray=function(){for(var r=this,t=[];r!==i;)t.push(r.headValue),r=r.tail();return t},o.prototype.fold=function(r,t){var n=this;return t(this.headValue,function(){return n.tail().fold(r,t)})},o.prototype.head=function(){return this.headValue},o.prototype.tail=function(){return this.tailValue},o.prototype.nth=function(r){return e("number"==typeof r),0===r?this.headValue:this.tail().nth(r-1)},o.prototype.take=function(r){e("number"==typeof r);var t=this;return 0===r?i:c(this.headValue,function(){return t.tail().take(r-1)})},o.prototype.drop=function(r){return e("number"==typeof r),0===r?this:this.tail().drop(r-1)},o.prototype.map=function(r){e("function"==typeof r);var t=this;return c(r(t.headValue),function(){return t.tail().map(r)})},o.prototype.append=function(r){if(r===i||Array.isArray(r)&&0===r.length)return this;var t=this;return c(t.headValue,function(){return t.tail().append(r)})},o.prototype.filter=function(r){e("function"==typeof r);var t=this;return r(t.headValue)?c(t.headValue,function(){return t.tail().filter(r)}):t.tail().filter(r)},o.prototype.every=function(r){e("function"==typeof(r=r||function(r){return r}));var t=r(this.headValue);return t?this.tail().every(r):t},o.prototype.some=function(r){e("function"==typeof(r=r||function(r){return r}));var t=r(this.headValue);return t||this.tail().some(r)},o.prototype.contains=function(r){return r===this.headValue||this.tail().contains(r)},o.prototype.containsNot=function(r){return r!==this.headValue&&this.tail().containsNot(r)},t.exports={nil:i,cons:c,append:function(){for(var r=i,t=0;t<arguments.length;t++)r=r.append(arguments[t]);return r},fromArray:f,singleton:function(r){return f([r])},iterate:function r(t,n){return c(t,function(){return r(n(t),n)})},fold:function(r,t,n){return Array.isArray(r)?function r(t,n,e,i){return i<t.length?e(t[i],function(){return r(t,n,e,i+1)}):n}(r,t,n,0):r.fold(t,n)}}},{assert:29}],31:[function(r,t,n){"use strict";function e(r){return parseInt(r,10)===r}function i(r){function t(t){if(void 0===t){t=new Array(r);for(var n=0;n<r;n++)t[n]=Math.floor(Math.random()*r)}else if("string"==typeof t)t=(t=""+t).split("").map(function(t){return t.charCodeAt(0)%r});else{if(!Array.isArray(t))throw new TypeError("invalid seed key specified");if(!t.every(function(r){return"number"==typeof r&&r===(0|r)}))throw new TypeError("invalid seed key specified: not array of integers")}for(var e=t.length,i=function(){for(var t=new Array(r),n=0;n<r;n++)t[n]=n;return t}(),o=0,s=0;s<r;s++){o=(o+i[s]+t[s%e])%r;var u=i[s];i[s]=i[o],i[o]=u}return i}function n(r){this.s=t(r),this.i=0,this.j=0}return n.prototype.randomNative=function(){this.i=(this.i+1)%r,this.j=(this.j+this.s[this.i])%r;var t=this.s[this.i];return this.s[this.i]=this.s[this.j],this.s[this.j]=t,this.s[(this.s[this.i]+this.s[this.j])%r]},n.prototype.randomUInt32=function(){return 256*(256*(256*this.randomByte()+this.randomByte())+this.randomByte())+this.randomByte()},n.prototype.randomFloat=function(){return this.randomUInt32()/4294967296},n.prototype.random=function(){var r,t;if(1===arguments.length)r=0,t=arguments[0];else{if(2!==arguments.length)throw new TypeError("random takes one or two integer arguments");r=arguments[0],t=arguments[1]}if(!e(r)||!e(t))throw new TypeError("random takes one or two integer arguments");return r+this.randomUInt32()%(t-r+1)},n.prototype.currentState=function(){return{i:this.i,j:this.j,s:this.s.slice()}},n.prototype.setState=function(t){var n=t.s,e=t.i,i=t.j;if(!(e===(0|e)&&0<=e&&e<r))throw new Error("state.i should be integer [0, "+(r-1)+"]");if(!(i===(0|i)&&0<=i&&i<r))throw new Error("state.j should be integer [0, "+(r-1)+"]");if(!Array.isArray(n)||n.length!==r)throw new Error("state should be array of length "+r);for(var o=0;o<r;o++)if(-1===n.indexOf(o))throw new Error("state should be permutation of 0.."+(r-1)+": "+o+" is missing");this.i=e,this.j=i,this.s=n.slice()},n}var o=i(256);o.prototype.randomByte=o.prototype.randomNative;var s=i(16);s.prototype.randomByte=function(){return 16*this.randomNative()+this.randomNative()};var u="a".charCodeAt(0),a="0".charCodeAt(0);function c(r){return r<10?String.fromCharCode(a+r):String.fromCharCode(u+r-10)}function f(r){return parseInt(r,16)}s.prototype.currentStateString=function(){var r=this.currentState();return c(r.i)+c(r.j)+r.s.map(c).join("")},s.prototype.setStateString=function(r){if(!r.match(/^[0-9a-f]{18}$/))throw new TypeError("RC4small stateString should be 18 hex character string");var t=f(r[0]),n=f(r[1]),e=r.split("").slice(2).map(f);this.setState({i:t,j:n,s:e})},o.RC4small=s,t.exports=o},{}],32:[function(r,t,n){"use strict";var e=r("assert");function i(r){this.x=r}function o(r,t){e("function"==typeof t),this.tramp=r,this.cont=t}function s(r){return r instanceof i||r instanceof o}function u(r){return s(r)?r:new i(r)}i.prototype.jump=function(r){return new o(this,function(t){return u(r(t))})},o.prototype.jump=i.prototype.jump,i.prototype.run=o.prototype.run=function(r){return function(r,t){for(var n=(t=t||{}).debug||!1,s=t.log||console.log,u=[];;)if(n&&s("trampoline execute: stack size "+u.length),r instanceof i){if(0===u.length)return r.x;r=u[u.length-1](r.x),u.pop()}else e(r instanceof o),u.push(r.cont),r=r.tramp}(this,r)},t.exports={isTrampoline:s,wrap:u,lazy:function(r){return e("function"==typeof r,"lazy: computation should be function"),u().jump(r)}}},{assert:29}],33:[function(r,t,n){"use strict";function e(r){return function(t){if(t.pos>=t.len)throw new SyntaxError("Expecting identifier, end-of-input found");var n=t.tokens[t.pos];if(n.type!==r)throw new SyntaxError("Expecting '"+r+"', found: "+n.type);return t.pos+=1,r}}var i=e(":"),o=e("{"),s=e("}"),u=e(";"),a=e("("),c=e(")"),f=e("["),p=e("]"),l=e("rec"),h=e("->");function y(r){if(r.pos>=r.len)throw new SyntaxError("Expecting identifier, end-of-input found");var t=r.tokens[r.pos];if("ident"!==t.type)throw new SyntaxError("Expecting 'ident', found: "+t.type);return r.pos+=1,t.value}function g(r,t,n){return function(e){var i=r(e),o=e.tokens[e.pos];return o&&o.type===t?(e.pos+=1,{type:n,arg:i}):i}}var d=g(function(r){if(r.pos>=r.len)throw new SyntaxError("Expecting terminal, end-of-input found");var t=r.tokens[r.pos];switch(t.type){case"false":case"true":case"unit":case"string":case"number":case"bool":case"ident":return r.pos+=1,t;case"{":return function(r){o(r);var t=r.tokens[r.pos];if(t&&"}"===t.type)return s(r),{type:"record",fields:{}};for(var n={};;){var e=y(r);i(r);var a=w(r);if(n[e]=a,(t=r.tokens[r.pos])&&"}"===t.type){s(r);break}if(!t||";"!==t.type)throw new SyntaxError("Expecting '}' or ';', found: "+t.type);u(r)}return{type:"record",fields:n}}(r);case"(":return function(r){a(r);var t=w(r);return c(r),t}(r);case"[":return function(r){f(r);var t=w(r);return p(r),{type:"brackets",arg:t}}(r);case"rec":return function(r){l(r);var t=y(r);return h(r),{type:"recursive",name:t,arg:w(r)}}(r);default:throw new SyntaxError("Expecting terminal, "+t.type+" found")}},"?","optional");function v(r,t,n){return function(e){for(var i=[r(e)];;){var o=e.tokens[e.pos];if(!o||o.type!==t)break;e.pos+=1,i.push(r(e))}return 1===i.length?i[0]:{type:n,args:i}}}var j=v(function(r){for(var t=d(r),n=[];;){var e=r.pos;try{var i=d(r);n.push(i)}catch(t){r.pos=e;break}}return 0===n.length?t:{type:"application",callee:t,args:n}},"&","conjunction"),m=g(v(j,"|","disjunction"),"...","variadic");var b=v(function r(t){var n=t.tokens[t.pos],e=t.tokens[t.pos+1];if(n&&e&&"ident"===n.type&&":"===e.type){t.pos+=2;var i=r(t);return{type:"named",name:n.value,arg:i}}return m(t)},",","product");function w(r){return function r(t){var n=b(t),e=t.tokens[t.pos];return e&&"->"===e.type?(t.pos+=1,{type:"function",arg:n,result:r(t)}):n}(r)}function k(r){var t=function(r){var t=r.match(/^([ \t\r\n]+|[\u22a4\u22a5\u2227\u2228\u00d7\u2192\u2026]|\ud835\udfd9|_\|_|\*|\(\)|"(?:[^"\\]|\\[\\'"n]|\\x[0-9a-fA-F]{2})*"|'(?:[^'\\]|\\[\\'"n]|\\x[0-9a-fA-F]{2})*'|[0-9a-zA-Z_\$@]+|,|->|:|;|&|\||\.\.\.|\(|\)|\[|\]|\{|\}|\?)*$/);if(null===t)throw new SyntaxError("Cannot lex type signature");return(t=r.match(/([ \t\r\n]+|[\u22a4\u22a5\u2227\u2228\u00d7\u2192\u2026]|\ud835\udfd9|_\|_|\*|\(\)|"(?:[^"\\]|\\[\\'"n]|\\x[0-9a-fA-F]{2})*"|'(?:[^'\\]|\\[\\'"n]|\\x[0-9a-fA-F]{2})*'|[0-9a-zA-Z_\$@]+|,|->|:|;|&|\||\.\.\.|\(|\)|\[|\]|\{|\}|\?)/g)).map(function(r){switch(r){case"_|_":case"⊥":return{type:"false"};case"*":case"⊤":return{type:"true"};case"()":case"𝟙":return{type:"unit"};case"true":return{type:"bool",value:!0};case"false":return{type:"bool",value:!1};case"rec":return{type:"rec"};case"&":case"∧":return{type:"&"};case"|":case"∨":return{type:"|"};case",":case"×":return{type:","};case";":return{type:";"};case":":return{type:":"};case"(":return{type:"("};case")":return{type:")"};case"[":return{type:"["};case"]":return{type:"]"};case"{":return{type:"{"};case"}":return{type:"}"};case"?":return{type:"?"};case"->":case"→":return{type:"->"};case"...":case"…":return{type:"..."}}return r.match(/^[ \r\r\n]+$/)?null:r.match(/^[0-9]+/)?{type:"number",value:parseInt(r,10)}:"'"===r[0]||'"'===r[0]?(r=r.slice(1,-1),{type:"string",value:(t=r,t.replace(/\\(?:'|"|\\|n|x[0-9a-fA-F]{2})/g,function(r){switch(r[1]){case"'":return"'";case'"':return'"';case"\\":return"\\";case"n":return"\n";case"x":return String.fromCharCode(parseInt(r.substr(2),16))}}))}):{type:"ident",value:r};var t}).filter(function(r){return null!==r})}(r),n={pos:0,len:t.length,tokens:t},e=w(n);if(n.pos!==n.len)throw new SyntaxError("expecting end-of-input, "+t[n.pos].type+" found");return e}function x(r){for(var t=[],n=0;n<r.length;n++){var e=r[n];t=t.concat(E(e))}return t}function E(r){switch(r.type){case"false":case"true":case"unit":case"string":case"number":case"bool":return[];case"ident":return[r.value];case"record":return function(r){var t=[];for(var n in r){var e=r[n];t=t.concat(E(e))}return t}(r.fields);case"named":return E(r.arg);case"conjunction":case"disjunction":case"product":return x(r.args);case"recursive":return E(r.arg).filter(function(t){return t!==r.name});case"optional":case"brackets":case"variadic":return E(r.arg);case"application":return E(r.callee).concat(x(r.args));case"function":return E(r.arg).concat(E(r.result))}}k.freeVars=function(r){var t=E(r);return t.sort(),function(r){for(var t=[],n=0;n<r.length;n++){var e=r[n];-1===t.indexOf(e)&&t.push(e)}return t}(t)},t.exports=k},{}],34:[function(r,t,n){"function"==typeof Object.create?t.exports=function(r,t){r.super_=t,r.prototype=Object.create(t.prototype,{constructor:{value:r,enumerable:!1,writable:!0,configurable:!0}})}:t.exports=function(r,t){r.super_=t;var n=function(){};n.prototype=t.prototype,r.prototype=new n,r.prototype.constructor=r}},{}],35:[function(r,t,n){t.exports=function(r){return r&&"object"==typeof r&&"function"==typeof r.copy&&"function"==typeof r.fill&&"function"==typeof r.readUInt8}},{}],36:[function(r,t,n){var e=/%[sdj%]/g;n.format=function(r){if(!d(r)){for(var t=[],n=0;n<arguments.length;n++)t.push(s(arguments[n]));return t.join(" ")}n=1;for(var i=arguments,o=i.length,u=String(r).replace(e,function(r){if("%%"===r)return"%";if(n>=o)return r;switch(r){case"%s":return String(i[n++]);case"%d":return Number(i[n++]);case"%j":try{return JSON.stringify(i[n++])}catch(r){return"[Circular]"}default:return r}}),a=i[n];n<o;a=i[++n])y(a)||!m(a)?u+=" "+a:u+=" "+s(a);return u},n.deprecate=function(r,t){if(v(global.process))return function(){return n.deprecate(r,t).apply(this,arguments)};if(!0===process.noDeprecation)return r;var e=!1;return function(){if(!e){if(process.throwDeprecation)throw new Error(t);process.traceDeprecation?console.trace(t):console.error(t),e=!0}return r.apply(this,arguments)}};var i,o={};function s(r,t){var e={seen:[],stylize:a};return arguments.length>=3&&(e.depth=arguments[2]),arguments.length>=4&&(e.colors=arguments[3]),h(t)?e.showHidden=t:t&&n._extend(e,t),v(e.showHidden)&&(e.showHidden=!1),v(e.depth)&&(e.depth=2),v(e.colors)&&(e.colors=!1),v(e.customInspect)&&(e.customInspect=!0),e.colors&&(e.stylize=u),c(e,r,e.depth)}function u(r,t){var n=s.styles[t];return n?"["+s.colors[n][0]+"m"+r+"["+s.colors[n][1]+"m":r}function a(r,t){return r}function c(r,t,e){if(r.customInspect&&t&&k(t.inspect)&&t.inspect!==n.inspect&&(!t.constructor||t.constructor.prototype!==t)){var i=t.inspect(e,r);return d(i)||(i=c(r,i,e)),i}var o=function(r,t){if(v(t))return r.stylize("undefined","undefined");if(d(t)){var n="'"+JSON.stringify(t).replace(/^"|"$/g,"").replace(/'/g,"\\'").replace(/\\"/g,'"')+"'";return r.stylize(n,"string")}if(g(t))return r.stylize(""+t,"number");if(h(t))return r.stylize(""+t,"boolean");if(y(t))return r.stylize("null","null")}(r,t);if(o)return o;var s=Object.keys(t),u=function(r){var t={};return r.forEach(function(r,n){t[r]=!0}),t}(s);if(r.showHidden&&(s=Object.getOwnPropertyNames(t)),w(t)&&(s.indexOf("message")>=0||s.indexOf("description")>=0))return f(t);if(0===s.length){if(k(t)){var a=t.name?": "+t.name:"";return r.stylize("[Function"+a+"]","special")}if(j(t))return r.stylize(RegExp.prototype.toString.call(t),"regexp");if(b(t))return r.stylize(Date.prototype.toString.call(t),"date");if(w(t))return f(t)}var m,x="",E=!1,A=["{","}"];(l(t)&&(E=!0,A=["[","]"]),k(t))&&(x=" [Function"+(t.name?": "+t.name:"")+"]");return j(t)&&(x=" "+RegExp.prototype.toString.call(t)),b(t)&&(x=" "+Date.prototype.toUTCString.call(t)),w(t)&&(x=" "+f(t)),0!==s.length||E&&0!=t.length?e<0?j(t)?r.stylize(RegExp.prototype.toString.call(t),"regexp"):r.stylize("[Object]","special"):(r.seen.push(t),m=E?function(r,t,n,e,i){for(var o=[],s=0,u=t.length;s<u;++s)S(t,String(s))?o.push(p(r,t,n,e,String(s),!0)):o.push("");return i.forEach(function(i){i.match(/^\d+$/)||o.push(p(r,t,n,e,i,!0))}),o}(r,t,e,u,s):s.map(function(n){return p(r,t,e,u,n,E)}),r.seen.pop(),function(r,t,n){if(r.reduce(function(r,t){return 0,t.indexOf("\n")>=0&&0,r+t.replace(/\u001b\[\d\d?m/g,"").length+1},0)>60)return n[0]+(""===t?"":t+"\n ")+" "+r.join(",\n ")+" "+n[1];return n[0]+t+" "+r.join(", ")+" "+n[1]}(m,x,A)):A[0]+x+A[1]}function f(r){return"["+Error.prototype.toString.call(r)+"]"}function p(r,t,n,e,i,o){var s,u,a;if((a=Object.getOwnPropertyDescriptor(t,i)||{value:t[i]}).get?u=a.set?r.stylize("[Getter/Setter]","special"):r.stylize("[Getter]","special"):a.set&&(u=r.stylize("[Setter]","special")),S(e,i)||(s="["+i+"]"),u||(r.seen.indexOf(a.value)<0?(u=y(n)?c(r,a.value,null):c(r,a.value,n-1)).indexOf("\n")>-1&&(u=o?u.split("\n").map(function(r){return" "+r}).join("\n").substr(2):"\n"+u.split("\n").map(function(r){return" "+r}).join("\n")):u=r.stylize("[Circular]","special")),v(s)){if(o&&i.match(/^\d+$/))return u;(s=JSON.stringify(""+i)).match(/^"([a-zA-Z_][a-zA-Z_0-9]*)"$/)?(s=s.substr(1,s.length-2),s=r.stylize(s,"name")):(s=s.replace(/'/g,"\\'").replace(/\\"/g,'"').replace(/(^"|"$)/g,"'"),s=r.stylize(s,"string"))}return s+": "+u}function l(r){return Array.isArray(r)}function h(r){return"boolean"==typeof r}function y(r){return null===r}function g(r){return"number"==typeof r}function d(r){return"string"==typeof r}function v(r){return void 0===r}function j(r){return m(r)&&"[object RegExp]"===x(r)}function m(r){return"object"==typeof r&&null!==r}function b(r){return m(r)&&"[object Date]"===x(r)}function w(r){return m(r)&&("[object Error]"===x(r)||r instanceof Error)}function k(r){return"function"==typeof r}function x(r){return Object.prototype.toString.call(r)}function E(r){return r<10?"0"+r.toString(10):r.toString(10)}n.debuglog=function(r){if(v(i)&&(i=process.env.NODE_DEBUG||""),r=r.toUpperCase(),!o[r])if(new RegExp("\\b"+r+"\\b","i").test(i)){var t=process.pid;o[r]=function(){var e=n.format.apply(n,arguments);console.error("%s %d: %s",r,t,e)}}else o[r]=function(){};return o[r]},n.inspect=s,s.colors={bold:[1,22],italic:[3,23],underline:[4,24],inverse:[7,27],white:[37,39],grey:[90,39],black:[30,39],blue:[34,39],cyan:[36,39],green:[32,39],magenta:[35,39],red:[31,39],yellow:[33,39]},s.styles={special:"cyan",number:"yellow",boolean:"yellow",undefined:"grey",null:"bold",string:"green",date:"magenta",regexp:"red"},n.isArray=l,n.isBoolean=h,n.isNull=y,n.isNullOrUndefined=function(r){return null==r},n.isNumber=g,n.isString=d,n.isSymbol=function(r){return"symbol"==typeof r},n.isUndefined=v,n.isRegExp=j,n.isObject=m,n.isDate=b,n.isError=w,n.isFunction=k,n.isPrimitive=function(r){return null===r||"boolean"==typeof r||"number"==typeof r||"string"==typeof r||"symbol"==typeof r||void 0===r},n.isBuffer=r("./support/isBuffer");var A=["Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"];function S(r,t){return Object.prototype.hasOwnProperty.call(r,t)}n.log=function(){var r,t;console.log("%s - %s",(r=new Date,t=[E(r.getHours()),E(r.getMinutes()),E(r.getSeconds())].join(":"),[r.getDate(),A[r.getMonth()],t].join(" ")),n.format.apply(n,arguments))},n.inherits=r("inherits"),n._extend=function(r,t){if(!t||!m(t))return r;for(var n=Object.keys(t),e=n.length;e--;)r[n[e]]=t[n[e]];return r}},{"./support/isBuffer":35,inherits:34}]},{},[15])(15)});

A Specification for Maps as a free category

Prerequisites

  1. Our free category needs products, denoted (_, _), with projections denoted p_1, p_2, ...

  2. Our free category needs sums, denoted _ + _, with embeddings denoted e_1, e_2, ...

  3. Our free category needs a terminal object, denoted 1.

Undefined objects

  • Key
  • Value
  • Map

Undefined morphisms

  • empty : 1 -> Map
  • insert : (Map, Key, Value) -> Map
  • lookup : (Map, Key) -> 1 + Value
  • delete : (Map, Key) -> Map

Laws

(; denotes forward composition)

  • forall m k v. insert(m,k,v);lookup(_,k) === e_2(v) (Values can be stored and retrieved by key.)

  • forall k. empty();lookup(_,k) === e_1() (The empty map stores no values.)

  • forall m k. delete(m,k);lookup(_,k) === e_1() (Stored values can be deleted by key.)

How to use

The free category generated by this spec consists of all objects and morphisms that can be constructed in finitely-many terms from the above undefined objects, undefined morphisms, products, sums, and terminal object (which is essentially every pseudocode program one can write about maps), modulo the relations defined under "Laws."

An implementation consists of an assignment of the undefined objects to types (not-necessarily statically-checked) and implementations of the undefined morphisms as functions in a programming language. If the type system of the language has products, sums, and a terminal object (many do, if not named as such) and the implementation satisfies the above laws (which can be formally proven by hand, or brute-forced by a proof assistant, or demonstrated by property testing) then the implementation defines a functor from the free category generated by the spec into the category of types and functions of the programming language. The significance of having a well-defined functor is that map pseudocode can be ported into the programming language and will have the same meaning.

#!/usr/bin/env stack
-- stack --resolver lts-14.0 script --package QuickCheck
-- This is an executable Haskell script. To run it:
-- 1. make sure you have the Haskell tool `stack` on your path
-- 2. chmod +x maps.hs
-- 3. ./maps.hs
--
-- It will download GHC and QuickCheck if you don't have them and store
-- them in your home directory for later use, but it will not touch any
-- system-level files.
{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE AllowAmbiguousTypes, ScopedTypeVariables, TypeApplications #-}
import Prelude hiding (lookup)
import Test.QuickCheck
-- Linked lists of tuples.
-- This has very poor performance, but it serves our purposes.
-- `insert` is constant, `lookup` is O(n), `delete` is O(n).
-- It's polymorphic in the key type, `k`, and the value type, `v`.
type Map k v = [(k, v)]
empty :: Map k v
empty = []
insert :: Map k v -> k -> v -> Map k v
insert m k v = (k, v) : m
-- NOTE: The `Eq k =>` in `lookup` and `delete` means `k` must have
-- a designated equality comparison operation in global scope. This is
-- what allows us to use `==` polymorphically.
lookup :: Eq k => Map k v -> k -> Maybe v
lookup [] _ = Nothing
lookup ((k, v) : rest) k0 | k == k0 = Just v
| otherwise = lookup rest k0
delete :: Eq k => Map k v -> k -> Map k v
delete m k0 = filter (\(k, _) -> k /= k0) m
-- Values can be stored and retrieved by key.
mapLaw1 :: (Eq k, Eq v) => Map k v -> k -> v -> Bool
mapLaw1 m k v = lookup (insert m k v) k == Just v
-- The empty map stores no values.
mapLaw2 :: forall k v. (Eq k, Eq v) => k -> Bool
mapLaw2 k = lookup empty k == Nothing @v
-- Stored values can be deleted by key.
mapLaw3 :: (Eq k, Eq v) => Map k v -> k -> Bool
mapLaw3 m k = lookup (delete m k) k == Nothing
-- Demonstrates fullfilment of the spec for a few choices of `k`
-- and `v`, up to some probabilistic factor.
-- `quickCheck` is a program that randomly generates input cases
-- for our laws and runs them, checking that they all come back true.
main :: IO ()
main = do
putStrLn "\nchecking Map Int String"
quickCheck (mapLaw1 @Int @String)
quickCheck (mapLaw2 @Int @String)
quickCheck (mapLaw3 @Int @String)
putStrLn "\nchecking Map String Double"
quickCheck (mapLaw1 @String @Double)
quickCheck (mapLaw2 @String @Double)
quickCheck (mapLaw3 @String @Double)
putStrLn "\nchecking Map String String"
quickCheck (mapLaw1 @String @String)
quickCheck (mapLaw2 @String @String)
quickCheck (mapLaw3 @String @String)
package local.maps;
import java.util.Optional;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;
import org.scalacheck.Arbitrary;
import org.scalacheck.Gen;
import org.scalacheck.Prop;
import org.scalacheck.Shrink;
import org.scalacheck.util.Pretty;
// This is an executable Java class (because it has a `main` method).
//
// To run it:
// 1. Get `java` version 1.8 however you install software on your system.
// 2. Download the following jars from Maven Central (http://search.maven.org):
// a. scalacheck_2.13-1.14.0.jar (https://search.maven.org/remotecontent?filepath=org/scalacheck/scalacheck_2.13/1.14.0/scalacheck_2.13-1.14.0.jar)
// b. scala-java8-compat_2.13-0.9.0.jar (https://search.maven.org/remotecontent?filepath=org/scala-lang/modules/scala-java8-compat_2.13/0.9.0/scala-java8-compat_2.13-0.9.0.jar)
// c. scala-library-2.13.0.jar (https://search.maven.org/remotecontent?filepath=org/scala-lang/scala-library/2.13.0/scala-library-2.13.0.jar)
// 3. Put all the jars in the same directory as this file (Maps.java).
// 4. Build a jar with the following command: `(mkdir java-build && cp Maps.java java-build && javac -classpath "scalacheck_2.13-1.14.0.jar:scala-java8-compat_2.13-0.9.0.jar:scala-library-2.13.0.jar" -d java-build Maps.java && (cd java-build && jar cvf maps.jar *) && cp -f java-build/maps.jar . && rm -rf java-build)`.
// 5. Run the built jar with the following command: `java -cp maps.jar:scalacheck_2.13-1.14.0.jar:scala-java8-compat_2.13-0.9.0.jar:scala-library-2.13.0.jar local.maps.Maps`.
//
// To compile and run on each save:
// 1. Get `java` as above.
// 2. Put all the jars in this directory, as above.
// 3. Get `inotifywait` however you install software on your system.
// 4. Use the following commands to create shell aliases:
// a. `alias build-java="rm -rf java-build && (mkdir java-build && cp Maps.java java-build && javac -classpath "scalacheck_2.13-1.14.0.jar:scala-java8-compat_2.13-0.9.0.jar:scala-library-2.13.0.jar" -d java-build Maps.java && (cd java-build && jar cvf maps.jar *) && cp -f java-build/maps.jar . && rm -rf java-build)"`
// b. `alias run-java="java -cp maps.jar:scalacheck_2.13-1.14.0.jar:scala-java8-compat_2.13-0.9.0.jar:scala-library-2.13.0.jar local.maps.Maps"`
// c. `alias build-run-java="build-java && run-java"`
// d. `alias watch-java="while inotifywait -e close_write Maps.java; do build-run-java; done"`
// 5. Run `watch-java` in the terminal. It'll compile and run each time you save. Happy hacking!
public final class Maps {
// Java doesn't have tuples in the standard library.
interface Pair<A, B> {
// Pair Accessors
A first();
B second();
// Pair Constructors
static <A, B> Pair<A, B> of(A a, B b) {
return new Pair<A, B>() {
public A first() { return a; }
public B second() { return b; }
};
}
}
// The linked list in Java's standard library is mutable,
// so `Map::insert` would have to clone, making it O(n).
interface List<A> {
// List Accessors
<B> B matchList( Supplier<B> withEmpty,
BiFunction<A, List<A>, B> withCons );
// List Combinators
default List<A> filter(Predicate<A> p) {
return matchList(
() ->
empty(),
(head, tail) ->
p.test(head)? cons(head, tail.filter(p)): tail.filter(p)
);
}
// List Constructors
static <A> List<A> empty() {
return new List<A>() {
public <B> B matchList( Supplier<B> withEmpty,
BiFunction<A, List<A>, B> withCons ) {
return withEmpty.get();
}
};
}
static <A> List<A> cons(A a, List<A> as) {
return new List<A>() {
public <B> B matchList( Supplier<B> withEmpty,
BiFunction<A, List<A>, B> withCons ) {
return withCons.apply(a, as);
}
};
}
}
// Linked lists of pairs.
// This has very poor performance, but it serves our purposes.
// `insert` is O(1), `lookup` is O(n), `delete` is O(n).
// This also does a lot of unnecessary heap allocation.
// It's polymorphic in the key type, `K`, and the value type, `V`.
interface Map<K, V> {
// Map Accessors
List<Pair<K, V>> unmap();
default Optional<V> lookup(K k) {
return unmap().matchList(
() ->
Optional.empty(),
(head, tail) ->
head.first().equals(k)? Optional.of(head.second()): of(tail).lookup(k)
);
}
// Map Combinators
default Map<K, V> insert(K k, V v) {
return Map.of(List.cons(Pair.of(k, v), unmap()));
}
default Map<K, V> delete(K k) {
return of(unmap().filter((pair) -> !pair.first().equals(k)));
}
// Map Constructors
static <K, V> Map<K, V> empty() {
return new Map<K, V>() {
public List<Pair<K, V>> unmap() { return List.empty(); }
};
}
static <K, V> Map<K, V> of(List<Pair<K, V>> x) {
return new Map<K, V>() {
public List<Pair<K, V>> unmap() { return x; }
};
}
}
// Values can be stored and retrieved by key.
public static <K, V> boolean mapLaw1(Map<K, V> m, K k, V v) {
return m.insert(k, v).lookup(k).equals(Optional.of(v));
}
// The empty map stores no values.
public static <K, V> boolean mapLaw2(K k) {
return Map.<K, V>empty().lookup(k).equals(Optional.<V>empty());
}
// Stored values can be deleted by key.
public static <K, V> boolean mapLaw3(Map<K, V> m, K k) {
return m.delete(k).lookup(k).equals(Optional.<V>empty());
}
// NOTE: Everything below is the tests. Don't be scared though! Since Java
// classes can be imported into Scala, many Java devs write their tests in
// Scala (see maps.scala to get an idea of how it'd look). The stuff below
// is just to show that, in principle, you can write them in pure Java.
private static <K, V> Arbitrary<Map<K, V>> arbitraryMap( Arbitrary<K> arbK,
Arbitrary<V> arbV ) {
Gen<Pair<K, V>> genPair =
Gen.zip(arbK.arbitrary(), arbV.arbitrary())
.map(scala_pair -> Pair.of(scala_pair._1, scala_pair._2));
Gen<List<Pair<K, V>>> genList =
Gen.listOf(() -> genPair).map(scala_list ->
scala_list.foldLeft(
List.<Pair<K, V>>empty(),
(acc, next) -> List.cons(next, acc)
));
return Arbitrary.apply(() -> genList.map(list -> Map.of(list)));
}
private static Arbitrary arbitraryInteger = Arbitrary.arbInt();
private static Arbitrary<String> arbitraryString = Arbitrary.arbString();
private static Arbitrary arbitraryDouble = Arbitrary.arbDouble();
private static <K, V> Shrink<Map<K, V>> shrinkMap() {
return Shrink.shrinkAny();
}
private static Shrink<Integer> shrinkInteger = Shrink.shrinkAny();
private static Shrink<String> shrinkString = Shrink.shrinkAny();
private static Shrink<Double> shrinkDouble = Shrink.shrinkAny();
// Demonstrates fullfilment of the spec for a few choices of `K`
// and `V`, up to some probabilistic factor.
// `scalacheck` is a library that randomly generates input cases
// for our laws and runs them, checking that they all come back true.
public static void main(String[] args) {
System.out.println("\nchecking Map<Integer, String>");
Prop.forAll( (Map<Integer, String> m, Integer k, String v) -> mapLaw1(m, k, v),
Prop::propBoolean,
arbitraryMap(arbitraryInteger, arbitraryString),
shrinkMap(),
Pretty::prettyAny,
arbitraryInteger,
shrinkInteger,
Pretty::prettyAny,
arbitraryString,
shrinkString,
Pretty::prettyAny
).check();
Prop.forAll( (Integer k) -> mapLaw2(k),
Prop::propBoolean,
arbitraryInteger,
shrinkInteger,
Pretty::prettyAny
).check();
Prop.forAll( (Map<Integer, String> m, Integer k) -> mapLaw3(m, k),
Prop::propBoolean,
arbitraryMap(arbitraryInteger, arbitraryString),
shrinkMap(),
Pretty::prettyAny,
arbitraryInteger,
shrinkInteger,
Pretty::prettyAny
).check();
System.out.println("\nchecking Map<String, Double>");
Prop.forAll( (Map<String, Double> m, String k, Double v) -> mapLaw1(m, k, v),
Prop::propBoolean,
arbitraryMap(arbitraryString, arbitraryDouble),
shrinkMap(),
Pretty::prettyAny,
arbitraryString,
shrinkString,
Pretty::prettyAny,
arbitraryDouble,
shrinkDouble,
Pretty::prettyAny
).check();
Prop.forAll( (String k) -> mapLaw2(k),
Prop::propBoolean,
arbitraryString,
shrinkString,
Pretty::prettyAny
).check();
Prop.forAll( (Map<String, Double> m, String k) -> mapLaw3(m, k),
Prop::propBoolean,
arbitraryMap(arbitraryString, arbitraryDouble),
shrinkMap(),
Pretty::prettyAny,
arbitraryString,
shrinkString,
Pretty::prettyAny
).check();
System.out.println("\nchecking Map<String, String>");
Prop.forAll( (Map<String, String> m, String k, String v) -> mapLaw1(m, k, v),
Prop::propBoolean,
arbitraryMap(arbitraryString, arbitraryString),
shrinkMap(),
Pretty::prettyAny,
arbitraryString,
shrinkString,
Pretty::prettyAny,
arbitraryString,
shrinkString,
Pretty::prettyAny
).check();
Prop.forAll( (String k) -> mapLaw2(k),
Prop::propBoolean,
arbitraryString,
shrinkString,
Pretty::prettyAny
).check();
Prop.forAll( (Map<String, String> m, String k) -> mapLaw3(m, k),
Prop::propBoolean,
arbitraryMap(arbitraryString, arbitraryString),
shrinkMap(),
Pretty::prettyAny,
arbitraryString,
shrinkString,
Pretty::prettyAny
).check();
}
private Maps() {
System.exit(1);
}
}
// To run:
// 1. Install `node` however it is you install software on your system.
// 2. Make sure `jsverify.standalone.min.js` is in the same directory as `maps.js`
// 3. `node maps.js`
'use-strict';
const jsv = require('./jsverify.standalone.min.js');
function Maybe(fold) {
return {
fold: (z, f) => fold(z, f),
map: (f) => fold(() => nothing, (x) => just(f(x))),
bind: (f) => fold(() => nothing, (x) => f(x)),
filter: (p) => fold(() => nothing, (x) => p(x)? just(x): nothing),
eq: (other) => fold(() => other === nothing, (x) => other.fold(() => false, (y) => x === y))
}
}
const nothing = Maybe((z, f) => z());
function just(x) {
return Maybe((z, f) => f(x));
}
// Immutable maps, based on arrays of pairs.
// O(1) insert, O(n) lookup, O(n) delete.
// Bad performance, but it's just for demonstration.
function Map(array) {
return {
unmap: () => array,
insert: (k, v) => Map([[k, v], ...array]),
lookup: (k) => {
const hits = array.filter((kv) => kv[0] === k);
return just(hits)
.filter((hits) => hits.length > 0)
.map((hits) => hits[0][1]);
},
delete: (k) => Map(array.filter((kv) => kv[0] !== k))
};
}
const empty = Map([]);
// Values can be looked up by key.
function mapLaw1(m, k, v) {
return m.insert(k, v).lookup(k).eq(just(v));
}
// The empty map contains no values.
function mapLaw2(k) {
return empty.lookup(k).eq(nothing);
}
// Values can be removed by key.
function mapLaw3(m, k) {
return m.delete(k).lookup(k).eq(nothing);
}
function arbitraryMap(k, v) {
return jsv.array(jsv.pair(k, v))
.smap(
(arr) => Map(arr),
(map) => map.unmap(),
(map) => map.unmap().toString()
);
}
// Demonstrates that the implementation meets the spec
// for a few choices of key types and value types.
// JSVerify is a library that automatically generates
// test cases for our laws, runs them, and makes sure
// that they all come back `true`.
function main() {
console.log('\nchecking maps from nats to strings')
jsv.assert(jsv.forall(
arbitraryMap(jsv.nat, jsv.string),
jsv.nat,
jsv.string,
(m, k, v) => mapLaw1(m, k, v)
))
jsv.assert(jsv.forall(
jsv.nat,
(k) => mapLaw2(k)
))
jsv.assert(jsv.forall(
arbitraryMap(jsv.nat, jsv.string),
jsv.nat,
(m, k) => mapLaw3(m, k)
))
console.log('\nchecking maps from strings to numbers')
jsv.assert(jsv.forall(
arbitraryMap(jsv.string, jsv.number),
jsv.string,
jsv.number,
(m, k, v) => mapLaw1(m, k, v)
))
jsv.assert(jsv.forall(
jsv.string,
(k) => mapLaw2(k)
))
jsv.assert(jsv.forall(
arbitraryMap(jsv.string, jsv.number),
jsv.string,
(m, k) => mapLaw3(m, k)
))
console.log('\nchecking maps from strings to bools')
jsv.assert(jsv.forall(
arbitraryMap(jsv.string, jsv.bool),
jsv.string,
jsv.bool,
(m, k, v) => mapLaw1(m, k, v)
))
jsv.assert(jsv.forall(
jsv.string,
(k) => mapLaw2(k)
))
jsv.assert(jsv.forall(
arbitraryMap(jsv.string, jsv.bool),
jsv.bool,
(m, k) => mapLaw3(m, k)
))
console.log('\nAll tests pass!')
};
main();
#!/bin/sh
exec scala -classpath "scalacheck_2.13-1.14.0.jar" "$0" "$@"
!#
// This is an executable Scala script. To run it:
// 1. Get `scala` version 2.13 however you install software
// 2. Download scalacheck_2.13-1.14.0.jar
// (https://search.maven.org/remotecontent?filepath=org/scalacheck/scalacheck_2.13/1.14.0/scalacheck_2.13-1.14.0.jar)
// and put it in the same directory as this file (maps.scala).
// 3. chmod +x maps.scala
// 4. ./maps.scala
import org.scalacheck.Prop.forAll
// Linked lists of tuples.
// This has very poor performance, but it serves our purposes.
// `insert` is constant, `lookup` is O(n), `delete` is O(n).
// It's polymorphic in the key type, `K`, and the value type, `V`.
type Map[K, V] = List[(K, V)]
def empty[K, V]: Map[K, V] = Nil
def insert[K, V](m: Map[K, V], k: K, v: V): Map[K, V] = (k, v) :: m
def lookup[K, V](m: Map[K, V], k0: K): Option[V] = m match {
case Nil => None
case (k, v) :: _ if k == k0 => Some(v)
case _ :: rest => lookup(rest, k0)
}
def delete[K, V](m: Map[K, V], k0: K): Map[K, V] =
m.filter { case (k, v) => k != k0 }
// Values can be stored and retrieved by key.
def mapLaw1[K, V](m: Map[K, V], k: K, v: V): Boolean =
lookup(insert(m, k, v), k) == Some(v)
// The empty map stores no values.
def mapLaw2[K, V](k: K): Boolean =
lookup(empty, k) == None
// Stored values can be deleted by key.
def mapLaw3[K, V](m: Map[K, V], k: K): Boolean =
lookup(delete(m, k), k) == None
// Demonstrates fullfilment of the spec for a few choices of `K`
// and `V`, up to some probabilistic factor.
// `scalacheck` is a library that randomly generates input cases
// for our laws and runs them, checking that they all come back true.
def test(): Unit = {
println("\nchecking Map[Int, String]")
forAll((m: Map[Int, String], k: Int, v: String) => mapLaw1(m, k, v)).check
forAll((k: Int) => mapLaw2(k)).check
forAll((m: Map[Int, String], k: Int) => mapLaw3(m, k)).check
println("\nchecking Map[String, Double]")
forAll((m: Map[String, Double], k: String, v: Double) => mapLaw1(m, k, v)).check
forAll((k: String) => mapLaw2(k)).check
forAll((m: Map[String, Double], k: String) => mapLaw3(m, k)).check
println("\nchecking Map[String, String]")
forAll((m: Map[String, String], k: String, v: String) => mapLaw1(m, k, v)).check
forAll((k: String) => mapLaw2(k)).check
forAll((m: Map[String, String], k: String) => mapLaw3(m, k)).check
}
test()
check with key = Int and value = String
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
check with key = String and value = Double
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
check with key = String and value = String
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
@friedbrice
Copy link
Author

This is something I whipped up in about 15 minutes. In particular, there might be some useful laws that I'm missing. This is only meant to demonstrate the general method.

@friedbrice
Copy link
Author

friedbrice commented Aug 14, 2019

I think a nice soundbite description of QuickCheck (and similar libraries, JSVerify and Scalacheck) is "Type-driven testing". By defining test case generation logic for basic scalar types and then doing straightforward induction on structured types, these libraries can automatically generate test cases for complex data types built up out of layers of records, lists, maps, tuples, unions, and even in some cases functions. These libraries can generate test cases that reach to the far corners of the input space, finding problem inputs that the developer would never have guessed to check by hand.

@friedbrice
Copy link
Author

friedbrice commented Aug 14, 2019

In Java and Javascript, adding property tests takes a bit of boilerplate. But that boilerplate is reusable, so it means that all it takes is a single method call to add 100 tests, covering cases you'd never even think to. Since I believe that tests are vitally important, that boilerplate is worth it to me. If you see the value in tests, I think you'd agree.

And if you're already on Scala or Haskell, then the boilerplate is mostly done for you, and adding 100 tests becomes a one-liner, so why the hell not?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment