The eqsat from taktoa

Improve matching algorithm to efficiently support axioms

We should support Term nodes with associativity (A), commutativity (C), unitality (U), and idempotency (I) axioms, and combinations thereof.

Unification for all of these is known to be decidable (and algorithms are known for them), though I haven't looked into efficiency for all of them.

Other resources

Maude Manual (Version 2.5)
Summer 2014 RISC class on Unification Theory
Loop detection in term rewriting using the eliminating unfoldings
A DPLL-based Theorem Prover for Coherent Logic
- Rete matching can be used (see Efficient Rule-Matching for Automated Coherent Logic) for first-order theorem proving in coherent logic, so this may be relevant. Also see Efficient Rule-Matching for Hyper-Tableaux.
Handbook of Automated Reasoning

Benchmarks for term-indexing data structures

Write property tests for `EqSat.TermIndex.Class`

TermIndex
Perfect
Mergeable
Removeable

Compile with `-XMonadFailDesugaring`

The MonadFailDesugaring extension allows us to catch any problems induced by the upcoming MonadFailProposal.

Implement a basic discrimination tree

Termination and confluence checking

Ideally, we could warn the user if the rewriting system they give is known not to be terminating and confluent. There is a sizable amount of research in this direction:

TTT2 uses a wide range of techniques for proving and disproving the termination of term-rewriting systems: approximated dependency graph, argument filtering, bounds, dependency pair method, Knuth-Bendix order, lexicographic path order, loop detection, matrix interpretation, polynomial interpretation, predictive labeling, recursive SCC, root labeling, semantic labeling, simple projection and subterm criterion, uncurrying, usable rules. It is written in OCaml.
ConCon is a confluence checker for conditional term rewriting systems. It is written in Scala. ConCon works by first trying to simplify rules, removing infeasible rules from the input system, and then employing the following three confluence criteria:
1. A quasi-decreasing strongly deterministic 3-CTRS is confluent if all its critical pairs are joinable.
2. An almost orthogonal extended properly oriented right-stable 3-CTRS is confluent.
3. A deterministic 3-CTRS R is confluent if its unraveling U(R) is left-linear and confluent.
CSI is a confluence checker for first-order term rewriting systems. CSI^ho is an extension of CSI for higher-order pattern rewriting systems. Both are written in OCaml.
CaT analyzes a term-rewriting system to figure out its computational complexity. It is written in OCaml.

you're valid

this is proof. not 'eqsat', just my words

Rewrite `EqSat.Internal.MHashMap` to use Judy arrays

I suspect there could be a performance improvement if we used Judy arrays for EqSat.Internal.MHashMap. We'd probably need to make our own typeclass that replaces Hashable with something that will work better with the performance characteristics of Judy arrays (since sparse keys are undesirable).

Figure out whether or not it is safe to use the functions from judy with unsafeIOToST.
Write a wrapper module over Data.Judy that exposes a cleaner interface using ST.
Write benchmarks for EqSat.Internal.MHashMap.
Write a typeclass for hashing into keys usable in Judy arrays.
Switch EqSat.Internal.MHashMap over to Judy arrays.

Build fails out of memory

When running
nix-build ./default.nix --no-out-link -Q
it stops saying

