Default implementation of foldl seems backwards

[amarqueslee-da]

Affected Daml version

1.18.0

Bug description

If I implement a new datatype and give an instance of Foldable with foldMap and foldr implementations, the default foldl implementation will fold over my data structure from right-to-left instead of left-to-right

To reproduce

I invented a superficial type that just wraps the standard list:

data TestFoldable a = TestFoldable [a]
  deriving (Eq, Show)

instance Functor TestFoldable where
  fmap f (TestFoldable as) = TestFoldable $ fmap f as

instance Foldable TestFoldable where
  foldl f z (TestFoldable as) = foldl f z as -- comment me out
  foldr f z (TestFoldable as) = foldr f z as
  foldMap f (TestFoldable as) = foldMap f as

And wrote a test scenario for foldl that I expect to pass:

foldl_executesFromLeftToRight : Scenario ()
foldl_executesFromLeftToRight = do

  foldl (\sum next -> sum <> " " <> next) "" (TestFoldable [ "these", "items", "should", "be", "in", "order"])
      === " these items should be in order"

The test passes when the foldl implementation is provided, but fails if the foldl implementation is commented out with this error:

Message: 
  Scenario execution failed:
  Unhandled exception:
  DA.Exception.AssertionFailed:AssertionFailed@3f4deaf145a15cdcfa762c058005e2edb9baa75bb7f95a4f8f6f937378e86415
  with
  message =
  "Failure, expected " order in be should items these" == " these items should be in order""

  Ledger time: 1970-01-01T00:00:00Z

Expected behavior

I would expect the provided test scenario to pass, even when the provided implementation of foldl is commented-out.

Additional context

The haskell stdlib default implementation for foldl appears to use the Dual wrapper monoid to reverse composition of functions passed to Endo:

    foldl :: (b -> a -> b) -> b -> t a -> b
    foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

The daml implementation looks like it just uses Endo directly, passing flip f.

[stefanobaghino-da]

@amarqueslee-da How have you found out about this? This is quite a remarkable bug that has been lurking in the standard library since it was first implemented around 4 years ago. It's quite impressive it was never detected and we're wondering how much the Foldable type class is useful for end users.