Haskell's Fixed Point Combinator

http://playingwithpointers.com/archives/590

36 8 15 years ago

mccutchen• 15 years ago

Most of this went right over my head, but I enjoyed it nonetheless. I'm endlessly fascinated by Haskell.

FalconNL2• 15 years ago

As an alternative to the zipWith method of calculating the Fibonacci series, you can use scanl, resulting in (in my opinion) an even more elegant version:

    fibs = fix $ (1 :) . scanl (+) 1

darklajid• 15 years ago

Joining the other commenter, only 70% of the article reached this recipient's brain.

I would appreciate if you could help me fry it completely by offering a little more than an even shorter one-liner using a function I just read about the first time. Please?

FalconNL2• 15 years ago

I don't know if this will add much to the article, but let's go over things step by step.

scanl is the same as foldl, save for the fact that it outputs a list of all intermediate values. So where

    foldl (+) 0 [1..10]

would output 55,

    scanl (+) 0 [1..10]

would output [0,1,3,6,10,15,21,28,36,45,55].

(1 :) means prepend a 1 to the list it is given. The function that is passed as an argument to fix therefore returns a 1 followed by the successive summation values of its argument.

fix just infinitely applies its argument to itself, i.e.

    fix f = f (fix f)

In any strict language this would ofcourse just result in an infinite loop, but fortunately Haskell has lazy evaluation. So if we evaluate the list, for example with

    take 5 fibs

the following happens:

Haskell wants the first list element. The first element of (1 :) . scanl (+) 1 is 1, so there's no need to evaluate the scanl part yet. Now we need the second element. scanl first returns its accumulator, so that's another 1. For the third list element scanl needs the first element of its argument for the addition, so now we get to the recursive application. As before, the first element of (1 :) . scanl (+) 1 is 1, so the next element is 1 + 1 = 2. This 2 is then added to the next element, which is another 1, resulting in 3. Finally, we add 3 to the third element, giving 5. We now have five elements, which is what we requested, so the result will be [1,1,2,3,5].

I hope this helped a little. If you have any other questions, just let me know.

qntm• 15 years ago

I would be very interested to see a single real-world use for a fixed-point combinator. I have a reasonable understanding of what one does, but I still haven't got the faintest idea why you would ever need one, nor have I seen a single situation in which applying one doesn't make the situation unimaginably more complicated to understand.

thedigitalengel• 15 years ago

Neither have I. I just find it very beautiful.

stefano• 15 years ago

Fixed point operators are heavily used in abstract interpretation (https://secure.wikimedia.org/wikipedia/en/wiki/Abstract_inte...), which in turn is used in static analysis of programs for automatic bug detection or compiler optimizations. In certain situations it can also be used to formally prove the correctness of a program. Just to give a concrete example, this is a static analyzer based on abstract interpretation: http://www.astree.ens.fr/ . Polyspace (https://secure.wikimedia.org/wikipedia/en/wiki/Polyspace) is another static analysis tool that uses abstract interpretation.

rsaarelm• 15 years ago

I think Haskell uses a fixpoint combinator built into the core language under some syntactic sugar to enable any sort of recursion, so the real-world use would be pretty much making every Haskell program ever work.

Haskell's Fixed Point Combinator

Related Stories