tag:blogger.com,1999:blog-1777990983847811806.post8137932186432001110..comments2021-01-21T06:41:40.209-08:00Comments on Haskell for all: The visitor pattern is essentially the same thing as Church encodingGabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-1777990983847811806.post-11611833944135420062021-01-08T08:57:28.647-08:002021-01-08T08:57:28.647-08:00I had exactly the same feeling, but I might be bia...I had exactly the same feeling, but I might be biased because I just spent a week studying recursion-schemes and I know see them everywhere.<br /><br />To add to this: Gabriel noted that the preorder function never recursively calls itself. If I understand correctly, that's because the construction of trees actually bakes in that its constituent parts are provided with the same 'handlers' for each constructor, much like an F-algebra would do for the Base functor?<br /><br />I'm wondering what implications this would have when we want to write minmax evaluation over these same trees, so without introducing a tag/constructor in the datatype signaling whether a node is a max or a min node.<br /><br />With a traditional (tagged initial?) datatype encoding, we could write 'minmax' by pattern matching on up to two levels of nesting at once, and then recursively call 'minmax' again.<br />I'm not so sure how this would translate for the Böhm-Berarducci approach, whether it is possible and how.. I'm might need to do some experimenting this evening!mvanderhallenhttps://www.blogger.com/profile/17078182565592575952noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-83822157203387396292021-01-07T08:32:13.054-08:002021-01-07T08:32:13.054-08:00As well as the Church/Böhm-Berarducci encoding, th...As well as the Church/Böhm-Berarducci encoding, there's a Parigot encoding. For the former, binary trees are expressed by<br /><br /> type Tree = forall t . (Int -> t -> t -> t) -> t -> t<br /><br />so the type is not recursive, but the constructors have to be recursive; this corresponds to what GOF call "internal visitors", where it is the visitor that controls the order of traversal. Whereas for the latter the type is<br /><br /> type Tree = forall t . (Int -> Tree -> Tree -> t) -> t -> t<br /><br />which is recursive, but now the constructors need not be; this corresponds to GOF's "external visitors", where it is the client that controls the order of traversal. <br /><br />For more detail, see this paper from OOPSLA 2008, mostly by my former student Bruno Oliveira:<br /><br /> http://www.cs.ox.ac.uk/publications/publication1398-abstract.html<br />Jeremy Gibbonshttps://www.blogger.com/profile/04633943586802588755noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-77532843154203159452021-01-04T16:52:28.949-08:002021-01-04T16:52:28.949-08:00Great post!
Minor typo:
-- Evaluate the anonymous...Great post!<br /><br />Minor typo:<br />-- Evaluate the anonymous function<br />= pi * 4.6 ^ 2<br /><br /><br />-= pi * 4.6 ^ 2<br />Markhttps://www.blogger.com/profile/09877119195514564181noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-60796570234453879192021-01-04T14:34:59.068-08:002021-01-04T14:34:59.068-08:00Thanks for this insightful write up. I'm sensi...Thanks for this insightful write up. I'm sensing a strong relation of the Böhm-Berarducci encoding of Trees to F-Algebras and catamorphisms: <br /><br />preorder :: Tree -> [Int]<br /><br />pretty much looks like the F-Algebra of the Tree functor to me. I can't pinpoint this more precisely though for now. <br />Unknownhttps://www.blogger.com/profile/13587552231095691885noreply@blogger.com