On Sep 20, 2010, at 9:49 AM, Daniel Fischer wrote: > >> which I am inclined to believe. Your 'f' should also run in O(1) space. > > Alas, no. At least with GHC (and I don't see how it could be otherwise), > reverse is always an O(length xs) space operation. > > reverse :: [a] -> [a] > #ifdef USE_REPORT_PRELUDE > reverse = foldl (flip (:)) [] > #else > reverse l = rev l [] > where > rev [] a = a > rev (x:xs) a = rev xs (x:a) > #endif >
Good point, I guess I hadn't really thought that one through. It should have occurred to me that the garbage collector has no idea what 'head' does, and so at the time that the list is forced to WHNF for matching in 'head', everything that reverse _could_ return must be retained, which is the whole list. I think I had a poorly-formed notion that the GC should somehow know that only the (eventual) head of the list would ever be needed. On Sep 20, 2010, at 10:22 AM, Daniel Peebles wrote: > Have we put off the ultra-newbie by derailing his simple question into a > discussion on subtle issues he shouldn't care about this early on? Probably. It's both a joy and a curse having a community so enthusiastic about their language. It's a lot like when people talk perl and everything somehow turns into code golf or just plain obfuscation contests ;) -- James_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
