FP Terminology

Some difficult FP terms that I've been trying to learn from my time on Gitter.

Miscellaneous Terminology

Terminology	Code
Getter	A => B
Isomorphism	A => B B => A
Prism for A	A => Option[B] B => A
Monads (roughly)	A => F[A] and F[F[A]] => F[A]
Comonads (roughly)	F[A] => A and F[A] => F[F[A]]
Endofunction	A => A
a * (b + c) = a * b + a * c (Distributive)	(A, M[B, C]) => M[(A, B), (A, C)]

Tagless Final

"So, final tagless is a broader term, which is now getting used in a more specific meaning increasingly often. 

Generally speaking final tagless is a technique for encoding DSLs. 

These days, often it's used to mean "a final tagless encoding of an effectful algebra", like a DB or something. 

Anyway the general idea is simple: 

trait KVS[F[_]] { 

   def put(k: String, v: String): F[Unit] 

   def get(k: String): F[Option[String]] 

} 

F will be replaced by a concrete type like cats.effect.IO, or Kleisli[IO, DbConnection, ?] 

That's the gist of it really" - Fabio Labella @SystemFw Mar 01 2018 12:38 (Gitter)

"What mtl is now is a final tagless encoding of common effects : like state, reading from an environment, and so on." (Reddit)

It superficially looks like the old fashioned Java-like interface with the only new interesting thing being the methods return F[_]. However, this is a big deal. That F[_] could be a plain old type (using type Id[T] = T) or it could be something non-synchronous like a Future. Therein lies the magic. The same interface for both synchronous and non-synchronous calls, for example.

zygfryd @zygfryd
I don't get it, I thought tagless was a pattern for working with lifted side effects, while code generation doesn't need side effects, and the target language has no facilities for lifting anything
Anthony Cerruti @srnb_gitlab 
Tagless was for DSLs I thought
Rob Norris @tpolecat 
It’s a programming style for abstracting over effects.
It has nothing directly to do with side-effects.
(It’s more general than abstracting over effects but that’s the common case.)

It's much simpler than it at first appears.

Rob Norris @tpolecat
You can think of Jokes[F[_]] as a service interface [in Http4s]. It’s a interface for something that knows how to tell jokes. The interesting bit is that joke-telling happens “in” F which is your effect type. If F is Option then joke-telling might fall. If it’s Either[String, ?] then joke-telling may fail with an explanation. If it’s IO then joke-telling might involve reading from disk or taking to the network. When you construct an instance you know what F is. But when you use it you typically leave F abstract so your code may be able to work for many choices of F. Constraints in user code like F[_]: Monad allow you to restrict the abstract F to only those effects that provide operations you need.

PhillHenry @PhillHenry
@tpolecat Is that tagless final? Or is that something completely different?
Rob Norris @tpolecat
Yes, that’s tagless style. Also called MTL style.

John de Goes has an excellent article on the advantages of tagless-final here including a particularly useful section on its advantages in testing (and some caveats).


What is an FP algebra?

"An algebra is a set of constructors for some data type plus rules for composing them. In tagless style (typical usage, it's more general than this) we have a trait like 

Foo[F[_]] { def blah(...): F[Bar] ; ... } 

that is parameterized on some effect F and provides methods for constructing values in F. The rules of composition are orthogonal and are determined by constraints you place on F later; i.e., 

def doSomething[F[_]: Monad](..., foo: Foo[F]): F[Something]."

Rob Norris @tpolecat Mar 24 18:48 

What are exceptions in an FP algebra?

"I would define it this way:
an error is something that makes a flatMap/mapN short-circuit
or more precisely, an e such that raiseError(e).flatMap(f) == raiseError(e)" - Fabio Labella @SystemFw Feb 26 22:21 

Referential Transparency

"Referential transparency talks about the equivalence of two expressions under a syntactic transformation types aren't mentioned anywhere in fact, you don't need types for it (although typically pure languages are also typed)
...
In general, it's a bit more gradual than this: there is a spectrum of information you can have expressed in a type but it's not always "more is better", there is a curve
...
A type system is a tractable syntactic method for statically proving the absence of certain program behaviour by classifying sentences according to the kind of values they compute that's a formal definition from Types and Programming Languages (off the top of my head so it might be a bit off here and there)
...
It's fairly easy to end up in a situation where too much info in types gives you a fragile mess Finite State Machines with IndexedStateT vs Ref + an ADT being a prime example" - Fabio Labella @SystemFw Feb 26 22:47

Effects vs Side effects

"An effect is a computational context like partiality or nondeterminism or exception handling or dependency injection.

A side-effect is a syntactic property, namely the absence of referential transparency, which means the inability to inline or factor out an expression while leaving your program’s behavior unchanged." - Rob Norris @tpolecat 02:42

Concurrency and Synchronization

Oleg Pyzhcov @oleg-py 06:41
@blitzkr1eg if you have two threads doing update at the same time, one will always see results of another (not the case with var, for instance, where both can see old state) - that's safe concurrent modification. However, you can't enforce ordering of those operations with Ref alone - that's lack of synchronization.

Equality

Rob Norris @tpolecat Jun 08 15:17
oh in that case we want it a == b to not compile for mutable things
so that's what cats.Eq gives you. a === b won't compile for mutable things
the deal is that if a === b you should be able to freely substitute a with b and vice-versa. Which you can't do with mutable things