News for hackers. Stuff that matters.
Re:Algebraic patterns – Semigroup by Bromskloss on Sunday July 17, 2016 @08:01AM (#12109893)
How does that work in Haskell? Is the user of a semigroup somehow guaranteed that its operation is associative?
Re:Algebraic patterns – Semigroup by tikhonj on Sunday July 17, 2016 @12:17PM (#12110619)
No. Guaranteeing typeclass laws like associativity is hard. People have looked into various ways to do that, but haven't found anything completely satisfying. It's either hard for the programmer (dependent typing) or hard to implement (automatic theorem proving). I hope that'll change, but for now Haskell does not have any facilities for specifying or enforcing typeclass laws.

As it is, it works more or less exactly like interfaces from other languages. When you implement Comparable in Java you implicitly expect certain laws (ie that it's a valid ordering), but there is also no way to specify or verify them.

Re:Algebraic patterns – Semigroup by Bromskloss on Sunday July 17, 2016 @04:16PM (#12111605)
Clueless suggestion: What about the programmer (who implements the semigroup) also providing a proof (that can be automatically checked) that it satisfies associativity? Is that method perhaps already covered by one of the examples you mentioned?
Re:Algebraic patterns – Semigroup by reuben364 on Sunday July 17, 2016 @05:22PM (#12111900)
That is the dependent typed aspect mentioned. This is actually done in Idris with VerifiedSemigroup and other verified instances.
Re:Algebraic patterns – Semigroup by Bromskloss on Sunday July 17, 2016 @06:48PM (#12112278)
OK. I'm afraid I don't know enough to make the connection. Actually, I never understood the point of dependent types. They seem to do away with the neat order that types introduce. ¯\_(ツ)_/¯
Re:Algebraic patterns – Semigroup by wereHamster on Sunday July 17, 2016 @08:19AM (#12109942)
The person who implements Semigroup for a data type must ensure that the laws hold.
Re:Algebraic patterns – Semigroup by haimez on Sunday July 17, 2016 @02:56PM (#12111262)
Which is where property based testing really shines. Still requires the implementer to be a good citizen and write those tests though.
Re:Algebraic patterns – Semigroup by kristianp on Sunday July 17, 2016 @09:06PM (#12112707)