copying path '/nix/store/kis0zd9hw8bk8gfrpcq64y6vd7c724v5-source' from 'https://cache.nixos.org'...
copying path '/nix/store/vg0s4sl74f5ik64wrrx0q9n6m48vvmgs-glibc-locales-2.26-131' from 'https://cache.nixos.org'...
copying path '/nix/store/3fwjw1jxm7ll6hpfk2lwsnsd19yp4lzy-apr-1.6.3' from 'https://cache.nixos.org'...
copying path '/nix/store/b0zlxla7dmy1iwc3g459rjznx59797xy-binutils-2.28.1' from 'https://cache.nixos.org'...
copying path '/nix/store/zrqp1awj7xg2d72hx2ja60x3rc3j2fyv-cracklib-2.9.6' from 'https://cache.nixos.org'...
copying path '/nix/store/zmixfgjgbv301c7mxarvxs806dhn9ikg-cvs-1.12.13' from 'https://cache.nixos.org'...
copying path '/nix/store/xx9mdyxxqklcrj8jcdyx6ra47gwdz0bj-db-5.3.28' from 'https://cache.nixos.org'...
copying path '/nix/store/cg3yhpr5hfr00y0aah23pgxiijpzl6nz-diffutils-3.6' from 'https://cache.nixos.org'...
copying path '/nix/store/755x1h3h4s9vqk70cwg1hmfp3si7m2k8-cyrus-sasl-2.1.26' from 'https://cache.nixos.org'...
copying path '/nix/store/ww3am1r6i6yy8q0p84q3k1qa1xinfxxj-ed-1.14.2' from 'https://cache.nixos.org'...
copying path '/nix/store/1sq8mqjly01pb1nf471phgbgc71v12yy-expand-response-params' from 'https://cache.nixos.org'...
copying path '/nix/store/h48w6zjixk49mj6p1q25vhyknyml10sk-expat-2.2.5' from 'https://cache.nixos.org'...
copying path '/nix/store/364b5gkvgrm87bh1scxm5h8shp975n0r-findutils-4.6.0' from 'https://cache.nixos.org'...
copying path '/nix/store/j79xs2j519bmvq0gihz8ff4nw5aj3vlh-gawk-4.2.0' from 'https://cache.nixos.org'...
copying path '/nix/store/6nn4vpwqs4pvwp0q7whgbx1dzgsk0ch5-gdbm-1.14' from 'https://cache.nixos.org'...
copying path '/nix/store/mxjx0mml0ahhb4y2p20anqc6i7ms79xz-gettext-0.19.8' from 'https://cache.nixos.org'...
copying path '/nix/store/6ca5dl2wy0nh37li1n4b152fcazsp3f6-glibc-2.26-131-bin' from 'https://cache.nixos.org'...
copying path '/nix/store/8qfd8gx0j3yzamkrbrfz5kc00h4cqd1q-gmp-6.1.2' from 'https://cache.nixos.org'...
copying path '/nix/store/lhp5rw0dagi5mgqwr9i3x41240ba4ypz-gnumake-4.2.1' from 'https://cache.nixos.org'...
copying path '/nix/store/navldm477k3ar6cy0zlw9rk43i459g69-gnused-4.4' from 'https://cache.nixos.org'...
copying path '/nix/store/jbs6zz82d59znrc53xdbmc47qvmjwjzd-libffi-3.2.1' from 'https://cache.nixos.org'...
copying path '/nix/store/klyx4q30zahwy7d2hkgjs1ijwbxp2vwk-libtool-2.4.6-lib' from 'https://cache.nixos.org'...
copying path '/nix/store/yb9axzdqhnamqssl2i9l8kl30x22pcb9-libffi-3.2.1-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/f5qsrkj2fkv94j0d5h8ppx19qb65z5km-linux-headers-4.15' from 'https://cache.nixos.org'...
copying path '/nix/store/367ldm9q7cwc82698kdq438n53fbpz4c-linux-pam-1.3.0' from 'https://cache.nixos.org'...
copying path '/nix/store/p85kjy91dfvs4in358zyfxlksvibw0zn-glibc-2.26-131-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/069g827lh3hrhp4vkcq3rsh5jh65pm3l-ncurses-6.0-20171125' from 'https://cache.nixos.org'...
copying path '/nix/store/cmxaqb5cbzy4jk26na842n6hy1s4yn19-binutils-wrapper-2.28.1' from 'https://cache.nixos.org'...
copying path '/nix/store/bm7pb1s7rx1ad80706b5xqrznq7fgpgx-gcc-7.3.0' from 'https://cache.nixos.org'...
copying path '/nix/store/1zk7n2zckf1fm67ynav1mv45y1pmfpfn-libedit-20160903-3.1' from 'https://cache.nixos.org'...
copying path '/nix/store/04f09wchhzjw95099wsr97kcjd9l2jnx-nix-2.0-man' from 'https://cache.nixos.org'...
copying path '/nix/store/2bdmvf96s9bhb3zkpxjq9v5hvhs2wpny-openldap-2.4.45' from 'https://cache.nixos.org'...
copying path '/nix/store/m4ra4dv9sw6yh913ha4lqcaza1bbbr70-nix-2.0' from 'https://cache.nixos.org'...
copying path '/nix/store/d6f49b1c1770p8zijc79ykm2adw415ip-apr-util-1.6.1' from 'https://cache.nixos.org'...
copying path '/nix/store/w9s6rbk6s11gsgcwiw9x32x2pz8q5052-nix-prefetch-cvs' from 'https://cache.nixos.org'...
copying path '/nix/store/dk3hbw2lvhq4y3fgli1vjzk77fklj7n8-openssh-7.6p1' from 'https://cache.nixos.org'...
copying path '/nix/store/gd1mp76qr4zpbw3lccivhvi30b025x51-patch-2.7.6' from 'https://cache.nixos.org'...
copying path '/nix/store/y5rlyv6nz8134s687d95ysc2gakwx7am-patchelf-0.9' from 'https://cache.nixos.org'...
copying path '/nix/store/rf7pnq8qk9bkjpl4s2pm5dm2pk4yqhrc-paxctl-0.9' from 'https://cache.nixos.org'...
copying path '/nix/store/i75nslvdx1sk1p7rk0944x48spwdz3r0-pcre-8.41' from 'https://cache.nixos.org'...
copying path '/nix/store/jkxp76m7y3iai3ksn8n3agfmj8s92316-pcre2-10.23' from 'https://cache.nixos.org'...
copying path '/nix/store/s63b2myh6rxfl4aqwi9yxd6rq66djk33-gnugrep-3.1' from 'https://cache.nixos.org'...
copying path '/nix/store/s029gmjpgvm776wfb56naqny9qja9339-perl-5.24.3' from 'https://cache.nixos.org'...
copying path '/nix/store/gqg2vrcq7krqi9rrl6pphvsg81sb8pjw-gcc-wrapper-7.3.0' from 'https://cache.nixos.org'...
copying path '/nix/store/hg9wj640favvh0qcnh4ii74v12pamnxk-perl-Encode-Locale-1.05' from 'https://cache.nixos.org'...
copying path '/nix/store/g2bzsb86aqvb2zyaf9wyzvzm40ixr9dv-perl-HTML-Tagset-3.20' from 'https://cache.nixos.org'...
copying path '/nix/store/rrjfvxxwzy1k0rwb5ixxxzki3851v8dz-perl-HTTP-Date-6.02' from 'https://cache.nixos.org'...
copying path '/nix/store/lsqhqpzgv7sqsw3gw1k1k1lp03gifrvi-perl-HTML-Parser-3.72' from 'https://cache.nixos.org'...
copying path '/nix/store/6rq3lv4kk3z0gqahmy5kjybyjahjjhkf-perl-File-Listing-6.04' from 'https://cache.nixos.org'...
copying path '/nix/store/0sd6d8bxsrsff8h2iba1pqh8dpm99s2i-perl-CGI-4.38' from 'https://cache.nixos.org'...
copying path '/nix/store/6qxiv2qszczx2mp0mx8hrflalzs59alb-perl-IO-HTML-1.001' from 'https://cache.nixos.org'...
copying path '/nix/store/y06mvpsxh4phzgap1mlxax8ir3am1chs-perl-LWP-MediaTypes-6.02' from 'https://cache.nixos.org'...
copying path '/nix/store/d8wii8j951kwqq99sqqyp69h6dlhxhwk-perl-TermReadKey-2.37' from 'https://cache.nixos.org'...
copying path '/nix/store/qc04jc17k17h2xfl4v7iq865qidgcq8q-perl-URI-1.73' from 'https://cache.nixos.org'...
copying path '/nix/store/fpcmm6mylxldcy5ww13idv959ni7bd7c-readline-6.3p08' from 'https://cache.nixos.org'...
copying path '/nix/store/av46in3n3sahqjs3ydfdjfvkfbscggjw-perl-HTTP-Message-6.14' from 'https://cache.nixos.org'...
copying path '/nix/store/cqmmcd8llag0f7xhbahnq6a90sy5sbs7-perl-Net-HTTP-6.12' from 'https://cache.nixos.org'...
copying path '/nix/store/pz445bbfmc474xc7bcb5505y5wxh4l7d-perl-HTTP-Cookies-6.01' from 'https://cache.nixos.org'...
copying path '/nix/store/3c1ls4x6fkm63s290rrjw8vm1wpkhfn2-perl-HTTP-Daemon-6.01' from 'https://cache.nixos.org'...
copying path '/nix/store/z04yvzpw77k2w5wrfshnqi1kdy2g0f71-perl-HTTP-Negotiate-6.01' from 'https://cache.nixos.org'...
copying path '/nix/store/fnbham3mb5c511myjcsy5xds4hpgl38d-perl-WWW-RobotRules-6.02' from 'https://cache.nixos.org'...
copying path '/nix/store/nx3jw576gqw01iiijgsav39w2qa4cni2-python-2.7.14' from 'https://cache.nixos.org'...
copying path '/nix/store/nylnjq8pfmy5kkyaimqlhk92vxjf3bq4-perl-libwww-perl-6.15' from 'https://cache.nixos.org'...
copying path '/nix/store/aihd4bfifn17n34g3m2bivzpz2i86m05-python2.7-cffi-1.11.4' from 'https://cache.nixos.org'...
copying path '/nix/store/6lkl4g8jbg0m4fgl5s1jclafic2k6lhx-git-2.16.2' from 'https://cache.nixos.org'...
copying path '/nix/store/sdykyvsacalrznx2mi1j4m8pcm6fif2j-python2.7-cryptography-2.1.4' from 'https://cache.nixos.org'...
copying path '/nix/store/v2lvm5z30ky6gxw19g3a12m0vam5jfpj-nix-prefetch-git' from 'https://cache.nixos.org'...
copying path '/nix/store/xr3li4as4jycwk9lgqn08s0q9s86svqf-python2.7-setuptools-38.4.0' from 'https://cache.nixos.org'...
copying path '/nix/store/8nwhasclrspazf8wq0grp4jrldn9bmvj-serf-1.3.9' from 'https://cache.nixos.org'...
copying path '/nix/store/r1nhrw6rcfpi1v5yi7b9l9fcdbq9d656-python2.7-asn1crypto-0.24.0' from 'https://cache.nixos.org'...
copying path '/nix/store/a3qhl9b5v89b3gh0qjna6my1wl5vbqq7-python2.7-dulwich-0.18.6' from 'https://cache.nixos.org'...
copying path '/nix/store/6sx6q256adh3953syy37wbj1zad967fj-python2.7-enum34-1.1.6' from 'https://cache.nixos.org'...
copying path '/nix/store/6dgb8z6zcl0vdz91pdnvb3q7vi9ir5d1-python2.7-hg-git-0.8.10' from 'https://cache.nixos.org'...
copying path '/nix/store/q158xyfm6cizibdhpxy9jiim2s5d2yy5-python2.7-idna-2.6' from 'https://cache.nixos.org'...
copying path '/nix/store/d7gspk4njym9k88qk2a3sqjasi8ab2z6-mercurial-4.5' from 'https://cache.nixos.org'...
copying path '/nix/store/fgqr39hiajlhc5bvgjca7j7jjksf6p69-python2.7-ipaddress-1.0.18' from 'https://cache.nixos.org'...
copying path '/nix/store/2y12fqy6rbdfkfwbbn6sshafz38d6m45-nix-prefetch-hg' from 'https://cache.nixos.org'...
copying path '/nix/store/852miy07c56qa3am0gn92h9x2c0h91h1-python2.7-pyasn1-0.4.2' from 'https://cache.nixos.org'...
copying path '/nix/store/igpahydcmd4c3dzsvfq1szwwhxvblwff-python2.7-pycparser-2.14' from 'https://cache.nixos.org'...
copying path '/nix/store/vqp6ysnh5ppzkjxj9rq2c7mbfcizr1qz-python2.7-pyparsing-2.2.0' from 'https://cache.nixos.org'...
copying path '/nix/store/kf44m90k3mpayf6833z8acb9fw2akl3h-python2.7-cffi-1.11.4-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/z248x8a5fpp12m07zra6cf0f806cxzaw-python2.7-six-1.11.0' from 'https://cache.nixos.org'...
copying path '/nix/store/l3nz0167a4xhb78ldcjns5p4dwvlm1cw-stdenv' from 'https://cache.nixos.org'...
copying path '/nix/store/n992z6w0ay8ap999h4zica9rddjnmz2x-python2.7-packaging-16.8' from 'https://cache.nixos.org'...
copying path '/nix/store/7ql8gbcb514nhhkhrymi0vhr8xgbv13a-subversion-1.9.7' from 'https://cache.nixos.org'...
copying path '/nix/store/1lqdmpsn39a5598rbzjcsprgqznah1c3-python2.7-cryptography-2.1.4-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/2gam2db6kcch46pw36sk8lqib30b1fzb-nix-prefetch-svn' from 'https://cache.nixos.org'...
copying path '/nix/store/j907x6991b77p2qi9ar2plzacm356ihp-python2.7-paramiko-2.1.1' from 'https://cache.nixos.org'...
copying path '/nix/store/mwn8dp93ki2v14p6za9p64f9fhx3b4v2-bazaar-2.7.0' from 'https://cache.nixos.org'...
copying path '/nix/store/hjl4gv0ra9b3dilsz3v98xfyvaxsix5w-nix-prefetch-bzr' from 'https://cache.nixos.org'...
copying path '/nix/store/hxxmyv7mkh1mdqjan74ppcs54fi2l7na-nix-prefetch-scripts' from 'https://cache.nixos.org'...
copying path '/nix/store/m2zgzhxk7vn816p8rhkk979x1v0c6jgl-cabal2nix-2.9' from 'https://cache.nixos.org'...
building '/nix/store/sa078k2naqqrdfzw2mqr8f93rar7jcxh-cabal2nix-eqsat.drv'...
copying path '/nix/store/xnb387j16v56zbs6bvqgr7mgr00nrvgp-mirrors-list' from 'https://cache.nixos.org'...
copying path '/nix/store/ca2mb3ps7gbzvl6msp5da610rr1yk9za-c-ares-1.13.0' from 'https://cache.nixos.org'...
copying path '/nix/store/sc56lngngp80fpnqwj9c93ik9i418lfm-curl-7.59.0-bin' from 'https://cache.nixos.org'...
copying path '/nix/store/1f3mdwcckqa4zbpflilm8jc5h2kg5whj-curl-7.59.0-man' from 'https://cache.nixos.org'...
copying path '/nix/store/v254ddjpw0a4jwzp56kra7825lr6m926-libev-4.24' from 'https://cache.nixos.org'...
copying path '/nix/store/mxzv27c6s32syz8vibr35vshsy5zbszl-libkrb5-1.15.2-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/4yj9dld4jrapgx7y1fm04lkdib57zgds-libssh2-1.8.0-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/dwhx1bjb5lz1w75895gdi3rsrrr12sh1-nghttp2-1.24.0' from 'https://cache.nixos.org'...
copying path '/nix/store/0bgnx6v0i3zi6kpc4dnh98l8isix3rw2-openssl-1.0.2o-bin' from 'https://cache.nixos.org'...
copying path '/nix/store/gywkp5sn0x9qkwx17xj37v18j2l23ng9-nghttp2-1.24.0-bin' from 'https://cache.nixos.org'...
copying path '/nix/store/jd644x3ppch1i92lbiw837bd1rylqgip-openssl-1.0.2o-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/6rf6w17v62qlrjslyhygisivbllbmxvi-nghttp2-1.24.0-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/73jpvs9j0rk37xs3r61y3aldr9sh741h-stdenv' from 'https://cache.nixos.org'...
copying path '/nix/store/afs58x7k2mpgv9wdq5v6xr7g31jjihpl-unzip-6.0' from 'https://cache.nixos.org'...
copying path '/nix/store/8bsyix63bn598h4vr6zkx9r5yhv8f13r-zlib-1.2.11-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/2kgp3qkni59bvagdizcb8v6rdjzkw4km-curl-7.59.0-dev' from 'https://cache.nixos.org'...
building '/nix/store/k3k06m70srrmkxa44d0xl90m6dhv4gam-source.drv'...
building '/nix/store/q5wmwzqdl933bbjpzwd1i7bf69df1xy1-cabal2nix-sbv.drv'...
these derivations will be built:
  /nix/store/9qqw4chhl56va018gk6hcgk3psk3dn8x-remove-references-to.drv
  /nix/store/7dfzanq7bparfjcs9kqvk5b0lp7sr5xp-sbv-7.6.drv
  /nix/store/d8gw8jj5v22axnyp973rmjrhgapm888z-judy-0.4.0.drv
  /nix/store/l7kjfipp0ajzzzrbqmhfbjrcmrzr6d92-eqsat-0.1.0.drv
