hello listers, a few days ago A fellow lister sent me the following link: http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion The 'fix' function is interesting to say the least. There is one example that I've had difficulty expanding: fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 120 My interpretation: fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 ((\rec n -> if n == 0 then 1 else n * rec (n-1)) (fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) )) 5 . . . Yet, it does not quite explain how 'fix' does not result in infinite recursion. Sincerely Matthew J. Williams
n decreases on each step of the recursion, which will allow it to terminate. You need to expand AND substitute arguments: fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5
fix (\rec 5 -> if 5 == 0 then 1 else n * rec (5 -1)) fix (\rec 5 -> if 5 == 0 then 1 else n * (fix (\rec 4 -> if 4 == 0 then 1 else 4 * rec (3-1))))
And so on.
On Wed, Oct 15, 2008 at 3:51 PM, Matthew J. Williams
hello listers, a few days ago A fellow lister sent me the following link:
http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion
The 'fix' function is interesting to say the least. There is one example that I've had difficulty expanding:
fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 120
My interpretation: fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 ((\rec n -> if n == 0 then 1 else n * rec (n-1)) (fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) )) 5 . . .
Yet, it does not quite explain how 'fix' does not result in infinite recursion.
Sincerely Matthew J. Williams
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
On 2008 Oct 15, at 18:51, Matthew J. Williams wrote:
fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 120
My interpretation: fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 ((\rec n -> if n == 0 then 1 else n * rec (n-1)) (fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) )) 5 . . .
Yet, it does not quite explain how 'fix' does not result in infinite recursion.
Remember, Haskell is non-strict. When the computation reaches 0, the "then" branch of the conditional is evaluated and the "else" is unneeded and therefore ignored, so its re-invocation isn't seen. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
On 2008 Oct 15, at 19:04, Brandon S. Allbery KF8NH wrote:
On 2008 Oct 15, at 18:51, Matthew J. Williams wrote:
Yet, it does not quite explain how 'fix' does not result in infinite recursion.
Remember, Haskell is non-strict. When the computation reaches 0, the "then" branch of the conditional is evaluated and the "else" is unneeded and therefore ignored, so its re-invocation isn't seen.
Think about this, btw: you can create new control operations as ordinary functions In strict languages you need to rely on special syntax (such as Perl's IO syntax + \& prototype, or Ruby's special block/proc syntax; in LISP/Scheme, you have to use a macro and/or quoting); non-strict evaluation gives it to you for free. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
participants (3)
-
Brandon S. Allbery KF8NH -
Justin Bailey -
Matthew J. Williams