{"action":"closed","number":123,"pull_request":{"url":"https://api.github.com/repos/snowleopard/alga/pulls/123","id":220286781,"node_id":"MDExOlB1bGxSZXF1ZXN0MjIwMjg2Nzgx","html_url":"https://github.com/snowleopard/alga/pull/123","diff_url":"https://github.com/snowleopard/alga/pull/123.diff","patch_url":"https://github.com/snowleopard/alga/pull/123.patch","issue_url":"https://api.github.com/repos/snowleopard/alga/issues/123","number":123,"state":"closed","locked":false,"title":"Optimize foldg, fmap, induce and transpose composition","user":{"login":"nobrakal","id":6417395,"node_id":"MDQ6VXNlcjY0MTczOTU=","avatar_url":"https://avatars1.githubusercontent.com/u/6417395?v=4","gravatar_id":"","url":"https://api.github.com/users/nobrakal","html_url":"https://github.com/nobrakal","followers_url":"https://api.github.com/users/nobrakal/followers","following_url":"https://api.github.com/users/nobrakal/following{/other_user}","gists_url":"https://api.github.com/users/nobrakal/gists{/gist_id}","starred_url":"https://api.github.com/users/nobrakal/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nobrakal/subscriptions","organizations_url":"https://api.github.com/users/nobrakal/orgs","repos_url":"https://api.github.com/users/nobrakal/repos","events_url":"https://api.github.com/users/nobrakal/events{/privacy}","received_events_url":"https://api.github.com/users/nobrakal/received_events","type":"User","site_admin":false},"body":"Hi,\r\n\r\nThis is the code concerning the optimization I described in my last blog article: [Rewrite rules and a specific fold: use optimization techniques from GHC.Base](https://blog.nyarlathotep.one/2018/09/rewrite-rules-and-a-specific-fold/).\r\n\r\nIt is the same ideas than the rules behind `foldr . map` optimization.\r\n\r\nThese rules are made only for `Algebra.Graph` using `Algebra.Graph.Fold` (to avoid  circular dependencies, I have moved a part of the `Algebra.Graph.Fold` into a new module `Algebra.Graph.Fold.Internal` ).\r\n\r\nA quick benchmark, using Criterion:\r\n\r\n```Haskell\r\nimport Algebra.Graph\r\nimport Control.DeepSeq\r\nimport Criterion.Main\r\n\r\nmain :: IO ()\r\nmain = defaultMain\r\n  [ bgroup \"foldgFusion\"\r\n    [ bench \"foldg\" $ nf (foldg 0 (+1) (+) (+)) $!! grInt\r\n    , bench \"foldg . induce\" $ nf (foldg 0 (+1) (+) (+) . induce (/= 2)) $!! grInt\r\n    , bench \"foldg . transpose\" $ nf (foldg 0 (+1) (+) (+) . transpose) $!! grInt\r\n    , bench \"foldg . fmap\" $ nf (foldg 0 (+1) (+) (+) . fmap (+1)) $!! grInt\r\n    ]\r\n    \r\n  , bgroup \"fmapFusion\"\r\n    [ bench \"fmap\" $ nf (fmap (+1)) $!! grInt\r\n    , bench \"fmap . fmap\" $ nf (fmap (+1) . fmap (+1)) $!! grInt\r\n    ]\r\n    \r\n  , bgroup \"transposeRewriteBack\"\r\n    [ bench \"transpose\" $ nf (transpose . vertices) $!! intList\r\n    , bench \"transpose'\" $ nf (foldg Empty Vertex Overlay (flip Connect) . vertices) $!! intList\r\n    ]\r\n\r\n  ,  bgroup \"induceRewriteBack\"\r\n    [ bench \"induce\" $ nf (induce (/=1) . vertices) $!! intList\r\n    , bench \"induce'\" $ nf (induce' (/= 1) . vertices) $!! intList\r\n    ]\r\n  ]\r\n\r\ngrInt :: Graph Int\r\ngrInt = vertices intList\r\n\r\nintList :: [Int]\r\nintList = [0..9999]\r\n\r\ninduce' :: (a -> Bool) -> Graph a -> Graph a\r\ninduce' p = foldg Empty (\\x -> if p x then Vertex x else Empty) (k Overlay) (k Connect)\r\n  where\r\n    k _ x     Empty = x -- Constant folding to get rid of Empty leaves\r\n    k _ Empty y     = y\r\n    k f x y = f x y\r\n```\r\n\r\n* \"foldgFusion\" test if the fusion between foldg and an other function happen correctly\r\n* \"fmapFusion\" test if the fusion between two fmap and an other function happen correctly\r\n* \"transposeRewriteBack\" test that there is no impact on \"normal\" code (like a `transpose` alone)\r\n* \"induceRewriteBack\" test that there is no impact on \"normal\" code (like a `fmap` alone)\r\n\r\n```\r\nbenchmarking foldgFusion/foldg\r\ntime                 103.8 μs   (103.4 μs .. 104.3 μs)\r\n[...]\r\n\r\nbenchmarking foldgFusion/foldg . induce\r\ntime                 110.1 μs   (109.8 μs .. 110.5 μs)\r\n[...]\r\n\r\nbenchmarking foldgFusion/foldg . transpose\r\ntime                 100.2 μs   (100.1 μs .. 100.3 μs)\r\n[...]\r\n\r\nbenchmarking foldgFusion/foldg . fmap\r\ntime                 97.71 μs   (97.56 μs .. 97.90 μs)\r\n[...]\r\n\r\nbenchmarking fmapFusion/fmap\r\ntime                 224.7 μs   (224.5 μs .. 225.0 μs)\r\n[...]\r\n\r\nbenchmarking fmapFusion/fmap . fmap\r\ntime                 224.5 μs   (224.2 μs .. 225.0 μs)\r\n[...]\r\n\r\nbenchmarking transposeRewriteBack/transpose\r\ntime                 134.5 μs   (132.7 μs .. 137.2 μs)\r\n[...]\r\n\r\nbenchmarking transposeRewriteBack/transpose'\r\ntime                 214.8 μs   (209.2 μs .. 219.5 μs)\r\n[...]\r\n\r\nbenchmarking induceRewriteBack/induce\r\ntime                 383.6 μs   (381.7 μs .. 386.8 μs)\r\n[...]\r\n\r\nbenchmarking induceRewriteBack/induce'\r\ntime                 376.3 μs   (372.4 μs .. 382.6 μs)\r\n[...]\r\n```\r\n\r\nNote that this will not improve directly alga's benchmarks and will \"only\" improve user code, as displayed int the benchmarks.\r\n\r\nThere is certainly a lot of polishing to do, but the main idea is here :)","created_at":"2018-10-04T08:15:38Z","updated_at":"2018-11-18T18:39:06Z","closed_at":"2018-11-18T18:39:06Z","merged_at":"2018-11-18T18:39:06Z","merge_commit_sha":"ba51378ce960782b959ff3298dd015bc9ef42e46","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/snowleopard/alga/pulls/123/commits","review_comments_url":"https://api.github.com/repos/snowleopard/alga/pulls/123/comments","review_comment_url":"https://api.github.com/repos/snowleopard/alga/pulls/comments{/number}","comments_url":"https://api.github.com/repos/snowleopard/alga/issues/123/comments","statuses_url":"https://api.github.com/repos/snowleopard/alga/statuses/6d95182af2690cfc657d7b326deedd8bdf3e179b","head":{"label":"nobrakal:buildG","ref":"buildG","sha":"6d95182af2690cfc657d7b326deedd8bdf3e179b","user":{"login":"nobrakal","id":6417395,"node_id":"MDQ6VXNlcjY0MTczOTU=","avatar_url":"https://avatars1.githubusercontent.com/u/6417395?v=4","gravatar_id":"","url":"https://api.github.com/users/nobrakal","html_url":"https://github.com/nobrakal","followers_url":"https://api.github.com/users/nobrakal/followers","following_url":"https://api.github.com/users/nobrakal/following{/other_user}","gists_url":"https://api.github.com/users/nobrakal/gists{/gist_id}","starred_url":"https://api.github.com/users/nobrakal/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nobrakal/subscriptions","organizations_url":"https://api.github.com/users/nobrakal/orgs","repos_url":"https://api.github.com/users/nobrakal/repos","events_url":"https://api.github.com/users/nobrakal/events{/privacy}","received_events_url":"https://api.github.com/users/nobrakal/received_events","type":"User","site_admin":false},"repo":{"id":132659096,"node_id":"MDEwOlJlcG9zaXRvcnkxMzI2NTkwOTY=","name":"alga","full_name":"nobrakal/alga","private":false,"owner":{"login":"nobrakal","id":6417395,"node_id":"MDQ6VXNlcjY0MTczOTU=","avatar_url":"https://avatars1.githubusercontent.com/u/6417395?v=4","gravatar_id":"","url":"https://api.github.com/users/nobrakal","html_url":"https://github.com/nobrakal","followers_url":"https://api.github.com/users/nobrakal/followers","following_url":"https://api.github.com/users/nobrakal/following{/other_user}","gists_url":"https://api.github.com/users/nobrakal/gists{/gist_id}","starred_url":"https://api.github.com/users/nobrakal/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nobrakal/subscriptions","organizations_url":"https://api.github.com/users/nobrakal/orgs","repos_url":"https://api.github.com/users/nobrakal/repos","events_url":"https://api.github.com/users/nobrakal/events{/privacy}","received_events_url":"https://api.github.com/users/nobrakal/received_events","type":"User","site_admin":false},"html_url":"https://github.com/nobrakal/alga","description":"Algebraic graphs","fork":true,"url":"https://api.github.com/repos/nobrakal/alga","forks_url":"https://api.github.com/repos/nobrakal/alga/forks","keys_url":"https://api.github.com/repos/nobrakal/alga/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nobrakal/alga/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nobrakal/alga/teams","hooks_url":"https://api.github.com/repos/nobrakal/alga/hooks","issue_events_url":"https://api.github.com/repos/nobrakal/alga/issues/events{/number}","events_url":"https://api.github.com/repos/nobrakal/alga/events","assignees_url":"https://api.github.com/repos/nobrakal/alga/assignees{/user}","branches_url":"https://api.github.com/repos/nobrakal/alga/branches{/branch}","tags_url":"https://api.github.com/repos/nobrakal/alga/tags","blobs_url":"https://api.github.com/repos/nobrakal/alga/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nobrakal/alga/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nobrakal/alga/git/refs{/sha}","trees_url":"https://api.github.com/repos/nobrakal/alga/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nobrakal/alga/statuses/{sha}","languages_url":"https://api.github.com/repos/nobrakal/alga/languages","stargazers_url":"https://api.github.com/repos/nobrakal/alga/stargazers","contributors_url":"https://api.github.com/repos/nobrakal/alga/contributors","subscribers_url":"https://api.github.com/repos/nobrakal/alga/subscribers","subscription_url":"https://api.github.com/repos/nobrakal/alga/subscription","commits_url":"https://api.github.com/repos/nobrakal/alga/commits{/sha}","git_commits_url":"https://api.github.com/repos/nobrakal/alga/git/commits{/sha}","comments_url":"https://api.github.com/repos/nobrakal/alga/comments{/number}","issue_comment_url":"https://api.github.com/repos/nobrakal/alga/issues/comments{/number}","contents_url":"https://api.github.com/repos/nobrakal/alga/contents/{+path}","compare_url":"https://api.github.com/repos/nobrakal/alga/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nobrakal/alga/merges","archive_url":"https://api.github.com/repos/nobrakal/alga/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nobrakal/alga/downloads","issues_url":"https://api.github.com/repos/nobrakal/alga/issues{/number}","pulls_url":"https://api.github.com/repos/nobrakal/alga/pulls{/number}","milestones_url":"https://api.github.com/repos/nobrakal/alga/milestones{/number}","notifications_url":"https://api.github.com/repos/nobrakal/alga/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nobrakal/alga/labels{/name}","releases_url":"https://api.github.com/repos/nobrakal/alga/releases{/id}","deployments_url":"https://api.github.com/repos/nobrakal/alga/deployments","created_at":"2018-05-08T20:06:59Z","updated_at":"2018-05-08T20:16:08Z","pushed_at":"2018-11-18T13:02:56Z","git_url":"git://github.com/nobrakal/alga.git","ssh_url":"git@github.com:nobrakal/alga.git","clone_url":"https://github.com/nobrakal/alga.git","svn_url":"https://github.com/nobrakal/alga","homepage":"","size":1187,"stargazers_count":0,"watchers_count":0,"language":"Haskell","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"snowleopard:master","ref":"master","sha":"4d8a403a6d0de083c3fb7a3dc8e2267f02cfde15","user":{"login":"snowleopard","id":675286,"node_id":"MDQ6VXNlcjY3NTI4Ng==","avatar_url":"https://avatars1.githubusercontent.com/u/675286?v=4","gravatar_id":"","url":"https://api.github.com/users/snowleopard","html_url":"https://github.com/snowleopard","followers_url":"https://api.github.com/users/snowleopard/followers","following_url":"https://api.github.com/users/snowleopard/following{/other_user}","gists_url":"https://api.github.com/users/snowleopard/gists{/gist_id}","starred_url":"https://api.github.com/users/snowleopard/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/snowleopard/subscriptions","organizations_url":"https://api.github.com/users/snowleopard/orgs","repos_url":"https://api.github.com/users/snowleopard/repos","events_url":"https://api.github.com/users/snowleopard/events{/privacy}","received_events_url":"https://api.github.com/users/snowleopard/received_events","type":"User","site_admin":false},"repo":{"id":75574031,"node_id":"MDEwOlJlcG9zaXRvcnk3NTU3NDAzMQ==","name":"alga","full_name":"snowleopard/alga","private":false,"owner":{"login":"snowleopard","id":675286,"node_id":"MDQ6VXNlcjY3NTI4Ng==","avatar_url":"https://avatars1.githubusercontent.com/u/675286?v=4","gravatar_id":"","url":"https://api.github.com/users/snowleopard","html_url":"https://github.com/snowleopard","followers_url":"https://api.github.com/users/snowleopard/followers","following_url":"https://api.github.com/users/snowleopard/following{/other_user}","gists_url":"https://api.github.com/users/snowleopard/gists{/gist_id}","starred_url":"https://api.github.com/users/snowleopard/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/snowleopard/subscriptions","organizations_url":"https://api.github.com/users/snowleopard/orgs","repos_url":"https://api.github.com/users/snowleopard/repos","events_url":"https://api.github.com/users/snowleopard/events{/privacy}","received_events_url":"https://api.github.com/users/snowleopard/received_events","type":"User","site_admin":false},"html_url":"https://github.com/snowleopard/alga","description":"Algebraic graphs","fork":false,"url":"https://api.github.com/repos/snowleopard/alga","forks_url":"https://api.github.com/repos/snowleopard/alga/forks","keys_url":"https://api.github.com/repos/snowleopard/alga/keys{/key_id}","collaborators_url":"https://api.github.com/repos/snowleopard/alga/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/snowleopard/alga/teams","hooks_url":"https://api.github.com/repos/snowleopard/alga/hooks","issue_events_url":"https://api.github.com/repos/snowleopard/alga/issues/events{/number}","events_url":"https://api.github.com/repos/snowleopard/alga/events","assignees_url":"https://api.github.com/repos/snowleopard/alga/assignees{/user}","branches_url":"https://api.github.com/repos/snowleopard/alga/branches{/branch}","tags_url":"https://api.github.com/repos/snowleopard/alga/tags","blobs_url":"https://api.github.com/repos/snowleopard/alga/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/snowleopard/alga/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/snowleopard/alga/git/refs{/sha}","trees_url":"https://api.github.com/repos/snowleopard/alga/git/trees{/sha}","statuses_url":"https://api.github.com/repos/snowleopard/alga/statuses/{sha}","languages_url":"https://api.github.com/repos/snowleopard/alga/languages","stargazers_url":"https://api.github.com/repos/snowleopard/alga/stargazers","contributors_url":"https://api.github.com/repos/snowleopard/alga/contributors","subscribers_url":"https://api.github.com/repos/snowleopard/alga/subscribers","subscription_url":"https://api.github.com/repos/snowleopard/alga/subscription","commits_url":"https://api.github.com/repos/snowleopard/alga/commits{/sha}","git_commits_url":"https://api.github.com/repos/snowleopard/alga/git/commits{/sha}","comments_url":"https://api.github.com/repos/snowleopard/alga/comments{/number}","issue_comment_url":"https://api.github.com/repos/snowleopard/alga/issues/comments{/number}","contents_url":"https://api.github.com/repos/snowleopard/alga/contents/{+path}","compare_url":"https://api.github.com/repos/snowleopard/alga/compare/{base}...{head}","merges_url":"https://api.github.com/repos/snowleopard/alga/merges","archive_url":"https://api.github.com/repos/snowleopard/alga/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/snowleopard/alga/downloads","issues_url":"https://api.github.com/repos/snowleopard/alga/issues{/number}","pulls_url":"https://api.github.com/repos/snowleopard/alga/pulls{/number}","milestones_url":"https://api.github.com/repos/snowleopard/alga/milestones{/number}","notifications_url":"https://api.github.com/repos/snowleopard/alga/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/snowleopard/alga/labels{/name}","releases_url":"https://api.github.com/repos/snowleopard/alga/releases{/id}","deployments_url":"https://api.github.com/repos/snowleopard/alga/deployments","created_at":"2016-12-05T00:30:03Z","updated_at":"2018-11-18T10:11:13Z","pushed_at":"2018-11-18T18:39:06Z","git_url":"git://github.com/snowleopard/alga.git","ssh_url":"git@github.com:snowleopard/alga.git","clone_url":"https://github.com/snowleopard/alga.git","svn_url":"https://github.com/snowleopard/alga","homepage":"","size":974,"stargazers_count":372,"watchers_count":372,"language":"Haskell","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":28,"mirror_url":null,"archived":false,"open_issues_count":29,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":28,"open_issues":29,"watchers":372,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/snowleopard/alga/pulls/123"},"html":{"href":"https://github.com/snowleopard/alga/pull/123"},"issue":{"href":"https://api.github.com/repos/snowleopard/alga/issues/123"},"comments":{"href":"https://api.github.com/repos/snowleopard/alga/issues/123/comments"},"review_comments":{"href":"https://api.github.com/repos/snowleopard/alga/pulls/123/comments"},"review_comment":{"href":"https://api.github.com/repos/snowleopard/alga/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/snowleopard/alga/pulls/123/commits"},"statuses":{"href":"https://api.github.com/repos/snowleopard/alga/statuses/6d95182af2690cfc657d7b326deedd8bdf3e179b"}},"author_association":"CONTRIBUTOR","merged":true,"mergeable":null,"rebaseable":null,"mergeable_state":"unknown","merged_by":{"login":"snowleopard","id":675286,"node_id":"MDQ6VXNlcjY3NTI4Ng==","avatar_url":"https://avatars1.githubusercontent.com/u/675286?v=4","gravatar_id":"","url":"https://api.github.com/users/snowleopard","html_url":"https://github.com/snowleopard","followers_url":"https://api.github.com/users/snowleopard/followers","following_url":"https://api.github.com/users/snowleopard/following{/other_user}","gists_url":"https://api.github.com/users/snowleopard/gists{/gist_id}","starred_url":"https://api.github.com/users/snowleopard/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/snowleopard/subscriptions","organizations_url":"https://api.github.com/users/snowleopard/orgs","repos_url":"https://api.github.com/users/snowleopard/repos","events_url":"https://api.github.com/users/snowleopard/events{/privacy}","received_events_url":"https://api.github.com/users/snowleopard/received_events","type":"User","site_admin":false},"comments":32,"review_comments":51,"maintainer_can_modify":false,"commits":68,"additions":195,"deletions":75,"changed_files":5}}
{"actor":{"display_login":"snowleopard"}}