On 07/10/2010 14:03, Derek Elkins wrote:
On Thu, Oct 7, 2010 at 8:44 AM, Luke Palmer<lrpal...@gmail.com> wrote:
On Thu, Oct 7, 2010 at 6:17 AM, Brent Yorgey<byor...@seas.upenn.edu> wrote:
The source code seems to be easy to read, but I don't think I understand that.
For me I think if I change the first line from
fib = ((map fib' [0 ..]) !!)
to
fib x = ((map fib' [0 ..]) !!) x
It should do the same thing since I think the previous version is just an
abbreviation for the second one.
Semantically, yes. And it's possible that ghc -O is clever enough to
notice that. But at least under ghci's naive evaluation strategy,
lambdas determine the lifetime of expressions. Any expression within a
lambda will be re-evaluated each time the lambda is expanded. Thus:
fib = (map fib' [0..] !!) -- fast
fib = \x -> map fib' [0..] !! x -- slow
fib = let memo = map fib' [0..] in \x -> memo !! x -- fast
The section works because "(a %^&)" (for some operator %^&) is short
for "(%^&) a" and "(%^& a)" is short for "flip (%^&) a". Sections
don't expand into lambdas.
In other words, in the middle expression, there is a new "map fib'
[0..]" for each x, whereas in the others, it is shared between
invocations.
Does that make sense?
In general, f is not semantically equivalent to \x -> f x in Haskell.
However, that is not what Brent said. The Report -defines- (m !!) as
\x -> m !! x. GHC simply does not follow the Report here. You can
witness this via: (() `undefined`) `seq` 0. By the Report this should
evaluate to 0, in GHC it evaluates to undefined.
Interesting. You're absolutely right, GHC doesn't respect the report,
on something as basic as sections! The translation we use is
(e op) ==> (op) e
once upon a time, when the translation in the report was originally
written (before seq was added) this would have been exactly identical to
\x -> e op x, so the definition in the report was probably used for
consistency with left sections.
We could make GHC respect the report, but we'd have to use
(e op) ==> let z = e in \x -> z op x
to retain sharing without relying on full laziness.
This might be a good idea in fact - all other things being equal, having
lambdas be more visible to the compiler is a good thing.
Cheers,
Simon
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
