Thank you!

[i-am-tom]

Hey,

John De Goes tweeted about being grateful to OSS contributors, so I thought it'd be a cool thing to do. You're why I got into functional programming, why I get to go to talks and preach the ways of PureScript/Haskell, and, between you and @joneshf, why I'm getting way too excited about category theory. I've emailed you before, and you replied to that, which was really great of you, too.

I put this on this one because I've been trying to pay attention to that talk you mentioned on denotational design, and I came looking for your F-algebra example. I guess I hoped it would stand out a bit more, too, and not make you feel like you had another problem to deal with :)

[stevemao]

I still don't understand the definition of Corecursion, Transducers, F-Algebras and all the morphism jargons appearing in the notes. I have watched the video and read the slides a few times but couldn't find the definition. The definitions on the internet is not easily understood by javascript developers. @i-am-tom Would you please write them up here? Thanks a lot!

[i-am-tom]

@stevemao I can certainly try, + hope @DrBoolean doesn't mind me using his issues space as a note pad! Warning: skip to the end when this stuff gets too dense to interpret.

Corecursion

The dual of recursion. With recursion, we can do things like reduce - take a group of things and combine them into one. For example:

const sum = xs => xs.reduce((acc, x) => acc + x, 0)

sum([1, 2, 3, 4, 5]) // 15

We started with a group of things (the five numbers) and ended up with one thing (15). That "one thing" can be anything - even another array! - but the point is that we combine a group of things. With corecursion, we start with the one thing and build the group:

const countDown = n => n > 0 ? [n, ... countDown(n - 1)] : []

countDown(5) // [5, 4, 3, 2, 1]

We started with one thing (5) and ended up with a group of things (the five numbers). See that it's exactly the opposite concept! In the most general form, we tend to express recursion and corecursion with things similar to fold (which JS calls reduce) and unfold respectively. The code for this talk gives an implementation of unfold, which we can use to rewrite our function above:

const countDown = n => unfold(function (n) {
  return n <= 0 ? undefined : [n, n - 1]
}, n)

Bonus: when Brian makes mention of a hylomorphism, that's an unfold followed by fold! We could use the above two examples to write a hylo to add up all the numbers up to a certain point:

const sumUntil = max => hylo(sum, countDown, max)

sumUntil(5) // 15!

• Recursion combines (folds) a group of values into a single value.
• Corecursion generates (unfolds) a group of values from a single value.

They're opposites :)

Transducers

The most fully-formed introductory explanation I've seen of these is in @getify's book in the first appendix. I would work through that chapter and see if that helps you. If not, get in touch, and we'll go through it together :)

F-Algebra

You can really just think of this as a term meaning, "thing that we can reduce", and you'll be on the right track. Strictly speaking, the F relates to some container type (array, tree, whatever) that holds some values of type a, and can be "reduced" to a single value of type a. f a -> a. That's all it is.

We can get much fancier by using a Fix structure, but I would recommend getting comfortable with other concepts like co-recursion first, as this is a bit intense, and not something you'll have to worry about. In a nutshell, we can think of this a bit like "factoring out recursion". I do think Brian's talk is as clear as you can make these advanced cases without just playing with them in the wild, but we'll talk about the morphism stuff in a minute and that should help!

For me, the post that cemented by understanding was Understanding F-Algebras by @BartoszMilewski. Of course, the examples are written in Haskell, but I'd be happy to translate the examples into JS if it hasn't already been done somewhere. As I say, though, I'd work through the first two points you mentioned, and come back to this later on. You can achieve everything an F-algebra does without using one - they just make for some really elegant code :)

Morphism Jargon

According to Wikipedia,

In many fields of mathematics, morphism refers to a structure-preserving map from one mathematical structure to another.

Soooo, you can basically read morphisms as a way of turning things of one type into things of another. That's all. Morphisms are, well, functions. However, as you pointed out, there are quite a few something-morphisms in the notes, so let's look at a bunch of them.

Catamorphism: it's a fancy word for reduce (well, technically reduceRight)! We did this back in the first part with sum. Take a bunch of things, and combine them into another. The morphism is from "bunch of things" to "another".

Anamorphism: it's a fancy word for unfold! countDown is an anamorphism. Anamorphisms are morphisms from "another" to "bunch of things", to flip the previous example.

Hylomorphism: the combination of anamorphism and catamorphism!

Isomorphism: a relationship between two types of thing that is losslessly reversible. Consider String and [Char]: "hello".split('').join('') === "hello". In fact, you can replace "hello" with any string and this will be true, because split and join form an isomorphism between those two types.

These are all written out in super general terms in the (perhaps appropriately-named?) Pointless.RecursionPatterns package in case you want some further reading and links to a lot of papers. To spare you, though, we'll go through the other two that got a mention:

Paramorphism: it's like reduceRight. However, there's a difference:

• In reduceRight, your reducer's arguments are the current value and the reduction of all previous values.
• In para, your reducer's arguments are the current value, the reduction of all previous values, and the list of values that formed that reduction.