these paths will be fetched (145.48 MiB download, 1857.91 MiB unpacked):
  /nix/store/01a6kli2hgj3grnx210dm4h93qbfdj12-QuickCheck-2.10.1
  /nix/store/03bhwd0lsagh3khh6822lfjyyqv35r06-parallel-3.2.1.1
  /nix/store/07cb96b99ysn6crw4963y1xbh4n0dxl4-prettyprinter-1.1.1
  /nix/store/0a2ggsihbah1b5x45s412hk80f57cjng-flow-1.0.11
  /nix/store/0dgliyx1gm5nswqib8fklwkwmy65az45-serialise-0.2.0.0-doc
  /nix/store/0gblv6lgrd7271aiypwfhrzyflyq2xcc-concurrent-output-1.10.4-doc
  /nix/store/0ggcq5rdnsyza9sfpg42ab0mrja02w9z-mmorph-1.1.1-doc
  /nix/store/0ynv2a40isplhpafb25yqh79sg6r2qy4-ansi-wl-pprint-0.6.8.2-doc
  /nix/store/18wxf85hl2bv5m9csc50vy7n286n074z-haskell-lexer-1.0.1
  /nix/store/1av5g5h9icw05k6h1rw0kj422p97krq1-blaze-markup-0.8.2.0
  /nix/store/1dckhyck0mhbp3slzhs541mjy123jgld-foundation-0.0.17
  /nix/store/1hg9z36wnkd8d26vxwp0qp2g5w5v86n5-bifunctors-5.5.2
  /nix/store/1k2z4ihk3hixidd3c3qqxwxbm7kq6cp9-time-locale-compat-0.1.1.3
  /nix/store/1pm10qir5l0ihsbk3dy04ysby83h1852-kan-extensions-5.0.2-doc
  /nix/store/22n116h1b4q4cdvqwfh95lail2mblb47-data-binary-ieee754-0.4.4
  /nix/store/22rs4ivdc421nb4v6z0qdx9bidx8qh0n-prettyprinter-ansi-terminal-1.1.1.2
  /nix/store/276rp3g8jzals6b2vmq2b7d0sljmgxaf-terminal-size-0.3.2.1
  /nix/store/2li4inznhpz292bbimcblxfr4nvgp21l-contravariant-1.4.1
  /nix/store/2v1fm5xjbbvf5s5ipvyicmfaqwfqcd4b-transformers-compat-0.5.1.4-doc
  /nix/store/2xr5vxf0nc1vwjl91cc0iw0wk9xi6i6m-eigen-2.1.7-doc
  /nix/store/31sr26j211i4w2q0qkcv1ljpyvbc5i4f-uuid-types-1.0.3
  /nix/store/32y9h557zgjcdqpakw61a9l2xwvbmp44-aeson-1.2.4.0-doc
  /nix/store/33m05qk0n2pzch9c44bahpnn2qr0jjpj-unordered-containers-0.2.8.0
  /nix/store/345yiq4i450s27qfysfkjgqb2kh8932w-half-0.2.2.3-doc
  /nix/store/372pb2jv6wfsqwj0k3glqv1045kjqwsm-ieee754-0.8.0-doc
  /nix/store/376sby39gx4p2m5jk2zm8087zxr2w0ar-tasty-0.11.3
  /nix/store/377msli03s8vrhh0i0rblprra90xkb8f-mtl-2.2.2
  /nix/store/3ark6alf8lsxxf4bn2labi7yvfbcfnd3-hspec-discover-2.4.4
  /nix/store/3ld6viwpd07xwmwnmcrlg1n0z28qaprg-ansi-terminal-0.7.1.1-doc
  /nix/store/3lpa8kpfa7jc7plb8si0bkw829fkdvfd-vector-0.12.0.1
  /nix/store/3pq5ddmmaxfncmqq9pjp7ciyxjjh7589-ansi-wl-pprint-0.6.8.2
  /nix/store/3sr4g1rwmz5x88nq5nknxk1bg4ajclsl-system-filepath-0.4.14
  /nix/store/43bjz3whvvxzgyh60g38ka4m8lvv54w9-tasty-hedgehog-0.1.0.2-doc
  /nix/store/44kirdla5871dc9284jl641s3xwsln1m-loc-0.1.3.2-doc
  /nix/store/462d425w8s9801gphabqi4w90w0kkgab-foundation-0.0.17-doc
  /nix/store/4a7ri056ad60qx4llamc4xp49czxzfyn-integer-logarithms-1.0.2-doc
  /nix/store/4bgbaxjghbgzrak3dgcvscjzp7aar248-hspec-expectations-0.8.2
  /nix/store/4bik9z0fdi4h2qhhw5qjrc75lh793kw1-tf-random-0.5
  /nix/store/4c0xb5zfc4ichb2x10l6214amlbhabq0-basement-0.0.4-doc
  /nix/store/4drw9d3fcr0alsga5m2izl1awn3bw8bq-cborg-json-0.2.0.0-doc
  /nix/store/4hrmry9zd5phvsbyf3yjpdc01nzcjinb-concurrent-output-1.10.4
  /nix/store/4y7kxxjyj5mz6aws85is2dw0v10lzcf2-semigroups-0.18.4
  /nix/store/54gn0fkyg3ds5mi2392wnf4k8v7zncpi-optparse-applicative-0.14.2.0
  /nix/store/597jrxrqmqxi1kqyxc7xx1wlzfaqpd25-adjunctions-4.3-doc
  /nix/store/5cvjcnxly4v99fh6drmnynyc40j2zvhc-optparse-applicative-0.14.2.0-doc
  /nix/store/5kbcz0n38rm1phd0pjcwi1b7sm0k5bi4-semigroups-0.18.4-doc
  /nix/store/5lc6ykj5mhyrjnm91dq2sfygbwmramnh-aeson-1.2.4.0
  /nix/store/5n6852x6n9ry5pxcl5wwk57bz02n4p4j-monad-control-1.0.2.3
  /nix/store/5nzk1hnm07ndzv8yijmzixppn7y6q73a-StateVar-1.1.0.4
  /nix/store/5skjyv0kkgn3r2fbi3lwvqkwl79n9sc2-unliftio-core-0.1.1.0
  /nix/store/5yphp4zjray175vwlwb5aivawps8adv2-aeson-pretty-0.8.5-doc
  /nix/store/66h1ym61h77ck7q4dgwz36xyw1rahhyc-regex-tdfa-1.2.2
  /nix/store/693a5m3cwnfykv32rmm2shjixbwm4zd1-profunctors-5.2.2-doc
  /nix/store/69ddx9b0visz9h921ypr923261vaably-clock-0.7.2-doc
  /nix/store/6aq67c4idhmlz9qq3gsyng490m4kcy1f-quickcheck-io-0.2.0
  /nix/store/6g33xkyz80adraill6gdkq0b15mq3wsi-data-binary-ieee754-0.4.4-doc
  /nix/store/6ga3iaqnlnxhfb1zawzbyx6qqvz3cpn3-kan-extensions-5.0.2
  /nix/store/6kl9hkfwp5bi3qr7237n08h8xawmas0a-pretty-show-1.6.16-doc
  /nix/store/6yls3ffa4p4r9p7znk3i8hsib8jxwikq-dlist-0.8.0.4-doc
  /nix/store/71faj4rpspvh40c8j76qr2wj4006l4pz-logict-0.6.0.2-doc
  /nix/store/71gp5mcz59y71barnb6zz6qd822phsqw-generic-deriving-1.12.1
  /nix/store/74aqy5zmd2ca9igz4lvz2ylx896cn852-call-stack-0.1.0-doc
  /nix/store/74dvy84nfz0pqjnhb2ljymaqwmpf8sz5-streaming-0.2.0.0-doc
  /nix/store/7alb34qf4j4b045vcjra9l3p2mykz83l-unbounded-delays-0.1.1.0-doc
  /nix/store/7ax1h4jski0rbj7y4glx6v33dah15xid-compact-0.1.0.1-doc
  /nix/store/7fw4gbjrgl1d9gw0ynywxc65brlqrgn6-regex-tdfa-1.2.2-doc
  /nix/store/7n12aq40vwrw8h61p9mx4ph08s3bxcyr-prelude-extras-0.4.0.3
  /nix/store/7xyhqj9mzcmfr3x9csxsdd56zbkw71v1-dlist-0.8.0.4
  /nix/store/830bhck2cpchbiscilmrkh3i7qnhpv9h-flow-1.0.11-doc
  /nix/store/84yk1pb5azf41bc0g2li52mr0s0dn9p1-void-0.7.2-doc
  /nix/store/874js959bzilfql5hvsb5cx6sn9mdwq8-scientific-0.3.5.2-doc
  /nix/store/8armvgpg1y27hd4wxjqaq5lardasvyis-tagged-0.8.5-doc
  /nix/store/8h9d6cn02sldlb3naqfys5k2xg525jir-mmorph-1.1.1
  /nix/store/8hpqw16p67z2i5pbjjv27hqf46mnx6pq-primitive-0.6.3.0-doc
  /nix/store/8i63maq7chyxpjljcn96wz2nvd60n5mx-resourcet-1.1.11
  /nix/store/8jcnmxnzgxgmnlsvqgl8nihlhhklx11w-fail-4.9.0.0
  /nix/store/8rrqb5lqmz8zxbb4c9bmsllsi3i0vky9-constraints-0.9.1-doc
  /nix/store/939z3cx27gcpyg2c16vz0zpswqljflwa-terminal-size-0.3.2.1-doc
  /nix/store/958qpxv20v24ihwl5ap969d6m1zidjsx-data-partition-0.3.0.0-doc
  /nix/store/9j02r96v50lk5pqdm00azcq9p7bfli87-prelude-extras-0.4.0.3-doc
  /nix/store/9jl576bm6hlmwqjjk7485kbfb94grwiv-th-lift-0.7.8
  /nix/store/9phasb26lr2s4rw0fhhra0rfif0bpnrj-semigroupoids-5.2.1
  /nix/store/9x4gw2465hb440q4nzg0pswj2cymlbif-cmdargs-0.10.20
  /nix/store/9yw0iwisqjfsbq1510jysarz9yhngzm2-z3-4.6.0
  /nix/store/a0lm2vc1adkrlhbjwpck8gdngsd41d52-ansi-terminal-0.7.1.1
  /nix/store/a4plb8q1l6jzwbcxfqjbi6yk2bb62bgz-blaze-builder-0.4.0.2
  /nix/store/a9b04flsh2vf9ivaaf5mpzhsmcfv87ak-base-compat-0.9.3
  /nix/store/aa3hhz6dj1xqpvih3kc7zb5h7gmj6dw4-hspec-core-2.4.4-doc
  /nix/store/akspb3hyzrn0lqmr9g7nd1jxw4z73aca-regex-base-0.93.2
  /nix/store/ar0nlbyiam6maz477sl03vkan8na5zyz-async-2.1.1.1-doc
  /nix/store/ax6wmnjpiqi7l22j12ynwkkgz23009vd-unexceptionalio-0.3.0
  /nix/store/azadpshaxz2sggag23hiw9m926kqlgmq-base-orphans-0.6
  /nix/store/azzl4im7smzngsi1j5l6k2nkvlqyn1az-exceptions-0.8.3
  /nix/store/b78zg0rmhr3rzi8cp4j5kjamz343kmrg-clock-0.7.2
  /nix/store/b83bwwn0k4kaygm1vq86sglxzzgi3rhz-lifted-async-0.9.3.3
  /nix/store/bb0fk34hy196ldsbf0sabzxpgqnnab2l-cereal-0.5.5.0-doc
  /nix/store/bjv2y678q4jyzf94gkjixfzv7jhq75w5-cborg-0.2.0.0-doc
  /nix/store/br0rfcy62rb03is4cvmqzvp6y7irvg53-ieee754-0.8.0
  /nix/store/br676dryris7yv3b93j94mhqw1dkadxa-syb-0.7-doc
  /nix/store/bv21jg8jd3pci5n0x5g0qydmpxphdnd0-async-2.1.1.1
  /nix/store/bz3619rchggscak8axfk481b9pjcvfmg-unliftio-core-0.1.1.0-doc
  /nix/store/bzxdzckz2zrfz2m62wsfhxxn01k87gw8-logict-0.6.0.2
  /nix/store/c4zl1229ivjn0qza52p6q56p5130vry1-transformers-compat-0.5.1.4
  /nix/store/c5yacdqy31crr3m3jr2w29fvq71whd2z-syb-0.7
  /nix/store/chszzmrvcv9y814y5lzz45s1vh2a6fx5-lifted-base-0.2.3.11-doc
  /nix/store/cihbfiqyppfklys58gqda1xi6948advp-old-locale-1.0.0.7
  /nix/store/ck8yfryrc0469lbyq7485yk7ssad6y3i-tasty-html-0.4.1.1-doc
  /nix/store/d00vqd8z3pah3d0b3p4vqrwhnknz3w3v-distributive-0.5.3
  /nix/store/d7slj283b99hxx4zbbllpwqa3zn34scj-haskell-lexer-1.0.1-doc
  /nix/store/dc5p1wnr96dzldf8q69xbk74m0s7nl9f-judy-1.0.5
  /nix/store/dlln7z1m8p6mgwkmhasfjq2vi3jdzlyp-text-1.2.2.2-doc
  /nix/store/dswas9ahspg47rga88pa0s681s51a5kk-tasty-smallcheck-0.8.1-doc
  /nix/store/dvqfwac51d4sqmf0scx4rzad97zljny0-constraints-0.9.1
  /nix/store/dx5gyp20dvk05895l219x5sws9b70x5q-pretty-show-1.6.16
  /nix/store/f403dpy4l6p3rgkzr1cc61ww18bc898v-data-partition-0.3.0.0
  /nix/store/f8xacp1ifpyh0igm5cmgvz8n5ffzp91a-uuid-types-1.0.3-doc
  /nix/store/fjq3x5x9b2x5mrymgc0agyqg8f2a0mqg-lifted-base-0.2.3.11
  /nix/store/fw3yrxfrf55hj391d12rhk2x5vvr2z5w-ghc-8.2.2-doc
  /nix/store/g021rvfn4b6qv65z49xrvkr67785lxlb-lifted-async-0.9.3.3-doc
  /nix/store/g504kpwnlq16r7jcf9702c29j6459nw1-blaze-html-0.9.0.1-doc
  /nix/store/g6v1fwl88ihzb3kvz63sngzg1di25457-bifunctors-5.5.2-doc
  /nix/store/gd788x1f7353cirq2z8wqnvbgjsfypmv-setenv-0.1.1.3
  /nix/store/gf56aih36m3ncd98l6rlk91zjp32vzsa-system-filepath-0.4.14-doc
  /nix/store/gr5x2sdx5mlp7b1hdgl60dh1lxwinc4q-hspec-2.4.4-doc
  /nix/store/grclmfyisbv3728a2y5r4134wyn9xzq8-attoparsec-0.13.2.2
  /nix/store/gx4kilvjdxvxp9b7a4pk83gnygzbadb7-monad-control-1.0.2.3-doc
  /nix/store/gy5vbz3piw95m16l841hhcv026spn2wz-compact-0.1.0.1
  /nix/store/h1kl8xax8x18hh4g97gsxbmlbiha23z8-prettyprinter-1.1.1-doc
  /nix/store/h1mzgkzg7j7j7vfar8kjzlrw8h99y359-colour-2.3.4-doc
  /nix/store/hqk2qfdhf5nrfmds42ng1z1il696cyzp-judy-0.4.0.tar.gz
  /nix/store/hsy4fspf5xlhwnz25aj4x6cwzh06drbh-pretty-show-1.6.16-data
  /nix/store/hw5v43jkzcsmip71ad4k7r0akpzig73r-old-locale-1.0.0.7-doc
  /nix/store/hwvkgsv4sald1mndyrl2c2hin9npmvqc-parallel-3.2.1.1-doc
  /nix/store/i6f1r0nxsr76w9mfmww58daz6ddlzf45-distributive-0.5.3-doc
  /nix/store/ia04mv16mgqb8lhqzzicmg5vjk5jxsx6-hashable-1.2.6.1
  /nix/store/ia7r1x0hiikx1xgs60g5fhh89v5j413w-cereal-0.5.5.0
  /nix/store/iib9g1dhqqgbkb5p752kcrgn497g3zyg-eigen-2.1.7
  /nix/store/ijf4jp7ggwpl8jillfpaalffyaqr1pha-hspec-core-2.4.4
  /nix/store/ipnb9a7s2pq7hqxsxrsdm3dppqqkfiqm-hedgehog-0.5.2-doc
  /nix/store/iqasnbb0ml00lm6nwxl136cx6brg8p1c-th-abstraction-0.2.6.0
  /nix/store/ivmyjhsb4xx9iw4xi9fxidjf7w1sgrym-crackNum-1.9-doc
  /nix/store/j116vbs3c4az3vd7d5nmw0pprhdy33y7-free-4.12.4-doc
  /nix/store/j11ci3m98f2iywq43mmyifzp58ps74ga-exceptions-0.8.3-doc
  /nix/store/j1vkq3l3bpic2krn8c9y2n73knjrlwd8-nondeterminism-1.4-doc
  /nix/store/j76kgvldzlkccbzlrfhm0b7bx81z0y4q-loc-0.1.3.2
  /nix/store/jis5nl5q51mjkkpn48n4xn292g38hcmv-hspec-2.4.4
  /nix/store/jpg2gr46jjwkg6mfsgz3ry3xall586p4-smallcheck-1.1.3.1
  /nix/store/jq1n8kk77q260r89yjkv0l2zar4cy9cs-StateVar-1.1.0.4-doc
  /nix/store/k4d0cl2wnaz180h9rjn5j4yqxm68q9dp-transformers-base-0.4.4-doc
  /nix/store/kd7za26fyf9ndfj3ncfyl5kw71ki2xdr-base-orphans-0.6-doc
  /nix/store/ki4imydg1cibh2vi5nq9fnsa50ypyxsk-FloatingHex-0.4-doc
  /nix/store/l5r1dz0k19q43iy40z2dy6ixvlp3hrwv-base-compat-0.9.3-doc
  /nix/store/l82bis8gxfrcg73g8byy5yspbll4nyyq-HUnit-1.6.0.0
  /nix/store/l8d59jp4h0kl2vmz1g2isgyrgc2l914f-integer-logarithms-1.0.2
  /nix/store/lfisdzb3m816qn0ix02g3ni9d4wz74nc-text-short-0.1.1
  /nix/store/libfzcyi024b4n9g4mhsps4s13bm3m7l-cmdargs-0.10.20-doc
  /nix/store/ljid93q69wa2fv8y4q7hasnxcwiricpk-adjunctions-4.3
  /nix/store/ljn1b8xx4hcsifx6hhkhp7yx407p3p4s-colour-2.3.4-data
  /nix/store/lmj6wsg346njmi6hfw7g88l9a8m6xk72-impure-containers-0.4.3
  /nix/store/lqlnfggjz44p2abyfyfnqa79f2v72syv-HUnit-1.6.0.0-doc
  /nix/store/ls4zrc3hfm77jpbssxkl5nmrsjgv3b2x-random-1.1-doc
  /nix/store/m25s9mj64mhgl29092bay68ay5q2dfg2-unexceptionalio-0.3.0-doc
  /nix/store/m2fcy1z47ijnrz505lwrhax6laqjdc32-vector-0.12.0.1-doc
  /nix/store/m6pr20728abhcbm284hrsih0ifdk08ih-time-locale-compat-0.1.1.3-doc
  /nix/store/m81i5hd8r33j3pmf7a6n4hzzxvwx97jy-lens-4.15.4-doc
  /nix/store/miqy2v6dz3s1696xv6fv46jvfzasw6in-tf-random-0.5-doc
  /nix/store/mmhdqindrpvg91a2vnrr76vxcn5a4n0x-ghc-8.2.2
  /nix/store/mw05jsns6xshaq5i8az0d8igqcw7w8y6-prettyprinter-ansi-terminal-1.1.1.2-doc
  /nix/store/mz9ix8v1vnx1g2f6zyz26vswb14nagx5-cborg-json-0.2.0.0
  /nix/store/naz52y9jkz68dila8pk4zgz2kk3g6cfr-crackNum-1.9
  /nix/store/ncbnn9jlmsydp18skh9qaciii6mx622s-basement-0.0.4
  /nix/store/ng9waq13xwvladnjmkjpawxp341fcw82-impure-containers-0.4.3-doc
  /nix/store/nnhjxilii381m1s4b1sqw6iixm1410ag-tasty-hunit-0.9.2-doc
  /nix/store/nx0988pbwrb736dlw02cjkilfsbxmj8k-contravariant-1.4.1-doc
  /nix/store/nygn85xwk5g1xwn3bdq53g85h2ri93f2-th-abstraction-0.2.6.0-doc
  /nix/store/nz9p3mfniszmjdh5h3c8i1b6g6mcs4sd-tasty-html-0.4.1.1-data
  /nix/store/nzk7pa1x277xyzgr5z22xgyxl5j1rp6v-aeson-pretty-0.8.5
  /nix/store/p0hdf2v65dbwl14d5b8ywcwv9zgw3k6g-mtl-2.2.2-doc
  /nix/store/p2cdxn9kilkafj082ccdh2db4k3n4zwa-unordered-containers-0.2.8.0-doc
  /nix/store/p2yx3g4d2ric2l92hs2xhcwr600p90j0-free-4.12.4
  /nix/store/p69rydp1sw7j5r1a5hbzfp1xfg5rkzpg-call-stack-0.1.0
  /nix/store/pm4an9phkkg7lrfc7517vysdsw8g3h5c-quickcheck-io-0.2.0-doc
  /nix/store/pmahqabys6yxq2ackyy8rk3gvlp5s0sn-nondeterminism-1.4
  /nix/store/pnz8m9nnnrj0yyn29alv3r0wds1n1bn6-tagged-0.8.5
  /nix/store/pr6qlj8494gc1y5i7vcl20918zbcbx9i-parsec-3.1.13.0
  /nix/store/prpq81799slxszayny96shhhgkj5y6dz-blaze-builder-0.4.0.2-doc
  /nix/store/q17g2cijq6bv06p0f92mqh06snhszb1x-parsec-3.1.13.0-doc
  /nix/store/q3hh4aa3a6ldz6ld5dghx99vi78ny1v9-tasty-0.11.3-doc
  /nix/store/q77a9qx65s4f6wqxsinyvd6v0ng2rj32-random-1.1
  /nix/store/q7nsx3vpf4qnkxm4rqvlklh3y1ghb1ws-smallcheck-1.1.3.1-doc
  /nix/store/qirnpr5qh5hwnyczzlm52w8jan46fsyc-hashable-1.2.6.1-doc
  /nix/store/qkhdzn1lqh8qamyrryryr4iqy32j4gsw-serialise-0.2.0.0
  /nix/store/qlzq2kfzzhv1kcskqllc2s5bzqhgkl23-vector-algorithms-0.7.0.1-doc
  /nix/store/r4sxf36i00lqaq9s0r3rhvwfa4qs2b76-generic-deriving-1.12.1-doc
  /nix/store/rbyrmq20jhb3bl96wfzcf9zbx4xjcdgk-transformers-base-0.4.4
  /nix/store/rvd2vj6msx7pq6k3p1m8ns0kqxpjwqza-FloatingHex-0.4
  /nix/store/s2j6gahnn8wa5pnjml6bhjhvnxsnzr5f-tasty-hedgehog-0.1.0.2
  /nix/store/s6yqzw184ff23p4xmmy4mcmb1wnhb41w-QuickCheck-2.10.1-doc
  /nix/store/s74rviw0nd14s2rd3frq25kn8rf0ayv1-streaming-0.2.0.0
  /nix/store/s9axsfca33b1jbp2rjxm9ardi40sxwzj-colour-2.3.4
  /nix/store/sb53i9k8h4c2yka9g29dnj9bsdv4rv2a-text-1.2.2.2
  /nix/store/sdy9z08b1dzxvgla15yg0zw8nhdhr1d0-vector-algorithms-0.7.0.1
  /nix/store/sfkfcm1jwpwrwccfs0vidc098i4x0k0j-stm-2.4.5.0-doc
  /nix/store/sjr7k4h86cvy3kmdmjyw776c82bgyyc6-void-0.7.2
  /nix/store/sq7vph5b5m12s0d5rcab5pj69x4axlz8-scientific-0.3.5.2
  /nix/store/sxhf67z0dn6613w0jv3jmn0p6yllrzm7-hscolour-1.24.2
  /nix/store/v4xwg8wn1dy9mnd82jjg63xzwn5zk2vz-resourcet-1.1.11-doc
  /nix/store/v9j77xli23ka09sfbpfi0c1zfd14jkxf-wl-pprint-annotated-0.1.0.0-doc
  /nix/store/vg22ynh0yni1347y7244n41i84ll7irl-reflection-2.1.3-doc
  /nix/store/vi2ic3v5dn7swv6l9fbr6s67ivbbhcgm-lens-4.15.4
  /nix/store/vrklj3jwzfjbcl0gddzv6c3qq7l23f8h-primitive-0.6.3.0
  /nix/store/vsa6cym9fifqln5kwscmbqwa7ifw7fib-tasty-smallcheck-0.8.1
  /nix/store/w3qc97b4hzfamd5ia159z847r66kv1z3-hspec-expectations-0.8.2-doc
  /nix/store/w5v8ks80h3n1wl3prhnh40rfnhd5fqxw-comonad-5.0.3
  /nix/store/widh0f3cn8r3j6apjqw6wmq4cndax180-half-0.2.2.3
  /nix/store/x1pp3lv4z3as64n7gljdywnq2sdp10gb-reflection-2.1.3
  /nix/store/x4mpkqdsnmnlywppdjkbqk4dijn6vph8-attoparsec-0.13.2.2-doc
  /nix/store/x78bq3aq80ygi5580z14pv5w0c7l5kjc-blaze-html-0.9.0.1
  /nix/store/xil0a43diay58wwzhgd0km70h02lcf7b-setenv-0.1.1.3-doc
  /nix/store/xpq63ijk6xaij3a3afn2ix2x9v5mjdf3-hspec-discover-2.4.4-doc
  /nix/store/xw145nrkxhzm4q2y0lwsgj7m31k0gc72-cborg-0.2.0.0
  /nix/store/y3f9qxjwk4zwrp9wv6qp0n0lfmmg9avz-stm-2.4.5.0
  /nix/store/y3i33b153qrk9d9ln1yn60rihwb4dv5n-gmp-6.1.2-dev
  /nix/store/yb39mjiirga3ppfm6dq6ypvh5kf954jr-regex-base-0.93.2-doc
  /nix/store/yhyv6rqszgbr9qax7i3y78npj4qkrnw2-th-lift-0.7.8-doc
  /nix/store/ypdhws0sikrqjyp8d7rqih5s5gybww4w-hedgehog-0.5.2
  /nix/store/ypsmvqpi4ggf70cdscvz1088x7vd7j4h-wl-pprint-annotated-0.1.0.0
  /nix/store/ys80jgas2kjg3jxnl2d5d60l54zm38ax-tasty-hunit-0.9.2
  /nix/store/yzs4fspmmjgv0641f2gcwqix46j79gy6-tasty-html-0.4.1.1
  /nix/store/z0yrlq1fdy5y0p72mys6wp1pdsniknyx-profunctors-5.2.2
  /nix/store/z4zylwq5fy36fx2wnlmvv1k2w7gikqns-text-short-0.1.1-doc
  /nix/store/z9cdcsqc98rn0bgswa1kwhnppbdi5lw9-semigroupoids-5.2.1-doc
  /nix/store/zcawbjc0pziiqmxpwyhqdccl4lx1yrz0-blaze-markup-0.8.2.0-doc
  /nix/store/zjjydl675zp7zqsdmc7gpy7ihcqimlkq-unbounded-delays-0.1.1.0
  /nix/store/zrn56nx31r4582hy8hjilhdcbxxfll7q-comonad-5.0.3-doc
