- Haskell-Cafe - Haskell.org

memoization hints
by David Feuer 23 Jan '02

23 Jan '02

(sorry I can't reply directly, but my mail situation is a bit messed up) Simon Marlow said: ----------- > Take a standard sort of example: > fib n =3D let > f =3D 0:1:zipWith (+) f (tail f) > in > f !! n > -- code that first calculates fib 1000, then fib 3, fib 4, then does > some other stuff >=20 >=20 > I believe that the entire list will be maintained (when compiled with > ghc -O) after calculating fib 1000, despite the fact that it=20 > will never > be used again. GHC will retain the list only if it determines that it might still be required, in other words if fib might be called again. If fib will never be called again, then the chances are that the list will be garbage collected. (I'm being intentionally imprecise, because of course the compiler can't in general determine accurately whether fib will or will not be called again).=20 If you don't want the list to be retained at all, you can use the -fno-full-laziness flag to GHC. Unfortunately there's no way to do this at the level of a single binding. Cheers, Simon ----------------- What I was talking about was whether it would be possible/practical to extend the language to allow this control at the single-binding level. This kind of control seems useful even without full laziness, but with full laziness it becomes essential--it is no longer possible to hide something in a function to prevent it from being persistent, and as all here know, it is often much better to compute values of a list over and over than to store the whole list in memory. This seems to require some weird form of garbage collection, where an accessible object which may be used again is collected. It is necessary, however, to ensure that enough information is retained to be able to reconstruct the value when necessary. I don't know nearly enough about GC to say what this might involve, but I'd be interested to hear what other people think about this problem, this (vague) solution, and perhaps other solutions. -- /Times-Bold 40 selectfont/n{moveto}def/m{gsave true charpath clip 72 400 n 300 -4 1{dup 160 300 3 -1 roll 0 360 arc 300 div 1 1 sethsbcolor fill}for grestore 0 -60 rmoveto}def 72 500 n(This message has been)m (brought to you by the)m(letter alpha and the number pi.)m(David Feuer) m(David_Feuer(a)brown.edu)m showpage

1 0

RE: memoization hints?
by Simon Marlow 22 Jan '02

22 Jan '02

> Take a standard sort of example: > fib n = let > f = 0:1:zipWith (+) f (tail f) > in > f !! n > -- code that first calculates fib 1000, then fib 3, fib 4, then does > some other stuff > > > I believe that the entire list will be maintained (when compiled with > ghc -O) after calculating fib 1000, despite the fact that it > will never > be used again. GHC will retain the list only if it determines that it might still be required, in other words if fib might be called again. If fib will never be called again, then the chances are that the list will be garbage collected. (I'm being intentionally imprecise, because of course the compiler can't in general determine accurately whether fib will or will not be called again). If you don't want the list to be retained at all, you can use the -fno-full-laziness flag to GHC. Unfortunately there's no way to do this at the level of a single binding. Cheers, Simon

1 0

RE: Programming style question
by Simon Marlow 22 Jan '02

22 Jan '02

> Ah, now I see the issue seems to be closeley related to > full lazy lambda lifting. Given.. > f = \x -> <blah> x > where <blah> has no free occurences of x, then I > thought the compiler would reduce this immediately to > f = <blah> > > Full lazy lambda lifting would give something like this.. > b = <blah> > f = \x -> b x > But this still requires, the (\x -> b x) to be reduced to b > to get.. > b = <blah> > f = b > (and hence f = <blah>) This transformation (eta reduction) is done by GHC under certain circumstances; in particular I believe that in the case where a binding can be eta-reduced so that its right hand side becomes a variable, then the reduction will be performed on the grounds that we can then substitute the binding everywhere without loss of efficiency or increase in code size. However, sometimes it is more beneficial to do the opposite, namely eta expansion. This is because in GHC a call to a known function with all the arguments present is the fastest type of call. Eg: f = \x -> h a x could be reduced to f = h a but if h has arity 2, then the call to h changes from a fast to a slow one, and futhermore we can't make any fast calls to f. On the other hand, the code for the second version is somewhat smaller. There are some subtle tradeoffs here, and this is one of the areas where we often tweak GHC's behaviour in order to try to pick the right balance more often. Cheers, Simon

1 0

Re: Ambiguous types
by Ashley Yakeley 21 Jan '02

21 Jan '02

At 2002-01-21 02:19, Janis Voigtlaender wrote: >The problem is >that for some instance A1 of Ord, l might be an empty list, whereas for >some other instance A2 of Ord, l might be nonempty. Right. I understand now. -- Ashley Yakeley, Seattle WA

1 0

Re: Ambiguous types
by Ashley Yakeley 21 Jan '02

21 Jan '02

I'm quite convinced the Haskell implementations are correct to complain, I just don't understand it intuitively. Anyway, here's an even simpler example: compiles fine: ordnull :: forall a. (Ord a) => [a] -> Bool ordnull = null ordtrue :: (forall a. (Ord a) => [a]) -> Bool ordtrue = const True gives type error: ordnull :: (forall a. (Ord a) => [a]) -> Bool ordnull = null -- Ashley Yakeley, Seattle WA

2 1

Re: Ambiguous types
by Ashley Yakeley 21 Jan '02

21 Jan '02

At 2002-01-21 02:04, Koen Claessen wrote: >But from the type you give the function `emptyList': > > emptyList :: Ord a => [a] > >we cannot derive that the type of the function `emptyList' >does not matter for its result. So, the type checker will >complain. That's it! Consider: -- class C a where emptyList :: [a] instance C Int where emptyList = [] instance C Char where emptyList = "Hello" -- Clearly emptyList has type "(C a) => [a]"... So in the original example, (validActions actor) cannot be compared to the empty list because its value may depend on the type of u. This would not be possible if there were no (Action u) context. -- Ashley Yakeley, Seattle WA

1 0

Re: Ambiguous types
by Ashley Yakeley 21 Jan '02

21 Jan '02

At 2002-01-21 01:15, Koen Claessen wrote: > | But this gives an error: > | > | emptyList :: (Ord a) => [a] > | emptyList = [] > | > | isempty :: Bool > | isempty = null emptyList > >Here is another (very similar) case: > > emptyList :: [a] > emptyList = [] > > showEmptyList :: String > showEmptyList = show emptyList >Now, you might argue that the type error resulting from this >program is too restrictive, since the empty list can always >be shown as: "[]". Of course not, show doesn't know how to show things of arbitrary type [a]. But null is supposed to work on _any_ list. And just from the type of emptyList, Haskell knows that it is a list of something. -- Ashley Yakeley, Seattle WA

2 1

Re: Ambiguous types
by Koen Claessen 21 Jan '02

21 Jan '02

(moved reply to haskell-cafe) Ashley Yakeley wrote: | But this gives an error: | | emptyList :: (Ord a) => [a] | emptyList = [] | | isempty :: Bool | isempty = null emptyList Here is another (very similar) case: emptyList :: [a] emptyList = [] showEmptyList :: String showEmptyList = show emptyList Now, you might argue that the type error resulting from this program is too restrictive, since the empty list can always be shown as: "[]". But this is not true for all types, look at the way the empty *string* is shown. I.e. changing the type of `emptyList' in this example changes the behavior of `showEmptyList'. The compiler does not know what type to choose, and thus gives a type error. /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen phone:+46-31-772 5424 mailto:koen@cs.chalmers.se ----------------------------------------------------- Chalmers University of Technology, Gothenburg, Sweden

1 0

Re: [Fwd: Re: type class VS struct/functor]
by Ashley Yakeley 19 Jan '02

19 Jan '02

At 2002-01-18 18:59, Ahn Ki-yung wrote: >Each of these Set types takes a string, but the membership test is >different. This is an annoying case in Haskell, because you can make a >String a member of the Eq typeclass in only one way. Your example seemed to translate into Haskell quite straightforwardly... module FunctorTest where { import Char; lowercase = fmap toLower; data EQ' t = EQ' { eq :: t -> t -> Bool }; data SET elt set = SET { empty :: set, add :: elt -> set -> set, mem :: elt -> set -> Bool }; fSet :: EQ' t -> SET t [t]; fSet mEq = SET { empty = [], add = \elt set -> elt:set, mem = let { mm elt [] = False; mm elt (x:xs) = if eq mEq x elt then True else mm elt xs; } in mm }; sensitiveCase :: EQ' String; sensitiveCase = EQ' { eq = \s s' -> s == s' }; insensitiveCase :: EQ' String; insensitiveCase = EQ' { eq = \s s' -> (lowercase s) == (lowercase s') }; sensitiveSet = fSet(sensitiveCase); insensitiveSet = fSet(insensitiveCase); } -- Ashley Yakeley, Seattle WA

1 0

schrist@gmx.net
by c-schnell＠t-online.de 19 Jan '02

19 Jan '02

Please add me to the mailinglist.

1 0