As with a lot of things, @pigworker gave a great explanation of why it's useful (again, in Haskell). Pay particular attention to the suff example, though:

// Obviously not safe for lists containing `undefined`,
// but good enough to make the point.
const para = (reducer, accumulator, [x, ... xs]) =>
  x !== undefined
  ? reducer(x, xs, para(reducer, accumulator, xs))
  : accumulator

const suffixes = list => para(
  (x, xs, suffxs) => [xs, ... suffxs],
  [],
  list
)

suffixes([1, 2, 3, 4, 5]) // [[2, 3, 4, 5], [3, 4, 5], [4, 5], [5], []]

I like this example because we're folding an array into an array of arrays. It goes to show that the folded type can be anything!

In the reducer for suffixes, we get x (the "next item to reduce", which we're ignoring), xs (the items consumed so far), and suffxs (what we'd call acc in a normal reduce). The magic here is that xs - the last step's reduction - is the suffix we want (because, last time, we ignored the head, and this time, we want to use it). Might take a couple of readthroughs, sorry. In essence, para is kind of like having a history of what got you to your current acc value.

Apomorphism: it's the opposite of para, just as ana is the opposite of cata. Whereas with para, you combine with access to the accumulator and what has been accumulated, apo lets you unfold with the potential to return early. This is cool because it answers the oft-asked question of "how do I early-abort reduce?" However, it's super frightening to a beginner, and I've been getting along just fine without really understanding it, so absolutely do not worry about it. Seriously. It's not something you need in JavaScript as we have other machinery for accomplishing the same thing.

---

Sorry, I got super carried away. I hope that's useful in some way - I know it gets progressively more complicated, but it also gets progressively less necessary for writing everyday functional code. Corecursion and transducers are useful in ways that are obvious almost immediately. F-algebra promotes really neat ways of doing recursion, as long as your entire team understands what they do. Morphisms are wonderful mathematical ideas, but, at my day job, I'd fail you on code review if I saw apo anywhere in your code. These really aren't topics you want to use in practice unless your surrounding coworkers are equally enthusiastic...

And, of course, no one knows all this stuff. Everyone has foggy areas. I myself have been trying to get through a recursion scheme article for days now, with very limited success. Keep re-reading, keep trying things out, and keep asking questions. If nothing else, it's great practice for others to have to explain their understanding!

[DrBoolean]

Great explanations @i-am-tom!

I should mention there is a JS port of some of these concepts from matryoshka and Haskell's recursion scheme lib here: https://github.com/DrBoolean/excursion

These are extremely powerful concepts that can capture any explicit recursion with composable pieces, but still needs a lot of optimization in JS

[i-am-tom]

Thanks, @DrBoolean! When I'm not busy with Fantasy Land, I'd love to sit down and have a go at coming up with a set of really practical, well-documented examples of each of the schemes in your matryoshka port. Would be great to get it out of the inner circle of academia 🙃

[stevemao]

