[Haskell-cafe] lecture notes for Finally Tagless - benefit of explicit fix combinator

[wren ng thornton]

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