[Haskell-cafe] advantages of using fix to define rcursive functions

[Dan Doel]

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