Re: [Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)
On 20/03/07, Bryan Burgers [EMAIL PROTECTED] wrote: On the topic of 'fix', is there any good tutorial for fix? I quite liked this one: http://dreamsongs.org/Files/WhyOfY.pdf Alistair ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)
Pete Kazmier: I understand the intent of this code, but I am having a hard time understanding the implementation, specifically the combination of 'fix', 'flip', and 'interate'. I looked up 'fix' and I'm unsure how one can call 'flip' on a function that takes one argument. I threw that in there because I figured you were up for another challenge. :-) It took me ages to get some clue about how to use fix, quite apart from combining it with flip. The concept of passing the output of a function as one of its parameters (tying the knot) can be difficult to accept, particularly if you haven't studied lambda calculus. Note that I could have just written this: let iterate a = do ... iterate a' ... iterate accum Or this: fix iterate accum where iterate a = do ... iterate a' ... Though with the latter, I presume you would still be confused about how I can pass two arguments to a function that only takes one. Actually, that's not that difficult. Say I have a function f that takes two arguments. Then I could write: (id f) a b No problem. But function application associates to the left (at least in value-land), so I could just as easily write: id f a b You could say I was passing three arguments to id, which only takes one argument. But id returns its first argument, so I'm really just passing the last two arguments to the function returned by id. So with my use of flip fix, I'm really just calling fix on the anonymous function (\iterate accum - ...), and then the parameter (accum) is passed to the function returned by fix. So now you just need a couple of weeks (or months if you're as slow as me) to understand what fix is all about... :-) There is the question of whether it's preferable to use the let form or the fix form for embedding a recursive function in the middle of a do-block. I don't know if there's any consensus on this question, but it seems to me to be about whether one prefers to read a function top-down or bottom-up. I think I'm about 80/20 top-down/bottom-up. When I read a let, I know (due to laziness) that it doesn't have any effect until the bindings are used, so I usually find myself scanning forward to find those uses. When I read fix \f - ..., I see exactly how the (anonymous) function is used, just before I get to its definition. So fix helps me to see things in a mostly top-down fashion. A couple of times I have wished that the libraries contained pre-flipped versions of fix, for example: fix1 a f = fix f a fix2 a b f = fix f a b fix3 a b c f = fix f a b c Any opinions on whether this would be a worthwhile addition? Or would it just legitimise an obscure idiom? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)
On the topic of 'fix', is there any good tutorial for fix? I searched google, but mostly came up with pages including things like 'bug fix'. It's hard for me to get an intuition about it when 'fix' always stack overflows on me because I don't really know how to use it. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)
Bryan Burgers: On the topic of 'fix', is there any good tutorial for fix? I searched google, but mostly came up with pages including things like 'bug fix'. It's hard for me to get an intuition about it when 'fix' always stack overflows on me because I don't really know how to use it. I don't know of any tutorials that teach how to use fix, but these are some of the pages that helped me on the way towards understanding what it is: http://en.wikipedia.org/wiki/Fixed_point_combinator http://en.wikipedia.org/wiki/Anonymous_recursion In Haskell, it might help to note the equivalence between a and a', b and b', etc, in the following (given appropriate definitions for p, q, r, s, t, etc): a = fix (\f - if t then f else r) a' = let f = (if t then f else r) in f b = fix (\f x - if t' x then f (s' x) else r' x) p b' = let f x = (if t' x then f (s' x) else r' x) in f p c = fix (\f x y - if t'' x y then uncurry f (s'' x y) else r'' x y) p q c' = let f x y = (if t'' x y then uncurry f (s'' x y) else r'' x y) in f p q etc. The first case is not of much practical use, since each iteration of f must produce the same result, so it must either return immediately (if it doesn't recurse into f) or never (if it does). The other cases can be useful, since the additional arguments can be used by the implementation of f to decide whether or not to recurse. When writing an anonymous function inside an invocation of fix, the main thing to realise is that the first argument of that anonymous function is the anonymous function itself. You can use that argument to make a recursive call to the anonymous function. So you could say it's not really anonymous after all. Of course, you eventually have to return without recursing if you want to avoid an infinite loop. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
