Skip to content

Lazier Lazy

Amazing work, I greatly enjoyed reading the blog post and playing with the code.

Here's a potential improvement. This version of the Lazy module, based on Endless

data Weaving m a b where
  Weaving :: m (Weave m b) -> (b -> a) -> Weaving m a b

data Weave m a where
  Pure :: a -> Weave m a
  Weft :: Some (Weaving m a) -> Weave m a

instance Functor (Weave m) where
  fmap f (Pure x)                     = Pure (f x)
  fmap f (Weft (Some ~(Weaving u g))) = Weft $ Some $ Weaving u (f . g)

instance Applicative m => Applicative (Weave m) where
  pure = Pure
  liftA2 f s w = fmap (uncurry f) $ case s of
    Pure x -> (,) x <$> w
    Weft (Some ~(Weaving u g)) -> Weft $
      case (case w of
          Pure y -> Some $ Weaving (pure $ pure y) id
          Weft t -> t) of
        Some ~(Weaving v h) ->
          Some $ Weaving (liftA2 (liftA2 (,)) u v) $ \ ~(x, y) -> (g x, h y)

weft :: m (Weave m a) -> Weave m a
weft u = Weft $ Some $ Weaving u id

mesh :: Monad m => Weave m a -> m a
mesh (Pure x)                     = pure x
mesh (Weft (Some ~(Weaving u f))) = f <$> (u >>= mesh)

goes further than the current Lazy when it comes to laziness tests.

Here's it giving me force level 2 + too strict 2 while not being much slower and still retaining linearity:

  Lazy
    Examples: OK
    Laziness: FAIL (expected)
      force level 0
      force level 1
      force level 2
        too strict 2
        CallStack (from HasCallStack):
          error, called at src/Examples.hs:52:85 in weave-test-0-inplace-we-mixin+6EW4QgITp4UjHOdyGh20U:Examples
       (expected failure)
    Time
      1x:     OK
        14.3 μs ± 5.6 μs,  70 KB allocated,  16 B  copied, 6.0 MB peak memory
      2x:     OK
        28.6 μs ±  12 μs, 139 KB allocated,  30 B  copied, 6.0 MB peak memory, 1.99x
      3x:     OK
        42.9 μs ±  22 μs, 209 KB allocated,  50 B  copied, 6.0 MB peak memory, 2.99x

while the current implementation only gets to force level 1 + too strict 1:

  Lazy
    Examples: OK
    Laziness: FAIL (expected)
      force level 0
      force level 1
        too strict 1
        CallStack (from HasCallStack):
          error, called at src/Examples.hs:52:63 in weave-test-0-inplace-we-mixin+6EW4QgITp4UjHOdyGh20U:Examples
       (expected failure)
    Time
      1x:     OK
        13.1 μs ± 5.5 μs,  56 KB allocated,  14 B  copied, 6.0 MB peak memory
      2x:     OK
        26.0 μs ±  11 μs, 113 KB allocated,  24 B  copied, 6.0 MB peak memory, 1.98x
      3x:     OK
        39.6 μs ±  22 μs, 170 KB allocated,  54 B  copied, 6.0 MB peak memory, 3.02x

Actually, here's another version that preserves linearity and unexpectedly passes (sic!) the laziness tests:

data Weaving m a b where
  Weaving :: Either b (m (Weave m b)) -> (b -> a) -> Weaving m a b

newtype Weave m a = Weft (Some (Weaving m a))

instance Functor (Weave m) where
    fmap f (Weft (Some ~(Weaving u g))) = Weft $ Some $ Weaving u (f . g)

comb
    :: Applicative m
    => Either a1 (m (Weave m a1))
    -> Either a2 (m (Weave m a2))
    -> Either (a1, a2) (m (Weave m (a1, a2)))
comb (Right m1) e2 = Right . liftA2 (liftA2 (,)) m1 $ case e2 of
    Left  a2 -> pure (pure a2)
    Right m2 -> m2
comb (Left a1) (Left a2) = Left (a1, a2)
comb (Left a1) (Right m2) = Right $ fmap (fmap (\a2 -> (a1, a2))) m2

instance Applicative m => Applicative (Weave m) where
  pure x = Weft $ Some $ Weaving (Left ()) $ \_ -> x
  liftA2 f (Weft (Some ~(Weaving u g))) (Weft (Some ~(Weaving v h))) =
    Weft . Some $ Weaving (comb u v) $ \ ~(x, y) -> f (g x) (h y)

weft :: m (Weave m a) -> Weave m a
weft u = Weft $ Some $ Weaving (Right u) id

mesh :: Monad m => Weave m a -> m a
mesh (Weft (Some ~(Weaving u f))) = f <$> (case u of
    Left  t  -> pure t
    Right u' -> u' >>= mesh)

It does appear to be 50% slower than the former, so maybe it's not worth it, dunno (or maybe it can be optimized further):

  Lazy
    Examples: OK
    Laziness: OK (unexpected)
      force level 0
      force level 1
      force level 2
       (unexpected success)
      Use -p '/Lazy.Laziness/' to rerun this test only.
    Time
      1x:     OK
        21.4 μs ±  13 μs, 103 KB allocated,  40 B  copied, 6.0 MB peak memory
      2x:     OK
        42.8 μs ±  22 μs, 205 KB allocated,  55 B  copied, 6.0 MB peak memory, 2.00x
      3x:     OK
        60.7 μs ±  25 μs, 307 KB allocated,  71 B  copied, 6.0 MB peak memory, 2.83x

What do you think?

Edited by effectfully