On Thursday 26 July 2007, Harald ROTTER wrote:
Hi,
I read about the usage of "fix" to define recursive functions. Although I think that I understood how to use "fix", I still wonder what the advantages of "fix" are (as compared to the "conventional" approach to define recursive functions).
Any hints are appreciated.
It may not be using fix per-se, but one interesting thing you can do with a fixed-point combinator is write one that memoizes the produced function:
table bounds f = array bounds [(i, f i) | i <- range bounds]
dp bounds f = (memo!) where memo = table bounds (f (memo!))
Then you can write something like:
fib' _ 1 = 1 fib' _ 2 = 1 fib' me n = me (n - 1) + me (n - 2) fib = dp (1, 30) fib'
And fib will only ever compute the nth fibonacci number once, saving it thereafter. Of course, with arrays, this only works over a fixed range, but you can write structures that will allow you to memoize over arbitrary domains this way (either lazy lists of exponentially sized arrays, or infinite, lazy tries will get you O(lg n) lookup on integers, for example; and the latter should be able to memoize over strings, among other things). The advantage being, you can write a library that will automatically do dynamic programming for you, instead of having to write the same knot-tying array/map code every time. So, that's not an example of why fix is directly useful, but it's certainly useful to understand how to use it for this reason. -- Dan