New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Thank you! #2
Comments
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! |
@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. CorecursionThe dual of recursion. With recursion, we can do things like 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 ( const countDown = n => n > 0 ? [n, ... countDown(n - 1)] : []
countDown(5) // [5, 4, 3, 2, 1] We started with one thing ( 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 const sumUntil = max => hylo(sum, countDown, max)
sumUntil(5) // 15!
They're opposites :) TransducersThe 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-AlgebraYou can really just think of this as a term meaning, "thing that we can We can get much fancier by using a 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 JargonAccording to Wikipedia,
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 Anamorphism: it's a fancy word for Hylomorphism: the combination of anamorphism and catamorphism! Isomorphism: a relationship between two types of thing that is losslessly reversible. Consider 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
As with a lot of things, @pigworker gave a great explanation of why it's useful (again, in Haskell). Pay particular attention to the // 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], []]
In the reducer for Apomorphism: it's the opposite of 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 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! |
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 |
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 🙃 |
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 :) |
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! |
@i-am-tom I don't know how you can early-abort reduce in // Obviously not safe for lists containing `undefined`,
// but good enough to make the point.
const para = (reducer, accumulator, [x, ... xs]) =>
x !== undefined In the |
I was watching @DrBoolean's [A Million Ways to Fold in JS](https://www.youtube.com/watch?v=JZSoPZUoR58) but I couldn't understand most of the morphism jargons. I presume the video is for experienced devs who are from a FP language background. The moment when I tried to search for "Catamorphism javascript" on google I couldn't get anything. I really hope there would be more in depth FP resources written in JavaScript. Luckily @i-am-tom kindly wrote up something that could be understood by JS devs like me. I have fixed a minor mistake in @i-am-tom's [original write up](DrBoolean/RecursionTalk#2 (comment)) and tweaked a few wording. Also cc @joneshf @getify @shineli1984 Thanks!
Ah. 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 😳 To see why unfoldr :: (b -> Maybe (a, b)) -> b -> [a] So, we can, at any stage, return 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 :) |
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? |
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. |
@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? |
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 |
Thanks for the quick response Brian. Understood on loops/trampolining. Thanks for clarifying.
The drawback of lenses specifically? Or all conversions of arrays to, if I understand correctly, head-tail accommodating shapes like
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. |
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 ***@***.***> 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 <#2?email_source=notifications&email_token=AAAG7EV52ICQ3VPKJLVSTXDQ76HRLA5CNFSM4CXP4CO2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKBYTAI#issuecomment-579045761>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAG7ETDYTDKS3ZNAIBUKOTQ76HRLANCNFSM4CXP4COQ>.
|
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 :)
The text was updated successfully, but these errors were encountered: