Haskell for Imperative Programmers #35 - Semigroup & Monoid
ฝัง
- เผยแพร่เมื่อ 9 ก.ค. 2024
- In this video it's going to get theoretical!
Documentation:
hackage.haskell.org/package/b...
hackage.haskell.org/package/b...
Further reading:
en.wikipedia.org/wiki/Algebra...
Timestamps:
00:00 - Intro
01:04 - Algebras and their definition
05:10 - Magma definition
05:35 - Semigroup definition
07:18 - Semigroup examples
09:10 - Monoid definition
11:30 - Monoid for [a]
12:08 - Monoids for numerical types
15:24 - What algebraic structures are good for
Support me on Ko-fi:
ko-fi.com/phagenlocher - วิทยาศาสตร์และเทคโนโลยี
Finally someone who understands learning: without the why, the content is pointless. Thank for this content, this is the most engaging and simple explanation on the starting point of category theory I've found after watching and reading for many hours.
It would also be great if you could mention your references somewhere in the video. Did you really learn all this only from Hackage and WIkipedia?
There is one more reason to formulate patterns like this, which is in my opinion even more important than any one that you mentioned. Programming is all about patterns and the better a language is at capturing and formalising those patterns, the better language it is overall. Why patterns are important? Well because we are extremely good at recognising patterns. That helps us a lot to learn new stuff or find our way around in complex systems. For instance once upon a time I was learning the programming language OCaml, which has a wonderful concurrency library called Lwt. I needed to learn that library for a project that I was building. So I started reading the documentation and was reading it and it didn't really explained that much until I found out there were bind and return functions. At that moment I said to myself: aha, so it's just a monad! And voila, from that moment on I was capable of basic usage of the library. Those two definitions alone were sufficient to get me started on using the library. This was an amazing experience and it was all just because I recognised a familiar pattern in the system that helped me further nagivate my learning process and use the system productively very quickly.
Another awesome video in this awesome series, I was afraid when you gave the MATH WARNING, but I think you explained it really well and I was able to follow along. My use case for haskell is only Xmonad for the moment but the more I learn about it the more I wanna try to use it in other contexts. Having a type system whose design is based on algebraic proofs I think is such an cool idea and I certainty think it gives the programmer much more confidence about program correctness than the Object Oriented Patterns, which at best are glorified common sense and at worse are over engineered garbage. I wish other languages would take notes from haskell's type system.
Hell yeah, I am actually studying group theory right now
stimes actually illustrates very well the practical usefulness of the Semigroup typeclass. Because of associativity, multiple operations with the same element can be grouped by the binary digits of the number of times it is performed, which is the default implementation and is very fast. For example, one can calculate large Fibonacci-numbers by taking powers of the 2x2 matrix (0 1)(1 1). One just needs to code up the multiplication and make it the diamond operator of the Semigroup instance; stimes takes care of the rest.
data Mat2by2 = M Integer Integer Integer Integer deriving (Show)
instance Semigroup Mat2by2 where
M a b c d M e f g h = M (a*e+b*g) (a*f+b*h) (c*e+d*g) (c*f+d*h)
fib :: Integer -> Integer
fib n = m11 $ stimes (n + 1) (M 0 1 1 1) where
m11 (M x _ _ _) = x
The use cases are impressive, great work!
Thank you, amazing work!
Best Haskell tutorial videos on the Internet! :)
Such a great channel!!
Excellent! Thank you!
Thank you very much for the content
In mathematics semigroup and monoid is the same thing. Monoid is Bourbaki's word.
The general constraint for a hash function should not be forgotten that if 2 (possibly different) objects are equal according to a certain equivalence relation then the according hash function must yield the same value for these objects.
Of course you can first map every objects to a base value which represents the equivalence class it belongs to. Then for Haskell these base values have no identity and so the purity of the hash function ensures the above general constraint.
Your example of distributed computation made me go back and watch the middle that I had skipped; I'm not a mathematician so I don't care about proofs & perfect rigor, but the (eventual) capability to trivially distribute a bunch of computation without having to thread & such would be awesome. Especially as we move away from single core performance and get more & more cores into our computers. The future will eventually be held by ease of parallelization, and formally describing properties like associativity will help enable that.
Yep, this is the reduce part of map-reduce. sconcat is an associative but not commutative reduction (Futhark reduce_comm uses both). Languages like OpenMP and Chapel have specific support for reductions also. The directional variant is folds, which are also common to most array languages.
Actually, the domain for “school arithmetic” as you call it is not the real numbers for division… {R} - {0}
Awesome.. thank you
Can you provide us with further sources (books) about the topics we have seen here?
Thanks ;)
The syntax in the last slide:
prop x y = ((xy)mempty) === (x(ymempty))
where types = (x::[Int],y::[Int])
is not standard haskell.
Where is it defined and which extension can be used to translate this language into valid haskell?
You are right. Watch video #18 - QuickCheck
The type of the hash function should be more general, i.e. f:: A -> B. And it's not a binary operation.
Why nothing algebra domain is empty set, but operations is magic none and not an empty set too?