copying path '/nix/store/nz9p3mfniszmjdh5h3c8i1b6g6mcs4sd-tasty-html-0.4.1.1-data' from 'https://cache.nixos.org'...
copying path '/nix/store/kd7za26fyf9ndfj3ncfyl5kw71ki2xdr-base-orphans-0.6-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/ljn1b8xx4hcsifx6hhkhp7yx407p3p4s-colour-2.3.4-data' from 'https://cache.nixos.org'...
copying path '/nix/store/8jcnmxnzgxgmnlsvqgl8nihlhhklx11w-fail-4.9.0.0' from 'https://cache.nixos.org'...
copying path '/nix/store/fw3yrxfrf55hj391d12rhk2x5vvr2z5w-ghc-8.2.2-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/y3i33b153qrk9d9ln1yn60rihwb4dv5n-gmp-6.1.2-dev' from 'https://cache.nixos.org'...
copying path '/nix/store/ki4imydg1cibh2vi5nq9fnsa50ypyxsk-FloatingHex-0.4-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/lqlnfggjz44p2abyfyfnqa79f2v72syv-HUnit-1.6.0.0-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/jq1n8kk77q260r89yjkv0l2zar4cy9cs-StateVar-1.1.0.4-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/ar0nlbyiam6maz477sl03vkan8na5zyz-async-2.1.1.1-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/l5r1dz0k19q43iy40z2dy6ixvlp3hrwv-base-compat-0.9.3-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/4c0xb5zfc4ichb2x10l6214amlbhabq0-basement-0.0.4-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/74aqy5zmd2ca9igz4lvz2ylx896cn852-call-stack-0.1.0-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/bb0fk34hy196ldsbf0sabzxpgqnnab2l-cereal-0.5.5.0-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/69ddx9b0visz9h921ypr923261vaably-clock-0.7.2-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/libfzcyi024b4n9g4mhsps4s13bm3m7l-cmdargs-0.10.20-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/h1mzgkzg7j7j7vfar8kjzlrw8h99y359-colour-2.3.4-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/7ax1h4jski0rbj7y4glx6v33dah15xid-compact-0.1.0.1-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/3ld6viwpd07xwmwnmcrlg1n0z28qaprg-ansi-terminal-0.7.1.1-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/nx0988pbwrb736dlw02cjkilfsbxmj8k-contravariant-1.4.1-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/0ynv2a40isplhpafb25yqh79sg6r2qy4-ansi-wl-pprint-0.6.8.2-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/ivmyjhsb4xx9iw4xi9fxidjf7w1sgrym-crackNum-1.9-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/6g33xkyz80adraill6gdkq0b15mq3wsi-data-binary-ieee754-0.4.4-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/958qpxv20v24ihwl5ap969d6m1zidjsx-data-partition-0.3.0.0-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/6yls3ffa4p4r9p7znk3i8hsib8jxwikq-dlist-0.8.0.4-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/830bhck2cpchbiscilmrkh3i7qnhpv9h-flow-1.0.11-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/462d425w8s9801gphabqi4w90w0kkgab-foundation-0.0.17-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/r4sxf36i00lqaq9s0r3rhvwfa4qs2b76-generic-deriving-1.12.1-doc' from 'https://cache.nixos.org'...
copying path '/nix/store/mmhdqindrpvg91a2vnrr76vxcn5a4n0x-ghc-8.2.2' from 'https://cache.nixos.org'...
error: out of memory
$

