11 ms·
Algebraic Structures: Things I wish someone had explained about FP
- tel 7y agoCalling these things algebraic structures might help you win some confidence, but the communities which talk about algebraic structures aren't going to be helpful for learning how to program with these things. Mathematicians love algebraic structures (and non-algebraic ones). The advantage really plays out more with the first-order structures, too. Things like monoid, semiring, torsor, group. You also have nice ones in more standard data structures: a balanced tree is an excellent example of a structure where the laws exist to cut out unbalanced trees. In my opinion, there are two things to study here: First, the practice of thinking about abstract structures that apply to concrete data. For this, the practice of thinking of there being a type (or multiple interrelated ones) which offers some set of "constructors" which create the type or augment existing values (gluing new items into a tree, merging two trees, etc) and some set of "laws" for which all values of that type must uphold. It turns out that you can do a lot of analysis of the behavior of these structures in the abstract and then apply it wholesale throughout programs. Many concrete values you work with are the combination of multiple structures in natural ways. Sometimes you can replace whole APIs with hundreds of calls, each named uniquely to this implementation of this type, with just a small set of nicely orthogonal methods with completely standard names. Second, the use of higher order structures like Functor, Applicative, Monad. These get a LOT of airtime because they're both challenging and offer important capabilities. But they're also in a lot of senses their own realm of study. Not only are they developed very uniquely in programming communities (as opposed to what you'll find if you read about the category theoretic definitions) but they are also "higher order" in that they involve functions between types. This higher-order nature both makes their own equations much more complex, but it also means that to see them applying (in languages other than Haskell and its ilk where purity drives this) you have to get really good at seeing languages in an abstract fashion. It's a great skill to develop, but ramps up the difficulty greatly. Master the "first order" ones first. Master concrete, interesting types like Either, Maybe, List (as a source of non-determinism) first. Then come back and see if you can see how the skills you develop with the "first order" structures apply to these higher order, computationally minded types.
- Vosporos 7y agoFor the more beginners of us, I love this blog post / cheatsheet by Julie Moronuki on the matter of Algebraic Structures https://argumatronic.com/posts/2019-06-21-algebra-cheatsheet.html https://argumatronic.com/posts/2019-06-21-algebra-cheatsheet...
- tom_mellior 7y agoThe https://en.wikipedia.org/w/index.php?title=Algebraic_structure&oldid=898454436132 https://en.wikipedia.org/w/index.php?title=Algebraic_structu... link in footnote 1 is broken, it takes me to a page saying 'The revision #898454436132 of the page named "Algebraic structure" does not exist.'. As for the quoted definition, I agree that if this is your first exposure to abstract algebra, you'll need a moment to unpack the sentence, follow some links, and especially, read on. But that's not just Wikipedia; the blog post also takes considerably more than one sentence to explain what it is trying to say. You can't explain everything in one sentence. For whatever it's worth, as a data point relating to a recent discussion on whether a university CS education makes you a better programmer or not: We literally started learning about algebraic structures in the first math class on the first morning of the first year of university. If you're going to program in a setting where algebraic structures (or data types!) are relevant, this university knowledge will help. Finally, this blog looks very nice visually, but the "broken typewriter" font effect makes the code examples much too hard to read. It would be great if the ribbon in that typewriter could be replaced.
- pbhowmic 7y agoI second the comment on the site design. Very beautiful indeed. In fact, I just spent some time looking at the css/scss files.
- jordigh 7y agoI think Wikipedia is wrong here. I never knew that anyone referred to any generic set with operations as an "algebra". That's a magma! An algebra has much more structure than any generic set with operations. Does this really happen? Do people really say generic "algebra" for any set with operations? (And as an aside, I don't like the "abstract algebra" monicker. It sounds so immature and undergraddy. There isn't an ordinary algebra and an abstract algebra. It's all just algebra.)
- gue5t 7y agoWhat structure does an algebra require to merit the name? I've been confused by examples such as the "algebra of a monad", which as I understand it arises from adding an "unwrap" operation in addition to monadic "return" and "join". Most of the references to this only ever refer to specific cases such as an algebra over a monad or an algebra over a functor or a division algebra, etc., and I haven't seen anyone be clear about what makes something an algebra.
- lidHanteyk 7y agoUnfortunately, the author doesn't actually understand functional programming; they think that it has to do with loops and mutability. Also, they cannot get outside of their "I worked really hard for my PhD" mindset for long enough to consider programming as it actually is, rather than as they want to imagine it to be.
- sedeki 7y agoYou might be interested to see https://jrsinclair.com/articles/2019/what-i-wish-someone-had-explained-about-functional-programming/ https://jrsinclair.com/articles/2019/what-i-wish-someone-had... where he puts those things under the header "Wrong Assumptions".
- KirinDave 7y agoMay I humbly recommend you read the article before leveling a complaint about its content, as at least some of this was clearly addressed in the second section, starting above the fold.
- Razengan 7y agoGotta say I love the style/aesthetics of that site.
- mc3 7y agoYou must have good vision, because it's annoying for me to read.
- evmar 7y agoThis post shows a Haskell-ish definition of Functor, then attempts to show the same thing in TypeScript. interface Functor<A> { map<B>(f: (a: A) => B): Functor<B>; } But the TypeScript definition loses something important: the point of a Functor is that you get back the same data type -- there's one `f` in the Haskell defn both in the argument and return type, while this TS definition can give you back any random data type. E.g. the implementation of Array.map could give you back an Either. I don't mean this comment to be a random nitpick of the post. Trying to think these things through is hard, and trying to use things you know to help understand the new idea is not unreasonable. But in particular with PL each thing has so much associated baggage (here in TS, subtyping) that reasoning "by metaphor" often means you end up missing the critical point.
- gcanti 7y agofp-ts [1] contains an implementation of Higher Kinded Types, which TypeScript doesn’t support natively (the idea for emulating higher kinded types in TypeScript is based on "Lightweight higher-kinded polymorphism" [2]) [1] https://github.com/gcanti/fp-ts https://github.com/gcanti/fp-ts [2] https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-ki...
- lacampbell 7y agoHaven't had a coffee yet so go easy on me - doesn't this solve your issue? interface Functor<A> { map<B>(f: (a: A) => A): Functor<A>; } You map over an option, you get an option. You map over an either, you get an either. etc etc.
- tel 7y agoThat gets closer to the problem, but the solution is further away. You don't want to return "Functor" (which is like a vtable, the interface itself) but instead the thing itself which is implementing the Functor interface. So you end up with interface Functor<A> { map<B>(f: (a: A) => A): Self<B> } where `Self` needs to recognize that the type being defined to implement this interface has a "slot". This tends to make things tough.
- 3PS 7y ago> Functor isn’t the only algebraic structure either. I actually wouldn't call it an algebraic structure at all. A functor really isn't just a set with some finitary operations. A quick search online [1] tells me I'm not alone. https://www.quora.com/Why-is-functor-considered-to-be-an-algebraic-structure https://www.quora.com/Why-is-functor-considered-to-be-an-alg...
- vcxy 7y agoAs a mathematician first (only an amature programmer), I wholeheartedly agree.
- Ezku 7y agoI guess this is an easy point of confusion. Are specific instances of functor algebras, then? (What about f-algebras?) What would be the more appropriate word for the category theoretical things the author is trying to refer to here, functor and monad and so on?
- edflsafoiewq 7y agoA monad (on Set) is an "algebraic structure" (eg. the notion of a group). An algebra for that monad is an "algebra" (eg. one individual group). This is the original use for monads in universal algebra, before they were interpreted as computational effects. An algebraic structure like a group or monoid is traditionally given by a signature: a list of what operations it has and what rules the operations need to follow. You can generalize from a signature Sig to a monad M. If a is a set, then Ma is "the set of expressions with constants from a": the set of formal expressions built from elements of a and the operations in Sig and where two expressions are regarded as equal if you can manipulate one into the other using the rules from Sig. The list monad for example corresponds to the signature for monoids. The monad laws can thus be read as expressing "how to do algebra" at the most general level (ie. the level that is common to all algebraic structures). I would gloss them as "the order you evaluate an expression does not matter".
- vcxy 7y agoedflsafoiewq's answer is good, but they didn't really mention functors. If you want an umbrella to put functors under, I'd say "higher order structure". It's a map between structures that respects structure.
- ErotemeObelus 7y agoI want to talk about the three criteria necessary to have an algebraic structure: 1. It must be a type/class. 2. It must implement methods with a specific type signature. 3. It must obey laws. Criteria 1, 2 have an implementation in programming languages. But criterion 3 doesn't. You can't check whether the implementation of a Group abstract class satisfies the three group axioms like you can check whether they extend the Group class or whether they're implementing the wrong type signature. That means this is going back to Dijkstra's "proof of correctness" paradigm of programming which is a bad idea.
- haolez 7y agoI don’t have a need right now to master a new programming paradigm in order to leverage my business. However, if I happen to bump into this need, I’d focus first on Logic and Array-Oriented programming languages first. They seem more valuable to my industry (finance). For example: Prolog and J.
- carapace 7y agoI know it's not for everybody, but go back and read Backus' Turing Award lecture introducing FP: "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs" https://dl.acm.org/ft_gateway.cfm?id=1283933&type=pdf https://dl.acm.org/ft_gateway.cfm?id=1283933&type=pdf The two main points (they're in the title) are eliminating the "von Neumann bottleneck" between the CPU and RAM, and the algebra of [FP] programs, the potential to manipulate programs as one manipulates mathematical formulas.
- jandrese 7y agoI just skimmed that paper but I don't see a section on how to avoid the bottleneck when your functional program is trapped on a Von Neumann machine. It seems to me that functional constructs have to be mapped down to structures that will suffer the Von Newmann bottleneck if they are being executed on a Von Newmann machine. But there isn't any apparent discussion of an alternative machine architecture, just the computer language. Indeed one of the complaints you sometimes see about functional programming is the amount of memory churn it produces on a Von Newmann architecture.
- carapace 7y agoI'm actually working on that. I've come up with a way to dynamically create dataflow graphs on banks of hardware interconnected by latching sort-nets and programmed by a simple, pure, functional, "concatinative" programming language called Joy.
- jandrese 7y agoDidn't the MIT LISP machines achieve this back in the 80s?
- keithnz 7y agoyou may want to read this https://en.wikipedia.org/wiki/Function-level_programming https://en.wikipedia.org/wiki/Function-level_programming it's different
- pierrebai 7y agoYAGNI 99% of problems one encounters while programming can be solved in C++ with std::vector and functions taking a vector in and producing a vector out. That's my main problem with FP and many other language making bold claims: oversell. That simple fact is that for most computing tasks, you don't meed much more than simple types.
- ryanianian 7y agoC++ is not a purely functional language, but the type-system is (caveat WIP things like concepts). Even if all you're doing is "vector-in, vector-out", the types of those vectors matters immensely. This is especially true in languages like C++ where the type-system is very deep but also very hard to debug or change at varying levels of abstraction.
- talaketu 7y agoHeck, even a turing machine could solve most of these problems.
- herbstein 7y agoYeah.... You're probably right. Let's not talk about the meta-structures of our programs, but just use those structures. Sure. I might be using a monad and the bind function every single day, but acknowledging any useful repetition of patterns is never useful. That's why no successful programmer has ever even given a thought to design patterns. /s Why is it that people are alright with identifying and naming the pattern of a single global instance of a type - i.e. a singleton, but as soon as you identify a pattern of type signatures you're instantly thought of as looney and overselling?
- privethedge 7y ago> a.map(g).map(f) ≣ a.map(x => f(g(x))) > But the one on the left will be slower and use a lot more memory. Is it really true? I mean, GC will clean the intermediate array, won't it? And the speed won't be significantly slower. It's still linear complexity anyway.
- tomkwong 7y agoImagine that the size of the intermediate array is half of your computer's memory. It matters because by composition it reduces the memory footprint from 2x to 1x.
- privethedge 7y agoThen it is 8Gb of pointers. I doubt it's practical to worry about such extreme cases.
- tom_mellior 7y agoDragging a large data structure through the cache only once rather than twice can be beneficial. Also, GC will clean the intermediate array, but (depending on the specifics of the language and the data types involved) it might first have to make yet another scan through the data structure. So yes, it's linear, but possibly 2-3x slower.
- privethedge 7y agoThen why do I have the following results? const a = [...Array(1000000).keys()]; const m = 8; let leftAvg = .0; for(let _ of Array(m)) { const t0 = performance.now(); a.map(Math.tan).map(Math.sin); const t1 = performance.now(); leftAvg += (t1 - t0)/m; } let rightAvg = .0; for(let _ of Array(m)) { const t0 = performance.now(); a.map(x => Math.sin(Math.tan(x))); const t1 = performance.now(); rightAvg += (t1 - t0)/m; } console.log(leftAvg, rightAvg, leftAvg/rightAvg); // JS Firefox 70: 264 360.75 0.7318087318087318 var a = Enumerable.Range(0, 10000000).Select(x => (double)x).ToArray(); double[] xs1 = null; double[] xs2 = null; var m = 16; var leftAvg = .0; foreach (var _ in Enumerable.Range(0, m)) { var watch = System.Diagnostics.Stopwatch.StartNew(); xs1 = a.Select(Math.Tan).ToArray().Select(Math.Sin).ToArray(); watch.Stop(); leftAvg += (double)watch.ElapsedMilliseconds / m; } var rightAvg = .0; foreach (var _ in Enumerable.Range(0, m)) { var watch = System.Diagnostics.Stopwatch.StartNew(); xs2 = a.Select(x => Math.Sin(Math.Tan(x))).ToArray(); watch.Stop(); rightAvg += (double)watch.ElapsedMilliseconds / m; } Console.WriteLine($"{leftAvg} {rightAvg} {leftAvg / rightAvg}"); // C# Results: 505.75 602.25 0.839767538397675