{"id":159004,"name":"LogicGrowsOnTrees","ecosystem":"hackage","description":"NOTE:  In addition to the following package description, see\n\nTUTORIAL.md\nfor a tutorial,\n\nUSERS_GUIDE.md\nfor a user's guide that provides more information about\nhow to use this package, and\n\nREADME.md\nfor an FAQ.\n\nYou can think of this package in two equivalent ways. First, you can think\nof it as an implementation of logic programming that is designed to be\nparellelized using workers that have no memory shared between them (hence,\n\"distributed\"). Second, you can think of this package as providing\ninfrastructure for exploring a tree in parallel. The connection between\nthese two perspectives is that logic programming involves making\nnondeterministic choices, and each such choice is equivalent to a branch\npoint in a tree representing the search space of the logic program. In the\nrest of the reference documentation we will focus on the tree perspective\nsimply because a lot of the functionality makes the most sense from the\nperspective of working with trees, but one is always free to ignore this and\nsimply write a logic program using the standard approach of using\nMonadPlus to indicate choice and failure, and the Tree implementation of\nthis typeclass will take care of the details of turning your logic program\ninto tree. (If you are not familiar with this approach, then see\n\u003chttp://github.com/gcross/LogicGrowsOnTrees/blob/master/TUTORIAL.md\nTUTORIAL.md\u003e.)\n\nTo use this package, you first write a function that builds a tree (say, by\nusing logic programming); the LogicGrowsOnTrees module provides\nfunctionality to assist in this. You may have your function either return a\ngeneric MonadPlus or MonadExplorable (where the latter lets you cache\nexpensive intermediate calculations so that they do not have to be performed\nagain if this path is re-explored later), or you may have it return a Tree\n(or one of its impure friends) directly. You can then test your tree using\nthe visting functions in the LogicGrowsOnTrees module.\n\nWARNING: If you need something like state in your tree, then you should\nstack the state monad (or whatever else you want) on top of Tree rather\nthan below it. The reason for this is that if you stack the monad below\nTreeT, then your monad will be affected by the order in which the tree is\nexplored, which is almost never what you want, in part because if you are\nnot careful then you will break the assumption made by the checkpointing and\nparallelization infrastructure that it does not matter in what order the\ntree is explored or even whether some parts are explored twice or not at all\nin a given run. If side-effects that are not undone by backtracking is\nindeed what you want, then you need to make sure that your side-effects do\nnot break this assumption; for example, a monad which memoizes a pure\nfunction is perfectly fine. By contrast if you are working within the IO\nmonad and writing results to a database rather than returning them (and\nassuming that duplicate results would cause problems) then you need to check\nto make sure you aren't writing the same result twice, such as by using the\nLogicGrowsOnTrees.Location functionality to identify where you are in the\ntree so you can query to see if your current location is already listed in\nthe database.\n\nIf you want to see examples of generating a tree to solve a problem, then\nsee LogicGrowsOnTrees.Examples.MapColoring or\nLogicGrowsOnTrees.Examples.Queens modules, which have some basic examples\nof using logic programming to find and/or count the number of solutions to a\ngiven map coloring problem and a given n-queens problem. The\nLogicGrowsOnTrees.Examples.Queens.Advanced module has my own solution to\nthe n-queens problem where I use symmetry breaking to prune the search tree,\ncutting the runtime by about a factor of three.\n\nOnce your tree has been debugged, you can start taking advantage of the\nmajor features of this package. If you are interested in checkpointing, but\nnot parallelization, then you can use the step functions in the\nLogicGrowsOnTrees.Checkpoint module to sequentially explore a tree one\nnode at a time, saving the current checkpoint as often as you desire; at any\ntime the exploration can be aborted and resumed later. Most likely, though,\nyou will be interested in using the parallelization infrastructure rather\nthan just the checkpointing infrastructure. The parallelization\ninfrastructure uses a supervisor/worker model, and is designed such that the\nlogic used to keep track of the workers and the current progress is\nabstracted away into the LogicGrowsOnTrees.Parallel.Common.Supervisor\nmodule; one then uses one of the provided adapters (or possibly your own) to\nconnect the abstract model to a particular means of running multiple\ncomputations in parallel, such as multiple threads, multiple processes on\nthe same machine, multiple processes on a network, and MPI; the first option\nis included in this package and the others are provided in separate\npackages. Parallelization is obtained by stealing workloads from workers;\nspecifically, a selected worker will look back at the (non-frozen) choices\nit has made so far, pick the first one, freeze it (so that it won't\nbacktrack and try the other branch), and then hand the other branch to the\nsupervisor which will then give it to a waiting worker.\n\nTo use the parallelization infrastructure, you have two choices. First, you\ncan opt to use the adapter directly; the exploration functions provided by\nthe adapter are relatively simple (compared to the alternative to be\ndiscussed in a moment) and furthermore, they give you maximum control over\nthe adapter, but the downside is that you will have to re-implement features\nsuch as regular checkpointing and forwarding information from the command\nline to the workers yourself. Second, you can use the infrastructure in\nLogicGrowsOnTrees.Parallel.Main, which automates most of the process for\nyou, including parsing the command lines, sending information to the\nworkers, determining how many workers (if applicable) to start up, offering\nthe user a command line option to specify whether, where, and how often to\ncheckpoint, etc.; this infrastructure is also completely adapter\nindependent, which means that when switching from one adapter to another all\nyou have to do is change one of the arguments in your call to the main\nfunction you are using in LogicGrowsOnTrees.Parallel.Main. The downside is\nthat the call to use this functionality is a bit more complex than the call\nto use a particular adapter precisely because of its generality.\n\nIf you want to see examples of using the LogicGrowsOnTrees.Parallel.Main\nmodule, check out the example executables in the examples/ subdirectory of\nthe source distribution.\n\nIf you are interested in writing a new adapter, then you have couple of\noptions. First, if your adapter can spawn and destroy workers on demand,\nthen you should look at the LogicGrowsOnTrees.Parallel.Common.Workgroup\nmodule, as it has infrastructure designed for this case; look at\nLogicGrowsOnTrees.Parallel.Adapter.Threads for an example of using it.\nSecond, if your adapter does not meet this criterion, then you should look\nat the LogicGrowsOnTrees.Parallel.Common.Supervisor module; your adapter\nwill need to run within the SupervisorMonad, with its own state contained\nin its own monad below the SupervisorMonad monad in the stack; for an\nexample, look at the LogicGrowsOnTrees-network module.\n\nNOTE: This package uses the hslogger package for logging; if you set the\nlog level to INFO or DEBUG (either by calling the functions in hslogger\nyourself or by using the -l command line option if you are using Main)\nthen many status messages will be printed to the screen (or wherever else\nthe log has been configured to be written).\n\nThe modules are organized as follows:\n\nOf the above modules, the ones you will be using most often\nare LogicGrowsOnTrees (for building trees), one of the\nadapter modules (such as\nLogicGrowsOnTrees.Parallel.Adapter.Threads), and possibly\nLogicGrowsOnTrees.Parallel.Main. If you are counting the\nnumber of solutions, then you will also want to look at\nLogicGrowsOnTrees.Utils.WordSum. Finally, if your program\ntakes a Word as a command line argument or option then\nyou might find the LogicGrowsOnTrees.Utils.Word_ module\nto be useful. The other modules provide lower-level\nfunctionality; in particular the\nLogicGrowsOnTrees.Parallel.Common.* modules are primarily\ngeared towards people writing their own adapter.","homepage":null,"licenses":"BSD-3-Clause","normalized_licenses":["BSD-3-Clause"],"repository_url":"https://github.com/gcross/LogicGrowsOnTrees","keywords_array":["bsd3","control","distributed-computing","library","logic","parallelism","Propose Tags"],"namespace":null,"versions_count":5,"first_release_published_at":"2013-09-14T09:35:35.000Z","latest_release_published_at":"2013-09-14T09:35:35.000Z","latest_release_number":"1.0.0","last_synced_at":"2026-09-25T07:52:09.922Z","created_at":"2022-04-05T17:27:42.973Z","updated_at":"2026-09-25T12:29:36.089Z","registry_url":"https://hackage.haskell.org/package/LogicGrowsOnTrees","install_command":"cabal install LogicGrowsOnTrees","documentation_url":null,"metadata":{},"repo_metadata":{"id":66845563,"uuid":"2081809","full_name":"gcross/LogicGrowsOnTrees","owner":"gcross","description":"A library and framework for massively parallelizing backtracking searches in Haskell with a strong emphasis on ease of use.","archived":false,"fork":false,"pushed_at":"2019-07-30T12:22:43.000Z","size":1460,"stargazers_count":31,"open_issues_count":0,"forks_count":2,"subscribers_count":3,"default_branch":"master","last_synced_at":"2025-07-23T14:43:35.709Z","etag":null,"topics":[],"latest_commit_sha":null,"homepage":"","language":"Haskell","has_issues":true,"has_wiki":null,"has_pages":null,"mirror_url":null,"source_name":null,"license":"bsd-2-clause","status":null,"scm":"git","pull_requests_enabled":true,"icon_url":"https://github.com/gcross.png","metadata":{"files":{"readme":null,"changelog":null,"contributing":null,"funding":null,"license":"LICENSE","code_of_conduct":null,"threat_model":null,"audit":null,"citation":null,"codeowners":null,"security":null,"support":null,"governance":null}},"created_at":"2011-07-21T04:41:55.000Z","updated_at":"2023-08-02T15:44:48.000Z","dependencies_parsed_at":null,"dependency_job_id":"c36e9d05-4f6c-4386-b393-ecbff8b0c96b","html_url":"https://github.com/gcross/LogicGrowsOnTrees","commit_stats":null,"previous_names":[],"tags_count":5,"template":false,"template_full_name":null,"purl":"pkg:github/gcross/LogicGrowsOnTrees","repository_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees","tags_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags","releases_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/releases","manifests_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/manifests","owner_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/owners/gcross","download_url":"https://codeload.github.com/gcross/LogicGrowsOnTrees/tar.gz/refs/heads/master","sbom_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/sbom","scorecard":null,"host":{"name":"GitHub","url":"https://github.com","kind":"github","repositories_count":341189360,"owners_count":37669346,"icon_url":"https://github.com/github.png","version":null,"created_at":"2022-05-30T11:31:42.601Z","updated_at":"2026-08-22T15:14:58.755Z","status":"online","status_checked_at":"2026-09-25T02:00:20.896Z","response_time":55,"last_error":null,"robots_txt_status":"success","robots_txt_updated_at":"2025-07-24T06:49:26.215Z","robots_txt_url":"https://github.com/robots.txt","online":true,"can_crawl_api":true,"host_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub","repositories_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories","repository_names_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repository_names","owners_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/owners"},"owner_record":{"login":"gcross","name":"Gregory Crosswhite","uuid":"87325","kind":"user","description":null,"email":"","website":null,"location":null,"twitter":null,"company":null,"icon_url":"https://avatars.githubusercontent.com/u/87325?v=4","repositories_count":103,"last_synced_at":"2023-04-17T16:16:12.367Z","metadata":{"has_sponsors_listing":false},"html_url":"https://github.com/gcross","funding_links":[],"total_stars":null,"followers":null,"following":null,"created_at":"2022-11-02T18:27:33.750Z","updated_at":"2023-04-17T16:16:12.864Z","owner_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/owners/gcross","repositories_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/owners/gcross/repositories"},"tags":[{"name":"1.1.0.2","sha":"b63d7be8a0b1e62c5c7e03325115de2b05f58e14","kind":"commit","published_at":"2014-03-07T19:41:03.000Z","download_url":"https://codeload.github.com/gcross/LogicGrowsOnTrees/tar.gz/1.1.0.2","html_url":"https://github.com/gcross/LogicGrowsOnTrees/releases/tag/1.1.0.2","dependencies_parsed_at":null,"dependency_job_id":null,"purl":"pkg:github/gcross/LogicGrowsOnTrees@1.1.0.2","tag_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.1.0.2","manifests_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.1.0.2/manifests"},{"name":"1.1.0.1","sha":"5c180baec3f4d7cb9039c8b966f016a7ef6f5e97","kind":"commit","published_at":"2014-03-04T03:09:26.000Z","download_url":"https://codeload.github.com/gcross/LogicGrowsOnTrees/tar.gz/1.1.0.1","html_url":"https://github.com/gcross/LogicGrowsOnTrees/releases/tag/1.1.0.1","dependencies_parsed_at":null,"dependency_job_id":null,"purl":"pkg:github/gcross/LogicGrowsOnTrees@1.1.0.1","tag_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.1.0.1","manifests_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.1.0.1/manifests"},{"name":"1.1","sha":"6151044f18f95771ecf9863389837334e7974deb","kind":"commit","published_at":"2014-03-03T19:31:06.000Z","download_url":"https://codeload.github.com/gcross/LogicGrowsOnTrees/tar.gz/1.1","html_url":"https://github.com/gcross/LogicGrowsOnTrees/releases/tag/1.1","dependencies_parsed_at":null,"dependency_job_id":null,"purl":"pkg:github/gcross/LogicGrowsOnTrees@1.1","tag_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.1","manifests_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.1/manifests"},{"name":"1.0.0.0.1","sha":"154795fb847caaf11319e13362b74ea9645a3324","kind":"commit","published_at":"2013-09-14T10:27:32.000Z","download_url":"https://codeload.github.com/gcross/LogicGrowsOnTrees/tar.gz/1.0.0.0.1","html_url":"https://github.com/gcross/LogicGrowsOnTrees/releases/tag/1.0.0.0.1","dependencies_parsed_at":null,"dependency_job_id":null,"purl":"pkg:github/gcross/LogicGrowsOnTrees@1.0.0.0.1","tag_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.0.0.0.1","manifests_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.0.0.0.1/manifests"},{"name":"1.0.0","sha":"6e1b4823062472ad55e93018c7f9e40080277c44","kind":"commit","published_at":"2013-09-14T05:30:34.000Z","download_url":"https://codeload.github.com/gcross/LogicGrowsOnTrees/tar.gz/1.0.0","html_url":"https://github.com/gcross/LogicGrowsOnTrees/releases/tag/1.0.0","dependencies_parsed_at":null,"dependency_job_id":null,"purl":"pkg:github/gcross/LogicGrowsOnTrees@1.0.0","tag_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.0.0","manifests_url":"https://repos.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2FLogicGrowsOnTrees/tags/1.0.0/manifests"}]},"repo_metadata_updated_at":"2026-09-25T12:29:36.088Z","dependent_packages_count":0,"downloads":5419,"downloads_period":"total","dependent_repos_count":1,"rankings":{"downloads":26.816056562892005,"dependent_repos_count":36.76227404915322,"dependent_packages_count":19.056851228830475,"stargazers_count":null,"forks_count":null,"docker_downloads_count":null,"average":27.545060613625235},"purl":"pkg:hackage/LogicGrowsOnTrees","advisories":[],"docker_usage_url":"https://docker.ecosyste.ms/usage/hackage/LogicGrowsOnTrees","docker_dependents_count":null,"docker_downloads_count":null,"usage_url":"https://repos.ecosyste.ms/usage/hackage/LogicGrowsOnTrees","dependent_repositories_url":"https://repos.ecosyste.ms/api/v1/usage/hackage/LogicGrowsOnTrees/dependencies","status":null,"funding_links":[],"critical":null,"issue_metadata":{"last_synced_at":"2026-09-25T07:52:10.749Z","issues_count":0,"pull_requests_count":0,"avg_time_to_close_issue":null,"avg_time_to_close_pull_request":null,"issues_closed_count":0,"pull_requests_closed_count":0,"pull_request_authors_count":0,"issue_authors_count":0,"avg_comments_per_issue":null,"avg_comments_per_pull_request":null,"merged_pull_requests_count":0,"bot_issues_count":0,"bot_pull_requests_count":0,"past_year_issues_count":0,"past_year_pull_requests_count":0,"past_year_avg_time_to_close_issue":null,"past_year_avg_time_to_close_pull_request":null,"past_year_issues_closed_count":0,"past_year_pull_requests_closed_count":0,"past_year_pull_request_authors_count":0,"past_year_issue_authors_count":0,"past_year_avg_comments_per_issue":null,"past_year_avg_comments_per_pull_request":null,"past_year_bot_issues_count":0,"past_year_bot_pull_requests_count":0,"past_year_merged_pull_requests_count":0,"issues_url":"https://issues.ecosyste.ms/api/v1/hosts/GitHub/repositories/gcross%2Flogicgrowsontrees/issues","maintainers":[],"active_maintainers":[]},"versions_url":"https://packages.ecosyste.ms/api/v1/registries/hackage.haskell.org/packages/LogicGrowsOnTrees/versions","version_numbers_url":"https://packages.ecosyste.ms/api/v1/registries/hackage.haskell.org/packages/LogicGrowsOnTrees/version_numbers","latest_version_url":"https://packages.ecosyste.ms/api/v1/registries/hackage.haskell.org/packages/LogicGrowsOnTrees/latest_version","dependent_packages_url":"https://packages.ecosyste.ms/api/v1/registries/hackage.haskell.org/packages/LogicGrowsOnTrees/dependent_packages","related_packages_url":"https://packages.ecosyste.ms/api/v1/registries/hackage.haskell.org/packages/LogicGrowsOnTrees/related_packages","codemeta_url":"https://packages.ecosyste.ms/api/v1/registries/hackage.haskell.org/packages/LogicGrowsOnTrees/codemeta","maintainers":[{"uuid":"GregoryCrosswhite","login":"GregoryCrosswhite","name":null,"email":null,"url":null,"packages_count":21,"html_url":"https://hackage.haskell.org/user/GregoryCrosswhite","role":null,"created_at":"2022-11-14T16:34:26.480Z","updated_at":"2022-11-14T16:34:26.480Z","packages_url":"https://packages.ecosyste.ms/api/v1/registries/hackage.haskell.org/maintainers/GregoryCrosswhite/packages"}]}