Gabriella439 / foldl

Composable, streaming, and efficient left folds
BSD 3-Clause "New" or "Revised" License
158 stars 51 forks source link

Costrong and Corepresentable instances #197

Closed Skyb0rg007 closed 1 year ago

Skyb0rg007 commented 1 year ago

The Fold a b type represents a left-fold, which means that it is isomorphic to functions of type [a] -> b (assuming the input list is finite). The profunctors package now has typeclasses to represent this isomorphism:

instance Cosieve Fold [] where
    cosieve = fold

instance Corepresentable Fold where
    type Corep Fold = []
    cotabulate f = fmap f list

instance Costrong Fold where
    unfirst = unfirstCorep

-- Laws
-- 1. cosieve . cotabulate == id :: ([a] -> b) -> [a] -> b
--    cosieve (cotabulate f) xs == f xs
--    fold (fmap f list) xs == f xs
--    F.foldr (\a k x -> k $ x . (a:)) (f . ($ [])) xs id == f xs
--    (f . ($ [])) (F.foldl (\k a -> k . (a:)) id xs) == f xs
--    f (F.foldl (\k a -> k . (a:)) id xs []) == f xs
--    f xs == f xs
--
-- 2. cotabulate . cosieve == id :: Fold a b
--    cotabulate (cosieve f) == f
--    fmap (fold f) list == f
--    f == f

Currently, foldl only requires profunctors >= 3.2, with Corepresentable added in profunctors 4.0 and Costrong in 4.3.2, so this addition would require changing the version bounds or adding preprocessor checks.

Gabriella439 commented 1 year ago

I think it's fine to increase the lower bound on profunctors. I'd accept a PR for this