On Thursday 07 October 2010 14:17:18, Brent Yorgey wrote: > Hi all, > > See below for this message from one of my students which has me > stumped. Just when you think you understand Haskell... ;) > > I've cc'ed him on this message; please include him on any replies as I > don't think he is subscribed to -cafe. > > -Brent
cf. http://www.haskell.org/pipermail/haskell-cafe/2009-October/067811.html If fib is defined without a type signature, the monomorphism restriction also kicks in, when fib is bound via a function binding, fib x = ... fib has polymorphic type (Num a) => Int -> a and that prevents sharing the list (since there are lists for all Num types). If bound via a simple pattern binding, fib = (map fib' [0 .. ] !!) where ... and the MR is not disabled, fib gets the monomorphic type Int -> Integer and that allows the list to be shared. If you give fib an explicit monomorphic type fib :: Int -> Integer the list will still not be shared if it's bound via a function binding because fib' and the list are bound inside the lambda: fib = \k -> let fib' ... in (map fib' [0 .. ] !!) k fib' is not a constant, so it's not floated out of the lambda, so it's not shared (and a fortiori map fib' [0 .. ] isn't shared). if fib is bound via a simple pattern binding (and no explicit lambda is given), fib' and the list are bound outside the lambda and hence shared: fib = let fib' = ...; lst = map fib' [0 .. ] in \k -> lst !! k Note however that using the list as "map fib' [0 .. ]" is more brittle than giving it a name and binding it explicitly in the where clause: fib :: Int -> Integer fib = (fibList !!) where fibList = map fib' [0 .. ] fib' 0 = 0 ... For the time being, GHC treats both the same, but the latter is less likely to break. > > ----- Forwarded message from Yue Wang <yulew...@gmail.com> ----- > > From: Yue Wang <yulew...@gmail.com> > Date: Tue, 5 Oct 2010 21:23:57 -0400 > To: Brent Yorgey <byor...@seas.upenn.edu> > Subject: store evaluated values > > Hi, Anthony (or Brent): > > Last time (in Anthony's TA office hour) we talked about how to store > evaluated values in the program for later used. I googled for a while > and wrote some code. But I still encountered two problems. Can you take > a look? Thanks. > > First, let's write the naive fib function: > > naive_fib 0 = 0 > naive_fib 1 = 1 > naive_fib n = trace(show(n)) > naive_fib (n - 1) + naive_fib (n - 2) > > this works good except it tries to calculate the same expression many > times. So when we evaluate it ghci will show the following: *Main> > naive_fib 5 > 5 > 4 > 3 > 2 > 2 > 3 > 2 > 5 > > Then there is a clever way to do that on haskell wiki: > > fib = ((map fib' [0 ..]) !!) > where > fib' 0 = 0 > fib' 1 = 1 > fib' n =trace(show(n)) fib (n - 1) + fib (n - 2) > > When we evaluate the same expression we can see it does not evaluate the > redundant expression over and over: *Main> fib 5 > 5 > 4 > 3 > 2 > 5 > > 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. But After I change that, *Main> fib > 5 > 5 > 4 > 3 > 2 > 2 > 3 > 2 > 5 > > So why does the x here matters? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
