[Haskell-cafe] advantages of using fix to define rcursive
dan.doel at gmail.com
Thu Jul 26 11:22:10 EDT 2007
On Thursday 26 July 2007, Harald ROTTER wrote:
> 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!)
> 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.
More information about the Haskell-Cafe