1 {-# LANGUAGE RankNTypes #-}
2 {-# LANGUAGE RecordWildCards #-}
3 {-# LANGUAGE ConstraintKinds #-}
5 module Main( main, boo ) where
7 import Prelude hiding (repeat)
9 boo xs f = (\x -> f x, xs)
11 repeat :: Int -> (a -> a) -> a -> a
12 repeat 1 f x = f x
13 repeat n f x = n `seq` x `seq` repeat (n-1) f \$ f x
15 ---- Buggy version
16 ------------------
18 type Numerical a = (Fractional a, Real a)
20 data Box a = Box
21 { func :: forall dum. (Numerical dum) => dum -> a -> a
22 , obj :: !a }
24 do_step :: (Numerical num) => num -> Box a -> Box a
25 do_step number Box{..} = Box{ obj = func number obj, .. }
27 start :: Box Double
28 start = Box { func = \x y -> realToFrac x + y
29 , obj = 0 }
31 test :: Int -> IO ()
32 test steps = putStrLn \$ show \$ obj \$ repeat steps (do_step 1) start
34 ---- Driver
35 -----------
37 main :: IO ()
38 main = test 2000 -- compare test2 10000000 or test3 10000000, but test4 20000
41 {-
42 ---- No tuple constraint synonym is better
43 ------------------------------------------
45 data Box2 a = Box2
46 { func2 :: forall num. (Fractional num, Real num) => num -> a -> a
47 , obj2 :: !a }
49 do_step2 :: (Fractional num, Real num) => num -> Box2 a -> Box2 a
50 do_step2 number Box2{..} = Box2{ obj2 = func2 number obj2, ..}
52 start2 :: Box2 Double
53 start2 = Box2 { func2 = \x y -> realToFrac x + y
54 , obj2 = 0 }
56 test2 :: Int -> IO ()
57 test2 steps = putStrLn \$ show \$ obj2 \$ repeat steps (do_step2 1) start2
59 ---- Not copying the function field works too
60 ---------------------------------------------
62 do_step3 :: (Numerical num) => num -> Box a -> Box a
63 do_step3 number b@Box{..} = b{ obj = func number obj }
65 test3 :: Int -> IO ()
66 test3 steps = putStrLn \$ show \$ obj \$ repeat steps (do_step3 1) start
68 ---- But record wildcards are not at fault
69 ------------------------------------------
71 do_step4 :: (Numerical num) => num -> Box a -> Box a
72 do_step4 number Box{func = f, obj = x} = Box{ obj = f number x, func = f }
74 test4 :: Int -> IO ()
75 test4 steps = putStrLn \$ show \$ obj \$ repeat steps (do_step4 1) start
76 -}
79 {-
80 First of all, very nice example. Thank you for making it so small and easy to work with.
82 I can see what's happening. The key part is what happens here:
83 {{{
84 do_step4 :: (Numerical num) => num -> Box a -> Box a
85 do_step4 number Box{ func = f, obj = x}
86 = Box{ func = f, obj = f number x }
87 }}}
88 After elaboration (ie making dictionaries explicit) we get this:
89 {{{
90 do_step4 dn1 number (Box {func = f, obj = x })
91 = Box { func = \dn2 -> f ( case dn2 of (f,r) -> f
92 , case dn2 of (f,r) -> r)
93 , obj = f dn1 number x }
94 }}}
95 That's odd! We expected this:
96 {{{
97 do_step4 dn1 number (Box {func = f, obj = x })
98 = Box { func = f
99 , obj = f dn1 number x }
100 }}}
101 And indeed, the allocation of all those `\dn2` closures is what is causing the problem.
102 So we are missing this optimisation:
103 {{{
104 (case dn2 of (f,r) -> f, case dn2 of (f,r) -> r)
105 ===>
106 dn2
107 }}}
108 If we did this, then the lambda would look like `\dn2 -> f dn2` which could eta-reduce to `f`.
109 But there are at least three problems:
110 * The tuple transformation above is hard to spot
111 * The tuple transformation is not quite semantically right; if `dn2` was bottom, the LHS and RHS are different
112 * The eta-reduction isn't quite semantically right: if `f` ws bottom, the LHS and RHS are different.
114 You might argue that the latter two can be ignored because dictionary arguments are special;
115 indeed we often toy with making them strict.
117 But perhaps a better way to avoid the tuple-transformation issue would be not to construct that strange expression in the first place. Where is it coming from? It comes from the call to `f` (admittedly applied to no arguments) in `Box { ..., func = f }`. GHC needs a dictionary for `(Numerical dum)` (I changed the name of the type variable in `func`'s type in the definition of `Box`). Since it's just a pair GHC says "fine, I'll build a pair, out of `Fractional dum` and `Real dum`. How does it get those dictionaries? By selecting the components of the `Franctional dum` passed to `f`.
119 If GHC said instead "I need `Numerical dum` and behold I have one in hand, it'd be much better. It doesn't because tuple constraints are treated specially. But if we adopted the idea in #10362, we would (automatically) get to re-use the `Numerical dum` constraint. That would leave us with eta reduction, which is easier.
121 As to what will get you rolling, a good solution is `test3`, which saves instantiating and re-generalising `f`. The key thing is to update all the fields ''except'' the polymorphic `func` field. I'm surprised you say that it doesn't work. Can you give a (presumably more complicated) example to demonstrate? Maybe there's a separate bug!
123 -}