Being at Xubuntu, Linux somename 4.4.0-127-generic #153-Ubuntu SMP Sat May 19 10:58:46 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

Implement a basic substitution tree

Allow conditional rewriting

Using the techniques described in From Conditional to Unconditional Rewriting by Grigore Roşu, we should be able to convert a conditional TRS (term-rewriting system) into an unconditional TRS, allowing us to expose an API that allows conditional rewriting without changing anything about our current matching or rewriting algorithms. This would probably be fairly useful in writing axioms, so we should support it.

Figure out how the Equation type should change to support conditional rewriting rules.
Read the papers and investigate which algorithm makes the most sense for our application.
Implement the algorithm.

EDIT: another related paper by the same research group

Use `streaming` for all situations where we currently take callbacks

In many parts of this library, we take callbacks as input, mainly as a way of avoiding intermediate allocations and to allow equality saturation to be an "anytime" algorithm. We should replace these with a stream processing library like pipes or streaming. Since this library is meant to be performant, we will probably want to go with streaming.

This could also make it possible to do even more optimizations; for example, it might make sense to have equality saturation emit a stream of differences to the equality proof tree, rather than re-emitting the proof tree every time. It also naturally supports incrementalization: it could accept a Producer for diffs to the original Term.

This idea is courtesy of @mckeankylej

