Nice fusible list abstraction: `foldDfs`
While working on #18964, I came up with the following fusible list combinator but ultimately decided against using it (time is short, plus would have to figure out how to write back the FB helpers to list functions):
-- | A depth-first search on lists.
--
-- @'foldDfs' discover finish l r xs@ will fold over the list @xs@, applying
-- @discover@ as if in a left-fold starting with accumulator @l@ and afterwards
-- applying @finish@ as if in a right-fold starting with accumulator @r@.
-- The choice of @r@ can depend on the final accumulator of the left fold.
--
-- 'foldDfs' generalises 'foldl', 'foldr' and 'ifoldr' in the following way:
-- > foldl f l xs = foldDfs f (\_ _ r -> r) l id xs
-- > foldr f r xs = foldDfs (\l _ -> l) (\_ -> f) r id xs
-- > ifoldr f r xs = foldDfs (\i _ -> i+1) f 0 (const r) xs
foldDfs :: (l -> a -> l) -> (l -> a -> r -> r) -> l -> (l -> r) -> [a] -> r
foldDfs discover finish l r xs = List.foldr c z xs l
where
c a k = Exts.oneShot (\l -> finish l a (k (discover l a)))
z = Exts.oneShot r
{-# INLINE ifoldr #-}
-- | An indexed right fold
ifoldr :: (Int -> a -> b -> b) -> b -> [a] -> b
ifoldr f acc xs = foldDfs (\i _ -> i+1) f 0 (\!_ -> acc) xs
{-# INLINE ifoldr #-}
Note that foldDfs
generalises a number of basic blocks such as foldl
, foldl'
and ifoldr
which in turn can be used to implement fusible implementations for "stateful" combinators like take
, drop*
, scan*
, etc., all of which have to take care of the incredibly subtle interplay of oneShot
annotations (take
and drop
lack these at the moment), strictness, as well as the general WTF of expressing left folds via foldr
. foldDfs
confines all the complicated stuff in one place, where we can focus on optimising well.
With the work in #22465 (closed) we might switch to destroy/unfoldr fusion before long, so this issue might become moot. One more reason not to worry about it too soon, but I wanted to record this combinator somewhere.