kowainik / slist

♾️ Sized list
https://kowainik.github.io/projects/slist
Mozilla Public License 2.0
46 stars 6 forks source link

Monoid instance doesn't obey the concatenation law #23

Closed rszczers closed 4 years ago

rszczers commented 4 years ago

I've played around with hedgehog-classes and your library in hope to solve #5. I guess I found a minor bug with mconcat: the monoid instance didn't obey the concatenation law (i.e. mconcat ≡ foldr mappend mempty). Consecutively, there were also problems with associativity and right identity monad laws; here's relevant part of test log:

Monoid: Concatenation   ✗ <interactive> failed 
    after 41 tests and 47 shrinks.

    forAll0 =
      [ Slist { sList = [ 0 ] , sSize = Size 1 }
      , Slist { sList = [ 1 ] , sSize = Size 1 }
      ]

    ━━━ Context ━━━
    When testing the Concatenation law(†), for the Monoid typeclass, the following test failed: 

    mconcat as ≡ foldr mappend mempty as, where
      as = [Slist {sList = [0], sSize = Size 1},Slist {sList = [1], sSize = Size 1}]
      mempty = Slist {sList = [], sSize = Size 0}

    The reduced test is: 
      Slist {sList = [1,0], sSize = Size 2} ≡ Slist {sList = [0,1], sSize = Size 2}

    The law in question: 
      (†) Concatenation Law: mconcat ≡ foldr mappend mempty

So mconcat concatenated lists in a wrong order, I guess. I flipped just here (xL ++ l, s + xS) to (l ++ xL, s + xS) and now all tests are passing fine :-)

vrom911 commented 4 years ago

Unfortunately, due to the usage of the hedgehog-classes library, I can't merge this to the project, as I'd like to support three latest major GHC versions, however hedgehog-classes limits this intentionally.

I really appreciate your help, but closing the PR and will implement this shortly by hands.