foldl1 and foldr1

[rhendric]

Should foldl1 and foldr1 be added either to the Foldable1 class or as helpers in the Data.Semigroup.Foldable module? They can be implemented, if awkwardly, in terms of foldMap1:

import Prelude

import Data.Monoid.Dual (Dual(..))
import Data.Newtype (alaF)
import Data.Semigroup.Foldable (class Foldable1, foldMap1)

data FoldRight1 a = FoldRight1 (a -> (a -> a -> a) -> a) a

instance foldRight1Semigroup :: Semigroup (FoldRight1 a) where
  append (FoldRight1 lf lr) (FoldRight1 rf rr) = FoldRight1 (\a f -> lf (f lr (rf a f)) f) rr

mkFoldRight1 :: forall a. a -> FoldRight1 a
mkFoldRight1 = FoldRight1 const

runFoldRight1 :: forall a. FoldRight1 a -> (a -> a -> a) -> a
runFoldRight1 (FoldRight1 f a) = f a

foldr1 :: forall a f. Foldable1 f => (a -> a -> a) -> f a -> a
foldr1 = flip (runFoldRight1 <<< foldMap1 mkFoldRight1)

foldl1 :: forall a f. Foldable1 f => (a -> a -> a) -> f a -> a
foldl1 = flip (runFoldRight1 <<< alaF Dual foldMap1 mkFoldRight1) <<< flip

but allowing instances to define their own for efficiency, as Foldable does, would be nice (in which case these could also be added as default implementations).

[hdgarrood]

Adding foldl1 and foldr1 to the class without the Semigroup constraint sounds good to me. It's breaking, but only for types which define a Foldable1 instance. Is FoldRight1 a genuine semigroup, or just a hack to get the thing to work?

[rhendric]

It's a genuine semigroup iff append is associative, which unless I've made a mistake, it is:

append (FoldRight1 xf xr) (append (FoldRight1 yf yr) (FoldRight1 zf zr))
  = append (FoldRight1 xf xr) (FoldRight1 (\a f -> yf (f yr (zf a f)) f) zr)
  = FoldRight1 (\a f -> xf (f xr ((\a' f' -> yf (f' yr (zf a' f')) f') a f)) f) zr
  = FoldRight1 (\a f -> xf (f xr (yf (f yr (zf a f)) f)) f) zr

append (append (FoldRight1 xf xr) (FoldRight1 yf yr)) (FoldRight1 zf zr)
  = append (FoldRight1 (\a f -> xf (f xr (yf a f)) f) yr) (FoldRight1 zf zr)
  = FoldRight1 (\a f -> (\a' f' -> xf (f' xr (yf a' f')) f') (f yr (zf a f)) f) zr
  = FoldRight1 (\a f -> xf (f xr (yf (f yr (zf a f)) f)) f) zr