{"id":40,"date":"2015-02-26T17:55:30","date_gmt":"2015-02-26T22:55:30","guid":{"rendered":"http:\/\/www.msully.net\/blog\/?p=40"},"modified":"2016-03-08T19:10:45","modified_gmt":"2016-03-09T00:10:45","slug":"microkanren-%ce%bckanren-in-haskell","status":"publish","type":"post","link":"https:\/\/www.msully.net\/blog\/2015\/02\/26\/microkanren-%ce%bckanren-in-haskell\/","title":{"rendered":"MicroKanren (\u03bcKanren) in Haskell"},"content":{"rendered":"<p>Our PL reading group read the paper &#8220;<a href=\"http:\/\/webyrd.net\/scheme-2013\/papers\/HemannMuKanren2013.pdf\">\u03bcKanren: A Minimal Functional Core for Relational Programming<\/a>&#8221; this week. It presents a minimalist logic programming language in Scheme in 39 lines of code. Since none of us are really Schemers, a bunch of us quickly set about porting the code to our personal pet languages. Chris Martens produced  <a href=\"https:\/\/github.com\/chrisamaphone\/ml-mukanren\/blob\/master\/mukanren.sml\">this SML version<\/a>. I hacked up a version in Haskell.<\/p>\n<p>The most interesting part about this was the mistake I made in the initial version. To deal with recursion and potentially infinite search trees, the Scheme version allows some laziness; streams of results can be functions that delay search until forced; when a Scheme \u03bcKanren program wants to create a recursive relation it needs wrap the recursive call in a dummy function (and plumb through the input state); the Scheme version wraps this in a macro called <code>Zzz<\/code> to make doing it more palatable. I originally thought that all of this could be dispensed with in Haskell; since Haskell is lazy, no special work needs to be done to prevent self reference from causing an infinite loop. It served an important secondary purpose, though: providing a way to detect recursion so that we can switch which branch of the tree we are exploring. Without this, although the <codes>fives<\/codes> test below works, the <codes>fivesRev<\/codes> test infinite loops without producing anything.<\/p>\n<p>The initial version was also more generalized. The type signatures allowed for operating over any <code>MonadPlus<\/code>, thus allowing pluggable search strategies. <code>KList<\/code> was just a newtype wrapper around lists. When I had to add <code>delay<\/code> I could have defined a new <code>MonadPlusDelay<\/code> typeclass and parametrized over that, but it didn\u2019t&#8217; seem worthwhile.<\/p>\n<p>A mildly golfed version that drops blank lines, type annotations, comments, aliases, and test code clocks in at 33 lines.<\/p>\n<div class=\"oembed-gist\"><script src=\"https:\/\/gist.github.com\/msullivan\/4223fd47991acbe045ec.js\"><\/script><noscript>View the code on <a href=\"https:\/\/gist.github.com\/msullivan\/4223fd47991acbe045ec\">Gist<\/a>.<\/noscript><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Our PL reading group read the paper &#8220;\u03bcKanren: A Minimal Functional Core for Relational Programming&#8221; this week. It presents a minimalist logic programming language in Scheme in 39 lines of code. Since none of us are really Schemers, a bunch of us quickly set about porting the code to our personal pet languages. Chris Martens [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,7],"tags":[],"class_list":["post-40","post","type-post","status-publish","format-standard","hentry","category-hacks","category-pl"],"_links":{"self":[{"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/posts\/40","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/comments?post=40"}],"version-history":[{"count":3,"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/posts\/40\/revisions"}],"predecessor-version":[{"id":43,"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/posts\/40\/revisions\/43"}],"wp:attachment":[{"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/media?parent=40"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/categories?post=40"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.msully.net\/blog\/wp-json\/wp\/v2\/tags?post=40"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}