lecture notes for Finally Tagless - benefit of explicit fix combinator
Hi all, I'm working my way through the lecture notes to the "Finally Tagless" course, available from: http://okmij.org/ftp/tagless-final/course/index.html As usual at every round of doing so, I think it's my 4th, I discover something new, something that hadn't occurred to me previously. This time it's a comment in the code of SerializeExt.hs -- * Tie up the knot fromTree = S.fix fromTreeExt -- One does use fix in real programs -- Now we can see the real benefit of using fix in real programs. -- The fixpoint combinator is NOT a mere curiosity about the fix-point combinator. I don't think I can deduce what he meant by that from the context alone, could somebody please enlighten me? I'm refering to the benefit of using the fix-point combinator in this particular scenario. Günther
Hi Günther The code in the two serialize modules looks very close to Konstantin Laufer's functional variation of the visitor pattern: http://webpages.math.luc.edu/~laufer/papers/mixins03.pdf This open recursion style - is used to get "inheritance" / extensibility - there is a more recent paper by Bruno Oliveira, Tom Schrijvers and William Cook here: http://tomschrijvers.blogspot.com/2009/09/effectiveadvice-aop-mixin-inherita... Best wishes Stephen
Hi Stephen, I'm glad I asked. This sure sounds more interesting than I had anticipated. Is this an old hat for your off-the-shelf haskeller or something only found in the more seasoned haskellers tool box? I think it's pretty much the first time I encounter it. Günther Am 19.06.10 17:01, schrieb Stephen Tetley:
Hi Günther
The code in the two serialize modules looks very close to Konstantin Laufer's functional variation of the visitor pattern:
http://webpages.math.luc.edu/~laufer/papers/mixins03.pdf
This open recursion style - is used to get "inheritance" / extensibility - there is a more recent paper by Bruno Oliveira, Tom Schrijvers and William Cook here:
http://tomschrijvers.blogspot.com/2009/09/effectiveadvice-aop-mixin-inherita...
Best wishes
Stephen
Hi Günther I haven't seen open recursion used in any libraries I'm familiar with, though as its not a technique I've used myself I'm not really "trained" to spot it. There's another paper by William Cook (and Daniel Brown) were the use is explicit (at least initially - Sections 2.2 & 2.3): http://userweb.cs.utexas.edu/users/wcook/Drafts/2009/sblp09-memo-mixins.pdf There are probably some other instances where it takes more expertise to spot - certainly Oleg Kiselyov and Ralf Lammel's OO-Haskell paper uses open recursion, but in a slightly different way. Best wishes Stephen
Günther Schmidt wrote:
Hi Stephen,
I'm glad I asked. This sure sounds more interesting than I had anticipated. Is this an old hat for your off-the-shelf haskeller or something only found in the more seasoned haskellers tool box?
I think it's pretty much the first time I encounter it.
It depends on what kind of seasoning you take :) Another use case which is really common is to use open recursion for things like memoization. That is, if we write an open-recursive function, using `fix` turns it into a normal recursive function but we can use a different fixed-point combinator in order to memoize the results. Luke Palmer has packaged up a version of this on Hackage[1]. You can perform similar tricks on the type level. Wouter Swierstra combats the expression problem by using open recursion to build ad-hoc union types[2]. Whereas Tim Sheard uses a somewhat different version of open recursion to create parameterized modules[3], with a specific use case being to separate variables from structure in unification algorithms[4]. [1] http://hackage.haskell.org/package/data-memocombinators [2] http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf [3] http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps [4] http://web.cecs.pdx.edu/~sheard/papers/generic.ps -- Live well, ~wren
participants (3)
-
Günther Schmidt -
Stephen Tetley -
wren ng thornton