Thanks for the detailed explanation @i-am-tom (I've been reading it many times now still trying to get my head around it 😄 ). I'm planing to add these to https://github.com/hemanth/functional-programming-jargon. There's limited good functional programming resources we can find in js world even people talking about react and redux all the time. I really hope to improve this in the community :)

[i-am-tom]

Awesome! I think we're all on the same mission, hah. If there's anything I can better explain in the above post, do let me know!

[stevemao]

@i-am-tom I don't know how you can early-abort reduce in Apomorphism. Looking at the implementation of Paramorphism

// Obviously not safe for lists containing `undefined`,
// but good enough to make the point.
const para = (reducer, accumulator, [x, ... xs]) =>
  x !== undefined

In the x !== undefined bit, if the last accumulation is undefined, does it early abort? Or it's just your simplified implementation?

[i-am-tom]

Ah. para isn't early-abort. The undefined bit was because, in reality, you'd do a proper check to see that the list was empty. This is a much more respectable implementation:

const para = (reducer, accumulator, elements) => {
  if (elements.length === 0)
    return accumulator

  const head = elements[0]
  const tail = elements.slice(1)

  return reducer(head, tail, para(reducer, accumulator, tail))
}

I was just being lazy :flushed:

---

To see why Apomorphism, we need to write a slightly more formal Anamorphism. To spare us all the recursion scheme boilerplate, we'll just use the basic one from unfoldr:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

So, we can, at any stage, return Nothing to indicate that we're done with unfolding. However, sometimes, we might be able to speed up the unfold if we already know the rest. The example in the article I quoted of list concat was a great one: if we have a Nil first list, we can early-abort because we know the rest of the unfold already - it's the second list! With that in mind, your type signature for a very simple apomorphism could probably look something like this:

simpleApo :: (b -> Either [a] (a, b)) -> b -> [a]

I want to spend a bit more time writing up an example once my Fantasy Land posts are done, but this should be enough intuition for now.

tl;dr "Early abort" in the context of unfolds might seem odd, because "abort" is the end of the unfold, so it's not really early. However, what it means is that, if we have access to exactly what the rest of the fold is going to be, we can say "actually just use this instead" and not loop through it. Hence, "early" abort :)

[salientknight]

I got here from a conversation about not using IF/ELSE and instead using a catamorphism. If/else is usually the fastest construct in any language, and has short cutting. What practical advantage is there for using catamorphism?

[stevemao]

I got here from a conversation about not using IF/ELSE and instead using a catamorphism.

I'm not sure if I understand you correctly but a sum type (union type) is usually used to replace if/else. You can use a sum type to pattern match different scenarios to branch your code while you can still compose everything.

[a-laughlin]

I should mention there is a JS port of some of these concepts from matryoshka and Haskell's recursion scheme lib here: https://github.com/DrBoolean/excursion

These are extremely powerful concepts that can capture any explicit recursion with composable pieces, but still needs a lot of optimization in JS

@DrBoolean I love the recursion scheme concepts and appreciate your example in excursion. Thanks for making that and linking it here! A few questions:

The repo mentions "in progress" circa 2016. Are you aware of any efforts to reach a production-worthy version since since your work? The closest I've found are excursion and static-land-recursion-schemes. Both seem to have stalled at the experiment stage. That raises my second question.

You state the concepts need optimization in JS. Does that imply engine-level or library-level optimizations? My (hopefully incorrect) guess is engine-level considering the power of recursion schemes and seeming lack of mature libs.

Assuming that engine level optimizations are needed to make recursion scheme libs performant in JS, what alternatives do you use to fold/unfold multi-level algebraic data types in day-to-day work?Transducers?

[DrBoolean]

Hi Adam,

Yeah, your observation is correct, the work as far as I'm aware, hasn't progressed much (we need a JS hero).

It's a shame because DOM recursions seem like a prime application.

My optimization comment was more toward implementing these concept with imperative loops under the hood or trampolining. Scala functional folks have really shown a great way to do these things.

I'm currently investigating capabilities, benefits and drawbacks of trying to do this stuff with lenses.

To me the major drawback is having to convert from [] to List and awkward functor instances. The functor instances might be fixable (no pun intended) with bifunctors or extra type wrappers, but i don't see a way around conversions

[a-laughlin]

Thanks for the quick response Brian.

Understood on loops/trampolining. Thanks for clarifying.

To me the major drawback is having to convert from [] to List and awkward functor instances.

The drawback of lenses specifically? Or all conversions of arrays to, if I understand correctly, head-tail accommodating shapes like Cons(1, Cons(2, Cons(3, Empty))) or Node(Leaf(),Leaf())?

I'm currently investigating capabilities, benefits and drawbacks of trying to do this stuff with lenses.

It sounds like we're both exploring that direction. This February I'm implementing the GraphQL spec as a FP learning project. The various AST shapes yield many different (sub)tree shapes to traverse and transform. My original plan was to use lenses and transducers until discovering recursion schemes. Now it's back to lenses.

Since we're both exploring lens-based recursion schemes, would you be interested in coordinating exploration for a month? Details flexible. One option could be fleshing out approaches together, then I can apply them to the GraphQL project's cases and document pros/cons as they arise. Depending on how quick it goes, there may be time left over for imperative optimization.

[DrBoolean]

Just to make sure “the drawback of recursion schemes” is that it requires fixed point data structures like the cons list, however, lenses can address this.

I’d love to be able to join forces with you, but I’m currently having a hard time balancing life and my day job. Hopefully, I’ll get more free time soon, but as of now I’m spent :(

That project sounds sweet though!

On Jan 27, 2020, at 6:08 PM, Adam Laughlin notifications@github.com wrote:

Thanks for the quick response Brian.

Understood on loops/trampolining. Thanks for clarifying.

To me the major drawback is having to convert from [] to List and awkward functor instances.

The drawback of lenses specifically, or all conversions of arrays to (if I understand correctly), head-tail accommodating shapes like Cons(1, Cons(2, Cons(3, Empty))) or `Node(Leaf(),Leaf())?

I'm currently investigating capabilities, benefits and drawbacks of trying to do this stuff with lenses.

It sounds like we're both exploring that direction. This February I'm implementing the GraphQL spec as a FP learning project. The various AST shapes yield many different (sub)tree shapes to traverse and transform. My original plan was to use lenses and transducers until discovering recursion schemes. Now it's back to lenses.

Since we're both exploring lens-based recursion schemes, would you be interested in coordinating exploration for a month? Details flexible. One option could be fleshing out approaches together, then I can apply them to the GraphQL project's cases and document pros/cons as they arise. Depending on how quick it goes, there may be time left over for imperative optimization.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/DrBoolean/RecursionTalk/issues/2?email_source=notifications&email_token=AAAG7EV52ICQ3VPKJLVSTXDQ76HRLA5CNFSM4CXP4CO2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKBYTAI#issuecomment-579045761, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAG7ETDYTDKS3ZNAIBUKOTQ76HRLANCNFSM4CXP4COQ.