Ask HN: How to be fluent in functional language speak?
When I read academic articles or blog posts written by functional programmers it feels alien to me because of the terms used in their writing. I am not just talking about monads, monoids etc, but the general programming terminology itself is different to what I regularly hear and read as imperative OO programmer. For e.g. this sentence "abstraction over type constructors"; whenever programmers from C++, Java etc world will read that they are sure to say, "eh?!?" and fall off their chair.
So how does a programmer from non-functional world become fluent in understanding sentence such as "abstraction over type constructors"?
111 comments
[ 2.8 ms ] story [ 67.4 ms ] threadIt’s been a while since I’ve dabbled with Haskell but I believe type constructors take a type and return a type (like List takes Int and returns List Int) so an abstraction over them might be an m where say m is a monad and it takes an a and gives you m a. m is an abstraction because it could be anything. A List, or Either, or State etc.
Ordinary constructors, which everyone here is familiar with, construct values. They may take some arguments, which are themselves values.
A type constructor constructs types. It may take some arguments, which are themselves types. List is a great example of a type constructor with one argument. `Bool` is a type, and arguably a type constructor with no arguments. `Either` is a type constructor with two arguments.
In C++, `Pair` is a type constructor with two arguments; although there are more constraints on how you can use it (or at least were last time I delved deep in C++).
An example of "abstraction over type constructors" would be something that lets you pass in a type constructor as an argument, giving different behavior (whether parametric or ad-hoc - sorry, more jargon...) depending on what you pick.
I think your best option is to directly contact authors or very good educators and ask them exactly what they mean.
Are you just trying to read academic articles and blog posts? Have you tried working in one or more of the languages? Beyond "toy problems" to trying to solve larger problems?
The more you work in a language, the more you might start to understand the needs that underlie things like category theory (the mathematics of monoids, semigroups, monads, etc) and where other higher level abstractions start to play in how you want/need to write software.
There's also places to practice even in C++, Java, etc. A lot of functional programming is making its way "stealth" into even the most imperative OO languages. Are you handy with your languages map/filter/reduce libraries around iterables? Have you tried pushing that deeper towards other monads such as query transformation (Linq) or time (async/await, ReactiveX)? Have you thought about how those work under the hood? (Explored what a iterable generator or an async/await decompile to?) Have you started yet to think in terms of high level "lambdas", places where functions themselves can be reused by other objects/functions? (Beyond "callbacks" towards thinking of functions themselves as lego bricks to build with.)
There's also middle ground languages such as F# or Clojure that you can use side-by-side (in some circumstances) C# or Java (respectively) code where maybe you can't work 100% in a functional language on a project, but you can get a compromise mix.
So much of understanding the "lingo" is recognizing the patterns and/or problems to which they refer, and a lot of the easiest way you will pick up patterns and see recurring patterns is practice.
I still remember "not getting" OO in university in my first lecture. I had programmed BASIC, C, Pascal, PHP before. And if someone would have tried to explain me the idea by means of the visitor pattern, it would surely have made me say "eh?!?" too. So allow yourself to start slowly.
I'm also still dabbling in functional programming - at least that's what it feels like reading about monoids etc - but by actually using functional programming languages in my more serious spare time projects I feel I get a better and better understanding. And "those" articles start to speak more to me.
Edit. For example, let's take 'catamorphism'. Read the Wikipedia entry [0] and it's a seemingly never ending jungle of more and more abstract terms. Homomorphism, initial algebra, F-algebra, endomporphism. This easy, let's see what an F-algebra is [1] and we'll be on our way soon. "If C is a category, and F: C → C is an endofunctor of C, then an F-algebra is a tuple (A, α), where A is an object of C and α is a C-morphism F(A) → A.". Oh my God, this is hopeless.
Or, find a good description, with examples [2]. A 'catamorphism' card, abbreviated from [2]:
Catamorphism
A function that “collapses” a recursive type into a new value based on its structure. Visitor pattern.
Define a sum type Gift:
Define a 'description' function over Gift: Parametrize the function, creating a 'catamorphism': Refactor your 'description' function to use a 'catamorphism': [0] https://en.wikipedia.org/wiki/Catamorphism[1] https://en.wikipedia.org/wiki/F-algebra
[2] https://fsharpforfunandprofit.com/posts/recursive-types-and-...
Still cool to know there's a name for it, but I wouldn't write in a code review "why don't you refactor your description function using a catamorphism".
Yup, category theory is often called "general abstract nonsense" precisely because it manages to talk about many disparate parts of math (or programming!) in a way that purposely avoids any reference to the specific. To usefully interpret the above, you specifically need to know that your domain often uses the category (C) of types (as objects) and functions (as morphisms), and that this category features certain generic types (such as Option, List, Array etc.) as endofunctors - and then literally plug all of those into the definition and work out the result.
It's exactly the difference between (in an elementary context) a word problem, vs. the general theory of equations of type foo which could be used to solve any number of word problems - except replicated at a higher level.
Perhaps the world lacks CT for dummies. Teach it in primary school. New Math was not aggressive enough ;)
You will find that your fluency in almost any subject is improved with this practice.
A constructor can be viewed as a function that takes values for the fields of a datatype and gives a value of the datatype in return. Not all functions are constructors, but some are.
At the type level, if we squint a little, "Maybe" or "List" behave a bit like constructors. They take types like "Int" or "Bool" as parameters, and give types like "Maybe Int" and "List Bool" in return. Not all type-level "functions" are type constructors (for example, in Haskell type families are not type constructors) but some are.
It's really hard to explain "abstraction over type constructors" in a pithy manner despite being a relatively simple statement because the obvious follow-up is "but why?" And the answer to that question isn't going to satisfy you without an understanding of the functional programming environment.
It's exactly like when novice programmers get thrown into Java land in CS101 and you have to tell the to just ignore the whole class, public, private, static, etc jargon. They need to gain experience programming in that environment to really appreciate those concepts.
"abstraction over type constructors" might have to do with typing and not related to functional programming.
The hardcore “sound types” crowd believes that anybody using dynamic types is doomed.
I must not have the same problems they do.
First class functions; closures; higher order functions; partial function application, seasoned with the occasional variadic vs fixed arity function, and I’m good.
One can learn the other 95% of the jargon to deal with 5% of the problems later.
What they believe is that "dynamic types" is a misnomer, and if you think your program is checking dynamic types, it is in fact doing runtime pattern matching over a variant record. There's nothing wrong with pattern matching and variant records; but conflating them with types is just nutty, and using them pervasively as part of the ordinary flow of code is no different than programming in old-style VB.
For the record I am a convert. Types have made my developer life much happier, especially working with unfamiliar code across multiple projects/teams. When you treat your builds as long term proofs your confidence level increases dramatically.
Though on first glance, doesn't it suggest that all programming features are good, and only their absence is bad? St. Exupéry's idea of perfection would disagree.
For example, the Lisp people are sure they're looking down when they look at Haskell - no macros. But the Haskell people are also sure they're looking down when they look at Lisp - no decent type system. But if they're both looking down at the other, that's kind of a problem for the Blub Paradox.
Here's the other problem with it: I don't care about "power" in languages in any platonic sense; I care about power to write the specific program I'm trying to write. That includes the language's expressiveness, sure, but it also includes available libraries and the rest of the ecosystem, tutorials if there's parts I have to learn, the ability to find others who are proficient if the program is big enough to need a team, and so on. The power to write my specific program depends on the problem, not just on the language.
Lot of webdev stuff is moving to functional paradigms. Lazy evaluation, streams/iterator pattern combined with map/reduce/filter (FRP). You can pick out any modern ui framework and you would be drowning in fp soon enough.
Many attempts at building a functional language for web - purescript, elm, reasonml etc.
non-abstracted:
abstracted: "List" is a type constructor (it takes a type and returns a type), but we can write a "map" function that works over more types than just List - for example, Maps and Options and so on (aka "Functors" in Haskell parlance). We've "abstracted (the function map) over the type constructor (of the data structure being mapped over)".To answer your more general question, if you just learn functional programming on a language with a powerful type system (Haskell is probably the most germane example) you will learn at least some of these terms. Most of them turn out not to be very deep, just hard to explain (for reasons unclear to those who understand them), but still very useful.
Then why didn't they just call those types "Mappables"?
What do you call the following common operations?
As far as I know there is no term for this grouping of operations outside of functional programming languages which use category theory.We call it a "monoid" based on the following precise definition:
> In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element[1].
I used the "identity element" specifically in my examples above since they tend to be a good way to grasp what is going on.
It turns out a "functor" has more properties than just being "mappable", which is why we like using the more precise term in our literature. However, it's still a decent intuition if you aren't familiar with the concept.
For example, in the parent comment the 'f' in the second line of code shows that it is some kind of structure that adheres to a Functor, and also infers that this structure can also be mapped over. This is a nice property because without caring about the implementation, we can still do functor-specific operations over abstract structures.
[1] https://en.wikipedia.org/wiki/Monoid
I think the point GP was making is that a monoid has something to do with a function f that takes two arguments a and b where there is a single value for b such that f(a, special_value) == a. I think.
As someone who doesn't really understand FP concepts I would probably call those functions "functions that can sensibly be used in a call to array.reduce"
+: concat marbles sequence
* : concat prime factors sequence
++: concat box sequence
For * , it can also be reduced to + via logarithms. I just don't have a good metaphor for '+ over reals' this morning.
Skimming through my thesaurus, I found a word for it: "Totalize".
Given that this is a thread on functional jargon, it might be interesting to note list metaphors as being useful for thinking about monoid might derive from lists being free monoids (in many contexts). This means that all functions from a collection elements to a monoid can be thought of as functions from that collection into a list with the appropriate type of elements and then a fold (also called a reduction) over that list. This knowledge can be super useful for thinking about program structure e.g. conceptually mapreduce is a general tool for large-scale distributed computation over monoids.
*it’s actually called “mappend”[0], short for monoid append, but I think the point still stands (and there is, in fact, a function called “mconcat”[1] but folds of a list of monoidal values using “mappend” to combine them.)
[0] http://hackage.haskell.org/package/base-4.14.0.0/docs/Data-M...
[1] http://hackage.haskell.org/package/base-4.14.0.0/docs/Data-M...
So reduceables?
That said, I am on the "name abstractions after the math" side of things. It makes it much clearer what guarantees I have when working with the interface, on either side of it.
You can use any function you want in a fold in Haskell. You're conflating two typeclasses, Monoids and Foldables, and restricting yourself to the function known in Haskell as foldMap.
"associative": (a + b) + c == a + (b + c)
"binary": f a b == a `f` b == a + b where f is addition
"identity element": the "empty" value which when paired with a second value, returns the second value as is
Though now that FP concepts are mainstream, I think there is a good case to offer some friendlier, more familiar names:
Functor -> Mappable
Applicative -> Pairable
Monad -> Thenable
[0]: https://softwareengineering.stackexchange.com/questions/2033...
I've been writing Haskell for over 5 years and to this day when I see <$>, <*>, >>= in my code I don't substitute English words for them.
mentalModel.update().
The query `python @` fails pretty hard though.
Citation needed
Calling Functor "Mappable" and Monad "Thenable" doesn't really add much to understanding.
The best advice I ever got was that a Functor is `f` with a function `fmap :: (a -> b) -> f a -> f b` that follows its laws. Same goes for Monad. If it has the type signature & follows the laws, it's a Monad. That's the definition. No need for a cute analogy-oriented name like FlatMap-able or Then-able.
Once you do that, you realize that the way to understand these things is to play type tetris with highly-generic type signatures. You stop needing English/real-world analogies to understand them and instead use the type system to understand the world (the reverse of using "nice" names)
It works really well but it is a steep hill to climb. It helps to talk to others who have climbed it, and it helps to just grind on a project and use Monads without being an expert. You can go a long way just knowing how `do`, `traverse`/`mapM`, etc work and not having big Monad intuition.
Citation needed.
“Functor,” points to a specific concept in Haskell and a slightly different one in Category Theory but otherwise it is fairly unambiguous given enough context. The concept not only refers to the type and the associated “map” operation but also the axioms of identity and composition and their properties.
“Mappable,” is a very common name people pick in these discussions but it doesn’t clarify the meaning any more than calling it “Rose.” It may in fact cause more harm than good if a name like Mappable exists in more contexts. There are plenty of objects one can apply a map operation to that are not valid Functors.
> The short form was really adopted as a mischievous pun on the use of "functor" in the OOP community.
Citation needed.
I just have never heard that allegation about `functor`, which seems to have been taken directly from mathematics that predate any notion of function object. It's possible that OO programmers and the mathematicians both borrowed it from the same source (it seems to have originated in linguistics).
That's been debated in philosophy for over 150 years, and there are many alternative theories.
I think a better point is that technical names don't matter because their formal meaning may not correspond with any word, and if there is an everyday word, it's probably slightly but importantly different.
Is there also a risk with FP too that people fall a little too much in love with “elegant” code only to find out later that maybe simpler is better? Reading some people writing about FP I feel there is some risk of people doing this.
When you could have written it yourself with one or two extra lines. Why? Is it simpler? Or is it unnecessarily abstracted?
2. It's harder to understand. "Why didn't this use the standard library function? Is it doing something different? It doesn't look like it, am I missing something?"
I know some functional programmers who write complex code because they want to use the latest features of the type system. They get additional type safety, or better code factorization, but it results in code that is very hard to read and maintain, especially for people not as skilled as the initial programmer.
Jumping on all the shiny-new-feature bandwagons that makes code drift towards unnecessary complexity, even if it technically makes things "better" given some sort of objective context, is something a team working with these languages really needs to consider.
For example:
The type is 'answer'. The constructors are Yes, No, and Maybe (these are actually called type variants but now we're getting into jargon). I presume an 'abstraction over type constructors' means you want to generalize that type, so you can use the constructors to produce an abstract type that works with any type but I've never heard that specific term.In most languages, however, that's not a construct you can do much of anything with.
You can start with the basic concepts and eventually build your way up to more abstract constructs when you realize you need them. But even there, you don't need to know the academic terminology (or if you do, it'll make more sense when you get familiar with the language).
I frequently use monads and functors, yet I don't know much about category theory (and the little I know doesn't make me a better programmer).
You also said that their use of "functor" was probably the result of being French vs English, when I pointed out that in fact it came from Standard ML, which is a British design. Moreover, the creators of Haskell originally built typeclasses as an extension to Standard ML (1980s), and Functor was added in the same version of Haskell that Monad was (1.3, roughly 1998).
The connection between ML functors (specifically the interface/signature) and typeclasses in Haskell is relatively clear, if you understand how they both work. I don't disagree that typeclasses are more general, but modules have their appeal as well. I'm pretty excited to see where Backpack ends up in Haskell, personally.
> OCaml's type system is not powerful/expressive enough that (to use the given example) abstracting over type constructors is likely to ever come up.
And I stand by that. It’s not likely to ever come up, even if it’s possible to kludge it.
You’re right about the name though - it seems like the anomalous use of “functor” predates francophone intervention.
What you said is that it's not powerful or expressive enough, but my impression was that they were both expressible in terms of System Fω, an understanding I would like to correct if it's wrong.
Eilenberg and Lane introduced functors (in the sense more or less used by Haskell) in the 40s.
> my impression was that they were both expressible in terms of System Fω
This is not correct anymore - Fω is insufficient to describe GADTs. You need coercions and equality constraints as well.
It's also approximately as useful a claim as "the languages are equally powerful because they're both Turing complete".
I'm referring to practicability, not theoretical possibility (and I've clarified as much several times now).
Yes.
>This is not correct anymore - Fω is insufficient to describe GADTs. You need coercions and equality constraints as well.
Of course, OCaml has GADTs these days. I suppose neither of them are really Fω anymore, then.
>It's also approximately as useful a claim as "the languages are equally powerful because they're both Turing complete".
Agree to disagree. I think when discussing how powerful a language is, a rigorous notion like Turing completeness or position on the lambda cube is still significant, even if it's not the most immediately visible.
>I'm referring to practicability, not theoretical possibility (and I've clarified as much several times now).
Fair enough, I'll chalk this up to a misunderstanding.
It's, in my opinion, better to just grab a functional language, built some software with it, and learn about the benefits and disadvantages of functional languages by interacting with them.
It did not help much.
https://fsharpforfunandprofit.com/fppatterns/
Then:
https://fsharpforfunandprofit.com/rop/
Then if wanna go round:
https://fsharpforfunandprofit.com/series/thinking-functional...
Ok, almost all that site. is truly good.
Incoming essay...
Pure functional programming is fundamentally about software components called "pure functions", or just "functions" for short. (I'm quoting the term because they're not the same as what are called functions in other languages. I'd call those other things "procedures" instead, but alas.) Other programming communities rally around components like "objects", and that's fine. The important thing is to pick something to break your system down into, and here, we're talking about "functions".
"Functions" are simpler kinds of components than objects or procedures: the ways in which they behave are much more limited, so they're easier to reason about. When a "function" is interacted with, it can't perform any side effects, so interacting with the "function" multiple times gives the same behavior every time. Procedures can manipulate global state, and objects can manipulate internal state, so reasoning about them takes more effort. You have to keep track of time: what happened before this interaction?
"Functions" have two interfaces: an input side and an output side. When a "function" receives a value on the input side, it will always emit a value on the output side. We can wire "functions" together by connecting the input of one to the output of another. The result is a system with a single free input side and a single free output side -- that is, it's also a "function". This makes it very easy to wire up lots of "functions".
Usually, a "function" has certain expectations of the input values that it receives, as well as some guarantees about the output values it emits. In a dynamically typed language, when those expectations are not met, a runtime error is emitted. This is fine -- it's just one way to handle failed expectations. But sometimes we can formalize those expectations statically, and let the compiler check up-front whether those expectations are met. This does add some complexity: you might not be able to wire up two "functions" if one can't satisfy the other's expectations. Statically-typed programmers have decided that they're willing to put up with that.
In a statically-typed world, the input and output interfaces of our "function" software components can be tagged with specifications. Functional languages are often judged by how expressive these specifications can be; a specification language like this is called a "type system". You can have type systems for components that are not "functions", but the rules of composition become more complex. (For "objects", class systems are quite popular.)
Most type systems allow you to break down an interface specification into smaller pieces, which themselves are valid specifications. That means we now have two kinds of components in our system: "functions", which exist at runtime, and types, which exist at compilation time. The rules for how types compose can be more complicated than those for "functions", but we're usually okay with that, as long as "functions" are kept simple.
Some type systems allow a value to satisfy multiple types. For example, class-based systems allow this via subtyping relations. Others might describe types as predicates (truth functions) on a pre-existing universe of values (e.g. TypeScript). Pure functional programming typically requires mutual exclusion: a value cannot be part of multiple types. We often say the the type defines its values because of this.
The low bar for a static type system is "algebraic types". This means that we have two ways to compose types, conventionally called "product" and "sum". Most type systems have products, but sum...
One thing I've noticed working in Haskell: Everyone is an expert in different things. Very rarely do I meet a Haskeller whose knowledge or interests subsumes another. That's part of the fun. Everybody doesn't know some terms!
Learning through games like this is a big help because they provide: 1. clear and approachable goals 2. clear feedback on whether you've achieved the goals
Maybe Clojure isn't what you're looking for but maybe there's a similar service for a language you'd like to learn.
https://racket-lang.org/