Implement online algorithm for strongly-connected components

It seems like it would be quite useful (e.g.: for implementing perfect sharing) to maintain the graph of strongly-connected components of a PEG/EPEG while we build up the graph. The current state of the art online algorithm for computation of strongly-connected components is described in A New Approach to Incremental Cycle Detection and Related Problems. Technically there are two algorithms described in that paper: one that has the best known complexity bound for sparse graphs and one that has the best bound for dense graphs. It seems likely to me that PEGs are mostly going to be sparse, though I may be underestimating the amount of sharing they have. Of course, in this regime I suspect the constant factors may matter more than the difference between an O(min(m^{3/2}, mn^{2/3})) algorithm and an O(n^2 log(n)) algorithm.

Finish writing laws for classes in EqSat.TermIndex.Class

TermIndex
Perfect
Mergeable
Removeable

Spin off EqSat.TermIndex.* into a separate package

Our term indexing data structures could be useful for other Haskell projects, such as Hoogle or Idris or Agda. We should put them in a separate package, ideally with not too many dependencies.

Implement the Rete algorithm for pattern matching

The current pattern matching algorithm is inefficient, as it repeats a lot of work. The original equality saturation implementation (Peggy) used the Rete algorithm to cache pattern matches, but the implementation seems complicated, so I wrote a simple but expensive version to start out (and so that we can more easily test the Rete implementation once it is written).

taktoa / eqsat Goto Github PK

eqsat's People

Contributors

Stargazers

Watchers

Forkers

eqsat's Issues

Other resources

Recommend Projects

Recommend Topics

Recommend Org