Question on leazy evaluation
Hello, I'm very new to Haskell and I'm learning it in my spare time (ie. just for fun ;) ). I already had a quick look through tutorials, some articles, the Wiki, ... My question is: is there some (simple?) rule/criteria to ensure leazy evaluation will be efficient ? Typically, I process a list and I know each list item can be processed as it come. But I'm not sure my code uses correctly this property ! Is there some way to be sure leazy evaluation is correctly used by my code ? And are there coding rules that will "ensure" correct leazy evaluation ? Thanks, Pierre -- Pierre Barbier de Reuille INRA - UMR Cirad/Inra/Cnrs/Univ.MontpellierII AMAP Botanique et Bio-informatique de l'Architecture des Plantes TA40/PSII, Boulevard de la Lironde 34398 MONTPELLIER CEDEX 5, France tel : (33) 4 67 61 65 77 fax : (33) 4 67 61 56 68
On Thu, 24 Mar 2005, Pierre Barbier de Reuille wrote:
My question is: is there some (simple?) rule/criteria to ensure leazy evaluation will be efficient ?
One rule of thumb is: If your implementation works for infinite lists then it will also be quite efficient for finite lists. Do you mean criteria of this kind?
Henning Thielemann a écrit :
On Thu, 24 Mar 2005, Pierre Barbier de Reuille wrote:
My question is: is there some (simple?) rule/criteria to ensure leazy evaluation will be efficient ?
One rule of thumb is: If your implementation works for infinite lists then it will also be quite efficient for finite lists. Do you mean criteria of this kind?
I think you mean doing something like : take 10 (fct infiniteList) .. this answers my first question: how to be sure it uses leazy evaluation :). But now the second (hardest ?) question: if the answer is "no", how can I detect where leazy evaluation fails ? Is there first approximation rules, at least pointing where leazy evaluation is likely to fail ? (like avoiding functions like length, minimum, ..., some structure ...) Pierre -- Pierre Barbier de Reuille INRA - UMR Cirad/Inra/Cnrs/Univ.MontpellierII AMAP Botanique et Bio-informatique de l'Architecture des Plantes TA40/PSII, Boulevard de la Lironde 34398 MONTPELLIER CEDEX 5, France tel : (33) 4 67 61 65 77 fax : (33) 4 67 61 56 68
Still on the same subject, I solved one problem but don't really understand why it didn't work in the first place ! Although it seems to be a difference between "newtype" and "data" ! I have a newtype defined as : data Fct s a = Fct (s -> [a]) and a function defined by : plus :: Fct a b -> Fct a b -> Fct a b plus (Fct f1) (Fct f2) = Fct ( \ a -> (f1 a) ++ (f2 a) ) For some reason, this function does not use leazy evaluation ! I can test it using : test_fct :: Fct Int Int test_fct = Fct( \ i -> [i] ) value = head $ apply (foldr plus test_fct $ repeat test_fct) 12 ... trying to get "value" does not terminate ! But if I change the type declaration into : newtype Fct s a = Fct (s -> [a]) ... it works ! The "plus" function uses leazy evaluation and "value" can be computed. Now, I didn't really understood the difference between newtype and data. Can anyone explain that behaviour ? Thank you, Pierre -- Pierre Barbier de Reuille INRA - UMR Cirad/Inra/Cnrs/Univ.MontpellierII AMAP Botanique et Bio-informatique de l'Architecture des Plantes TA40/PSII, Boulevard de la Lironde 34398 MONTPELLIER CEDEX 5, France tel : (33) 4 67 61 65 77 fax : (33) 4 67 61 56 68
On Fri, Mar 25, 2005 at 03:13:48PM +0100, Pierre Barbier de Reuille wrote:
plus :: Fct a b -> Fct a b -> Fct a b plus (Fct f1) (Fct f2) = Fct ( \ a -> (f1 a) ++ (f2 a) )
For some reason, this function does not use leazy evaluation ! I can test it using :
test_fct :: Fct Int Int test_fct = Fct( \ i -> [i] )
value = head $ apply (foldr plus test_fct $ repeat test_fct) 12
... trying to get "value" does not terminate !
That's because you pattern match on (Fct f2) in plus. If Fct is defined with 'data', this causes the second argument of plus to be evaluated.
But if I change the type declaration into :
newtype Fct s a = Fct (s -> [a])
... it works ! The "plus" function uses leazy evaluation and "value" can be computed.
If Fct is defined with 'newtype', it doesn't cause evaluation, because Fct is a kind of virtual / non-existent / zero-cost data constructor, so there is nothing to evaluate. Try these definitions: plus (Fct f1) ~(Fct f2) = Fct ( \ a -> (f1 a) ++ (f2 a) ) plus (Fct f1) f2 = Fct ( \ a -> (f1 a) ++ (apply f2 a) ) The first uses an irrefutable pattern, the second doesn't pattern match on Fct in the second argument. Best regards Tomasz
participants (3)
-
Henning Thielemann -
Pierre Barbier de Reuille -
Tomasz Zielonka