JavaScript-algorithms: Algorithms and data structures implemented in JavaScript(github.com)
github.com
JavaScript-algorithms: Algorithms and data structures implemented in JavaScript
https://github.com/trekhleb/javascript-algorithms
80 comments
> I tend to think of Javascript as the language that fulfills the promises that BASIC never did
I taught myself BASIC when I was 7 when I didn't know what a programming language was.
I've been programming JS for 25 years and I still commonly can't predict what the behavior of some aspects of my code is going to be, or what the state of the application is at a given point, until I try/run it.
I taught myself BASIC when I was 7 when I didn't know what a programming language was.
I've been programming JS for 25 years and I still commonly can't predict what the behavior of some aspects of my code is going to be, or what the state of the application is at a given point, until I try/run it.
Thus far, JS has overwhelmingly been my favorite programming language. Expressive; amazing type system with TS; fast (V8 is an engineering marvel); and its ecosystem has frameworks/libraries for nearly everything, given its overwhelming popularity!
What makes reasoning about JS your code difficult, relative to other languages? Maybe the event loop is unintuitive? In my experience, opaque application states were caused by my odd engineering choices rather than any particular language. But I'd love to hear your experience.
What makes reasoning about JS your code difficult, relative to other languages? Maybe the event loop is unintuitive? In my experience, opaque application states were caused by my odd engineering choices rather than any particular language. But I'd love to hear your experience.
There are so many gotchas that I give up even trying to remember them, thus I just try the code to find out what it will do. One fun one that just came up is that async callbacks work totally different inside a forEach vs a for loop. https://developer.mozilla.org/en-US/docs/Glossary/Hoisting
I’m sure someone out there has compiled the list of things that don’t make sense.
It’s like 100 people designed different features without talking to each other and glued it all together into one language.
I’m sure someone out there has compiled the list of things that don’t make sense.
It’s like 100 people designed different features without talking to each other and glued it all together into one language.
In one of my earlier JS projects, the coding guidelines strictly enforced the rule of declaring all variables at top of the function to not get confused by JS hoisting "magic".
You need to enforce coding conventions in JS as soon as you have greater than one person working on a project. Sometimes even if you are the lone person - esp if you are coming back to it after a delay.
You need to enforce coding conventions in JS as soon as you have greater than one person working on a project. Sometimes even if you are the lone person - esp if you are coming back to it after a delay.
It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration - Edsger W. Dijkstra
At university I took one cs class, which was an easy credit part of a math class. It was taught in Fortran and at the beginning of the first lecture (this was in 1990) the lecturer asked for a show of hands who had experience with BASIC and many of us raised our hands. We were then given a pessimistic variant of the Dijkstra quote.
I never took another CS class
I have been working in the industry for nearly 30 years, have worked on cutting edge technology, contributed to software that billions of people use (and written plenty that fewer than 10 people use)
I will, of course, never have the same impact/influence that Dijkstra has had.
Did he ever acknowledge how fundamentally wrong he was about this?
I never took another CS class
I have been working in the industry for nearly 30 years, have worked on cutting edge technology, contributed to software that billions of people use (and written plenty that fewer than 10 people use)
I will, of course, never have the same impact/influence that Dijkstra has had.
Did he ever acknowledge how fundamentally wrong he was about this?
This is quite hilarious considering the rest of the Dijkstra 1975 letter
>FORTRAN --"the infantile disorder"--, by now nearly 20 years old, is hopelessly inadequate for whatever computer application you have in mind today: it is now too clumsy, too risky, and too expensive to use.
>FORTRAN --"the infantile disorder"--, by now nearly 20 years old, is hopelessly inadequate for whatever computer application you have in mind today: it is now too clumsy, too risky, and too expensive to use.
"4" + 4 = "44"
"44" - 4 = 40
"44" - 4 = 40
People love to trot out examples like this while remaining totally silent about why they're trying to add/subtract numbers and strings in the first place or articulate what they expected to happen when they did it.
On two occasions I have been asked, "Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?" [...] I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.
On two occasions I have been asked, "Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?" [...] I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.
Why? Because type errors are a fact of life in programming. They're not evidence of programmers trying to be eccentric. What was expected? Regardless if static or dynamic, it should be strongly typed. Just throw the error. All languages that have tried to salvage the situation when the programmer's intent became ambiguous end up creating problems down the road.
> type errors are a fact of life in programming
...and anyone who cares, therefore, uses a typechecker.
What makes it such a weird criticism is that, in order for it to make sense, you have to satisfy all three of 1) being someone who is annoyed that the operators have these well-defined semantics for mixed types, 2) actually mixing types and doing so by accident rather than intentionally, but 3) nonetheless someone who refuses to use a typechecker. That's a special case of someone insistent on putting the wrong figures into the machine altogether...
> Regardless if static or dynamic, it should be strongly typed. Just throw the error.
Java and C# are two of the most popular and widely used strongly typed languages. They don't throw errors for this.
...and anyone who cares, therefore, uses a typechecker.
What makes it such a weird criticism is that, in order for it to make sense, you have to satisfy all three of 1) being someone who is annoyed that the operators have these well-defined semantics for mixed types, 2) actually mixing types and doing so by accident rather than intentionally, but 3) nonetheless someone who refuses to use a typechecker. That's a special case of someone insistent on putting the wrong figures into the machine altogether...
> Regardless if static or dynamic, it should be strongly typed. Just throw the error.
Java and C# are two of the most popular and widely used strongly typed languages. They don't throw errors for this.
Oh I absolutely ran into this because I had a bug, I had forgot to parse the number into the correct format, but it still feels odd that the language behaves this way. Here is an example of what Ruby outputs:
"4" + 4 : `+': no implicit conversion of Integer into String (TypeError)
"44" - 4 : undefined method `-' for "40":String (NoMethodError)
The funny thing being the implicit type conversion that javascript does. This is likely why typescript has become so popular.
Are there other languages that have implicit type conversion for basic types like javascript?
"4" + 4 : `+': no implicit conversion of Integer into String (TypeError)
"44" - 4 : undefined method `-' for "40":String (NoMethodError)
The funny thing being the implicit type conversion that javascript does. This is likely why typescript has become so popular.
Are there other languages that have implicit type conversion for basic types like javascript?
Java?
In other words: play stupid games, win stupid prizes. ;)
Haha yes, most oddities in JS are a result of the language allowing you to play stupid games - many languages would just throw an error here (heck even ruby does). I discovered this strangeness when I forgot to parseFloat on a string and things kept humming along as if nothing was wrong, until I did some addition and things grew exponentially.
> many languages would just throw an error here
Some do. Many don't.
I have a feeling that most people who say this sort of thing mean "Python" and assume that that's the norm. (The "heck even ruby does" remark def. reinforces that.)
Can you name any that do that aren't dynamic languages?
Some do. Many don't.
I have a feeling that most people who say this sort of thing mean "Python" and assume that that's the norm. (The "heck even ruby does" remark def. reinforces that.)
Can you name any that do that aren't dynamic languages?
C, Rust, Go. There are probably many more.
But I think you might be overall misinterpreting my original comment. I was responding to someone who said they still commonly find unpredictable behavior in Javascript that they were unaware of after using it for years. I just responded with something I recently discovered in a similar vein, and you appeared to take it as some sort of statement about Javascript as a language. I really enjoy Javascript, and I was really just highlighting a recent example I ran into that gave me the same feeling conveyed in the original comment I was responding to.
But I think you might be overall misinterpreting my original comment. I was responding to someone who said they still commonly find unpredictable behavior in Javascript that they were unaware of after using it for years. I just responded with something I recently discovered in a similar vein, and you appeared to take it as some sort of statement about Javascript as a language. I really enjoy Javascript, and I was really just highlighting a recent example I ran into that gave me the same feeling conveyed in the original comment I was responding to.
C does not throw an error. C does not even have the infrastructure to throw errors. The closest thing are signals, and it doesn't use those for this issue.
Go is similar to C, C#, Java, JS, etc in the sense that if anything is to be done about it then the expectation is for it to be flagged as part of typechecking before runtime.
I don't have enough experience with Rust, but I'd be willing to bet that it doesn't do what you're saying, either.
Go is similar to C, C#, Java, JS, etc in the sense that if anything is to be done about it then the expectation is for it to be flagged as part of typechecking before runtime.
I don't have enough experience with Rust, but I'd be willing to bet that it doesn't do what you're saying, either.
C throws a warning, because you need to manually cast to get expected behavior. But it does not behave the same as javascript, try it yourself, you will not get "44" when you add "4" to 4.
Go does not support implicit type conversion, so no it does not behave the same as Java or Javascript, and will throw an error.
Rust does not allow adding an integer to a string and will also throw an error.
I suggest actually trying these things yourself, we are talking about adding an integer to a string, or subtracting an integer from a string. Obviously many languages will throw an error when trying to do this.
Go does not support implicit type conversion, so no it does not behave the same as Java or Javascript, and will throw an error.
Rust does not allow adding an integer to a string and will also throw an error.
I suggest actually trying these things yourself, we are talking about adding an integer to a string, or subtracting an integer from a string. Obviously many languages will throw an error when trying to do this.
> C throws a warning [sic]
No, it doesn't. Nor does it throw an error. Once again: C does not even have the infrastructure to throw. Not just when adding numbers and strings, but anything. Ever. In any circumstance.
> it does not behave the same as javascript
Who said it did?
> I suggest actually trying these things yourself
Likewise (especially if you're going to be condescending about it).
> Obviously many languages will throw an error when trying to do this.
That's not obvious. I've asked you for examples, and you've named multiple ones that definitely don't. (And this is not an attempt to be rude, but rather frank: at this point in the discussion you come across as someone who, despite having probably used several handfuls of languages including the ones you mention, has a lot of confidence but only a coarse understanding and/or loose appreciation of the relevant concepts at play—down to confusing the distinction between compile-time vs run-time behavior.)
No, it doesn't. Nor does it throw an error. Once again: C does not even have the infrastructure to throw. Not just when adding numbers and strings, but anything. Ever. In any circumstance.
> it does not behave the same as javascript
Who said it did?
> I suggest actually trying these things yourself
Likewise (especially if you're going to be condescending about it).
> Obviously many languages will throw an error when trying to do this.
That's not obvious. I've asked you for examples, and you've named multiple ones that definitely don't. (And this is not an attempt to be rude, but rather frank: at this point in the discussion you come across as someone who, despite having probably used several handfuls of languages including the ones you mention, has a lot of confidence but only a coarse understanding and/or loose appreciation of the relevant concepts at play—down to confusing the distinction between compile-time vs run-time behavior.)
C: "4" + 4 = 8
warning: assignment to ‘char’ from ‘char *’ makes integer from pointer without a cast
Go: "4" + 4 invalid operation: "4" + 4 (mismatched types untyped string and untyped int)
Rust: "4" + 4 error[E0369]: cannot add `{integer}` to `&str`
Listen - you can argue semantics all you want but unless you try these things yourself, we're not going to get anywhere. You asked me for examples of non-dynamic languages that don't behave the same as javascript, I provided them. I feel like maybe you took my suggestion to actually try these things out as condescending, it wasn't, I was trying to be constructive.
This is a discussion about what languages allow you to do, compile-time vs run-time is irrelevant, if we get a warning or an error at compile-time vs run-time it makes no difference. The point is that Javascript silently hums along with no warning or error at all when you try to do something that many languages would not allow you to do without at least a warning. You can dig down into a semantic rabbit hole about what "throw" really means but I think you understand what I'm talking about.
Go: "4" + 4 invalid operation: "4" + 4 (mismatched types untyped string and untyped int)
Rust: "4" + 4 error[E0369]: cannot add `{integer}` to `&str`
Listen - you can argue semantics all you want but unless you try these things yourself, we're not going to get anywhere. You asked me for examples of non-dynamic languages that don't behave the same as javascript, I provided them. I feel like maybe you took my suggestion to actually try these things out as condescending, it wasn't, I was trying to be constructive.
This is a discussion about what languages allow you to do, compile-time vs run-time is irrelevant, if we get a warning or an error at compile-time vs run-time it makes no difference. The point is that Javascript silently hums along with no warning or error at all when you try to do something that many languages would not allow you to do without at least a warning. You can dig down into a semantic rabbit hole about what "throw" really means but I think you understand what I'm talking about.
Use stupid language, get stupid games
True, and apparently counterintuitive if presented that way, but it makes sense as '+' is a string concatenation operator. It is the type conversion that can be used in unclear contexts - it can be comfortable and also dangerous.
[deleted]
[deleted]
> I still commonly can't predict what the behavior of some aspects of my code is going to be
Commonly? Could you give an example?
> or what the state of the application is at a given point
That's not a criticism of a language though, is it? It is either a criticism of how an application is being written, or a statement about the complexity of the application.
Commonly? Could you give an example?
> or what the state of the application is at a given point
That's not a criticism of a language though, is it? It is either a criticism of how an application is being written, or a statement about the complexity of the application.
This is mostly because you have been at it so long. If you start fresh with TS + modern tooling the vast majority of the gotchas no longer exist.
I’m in the same boat. My grey beard is frequently showing.
I’m in the same boat. My grey beard is frequently showing.
> I think most js devs know JavaScript is a poor choice for this
Please elaborate, why is JavaScript a poor choice for demonstrating algorithms? Also what would be a better choice, and why?
Please elaborate, why is JavaScript a poor choice for demonstrating algorithms? Also what would be a better choice, and why?
As someone that writes Node as main production language, I will say I am very glad to have been taught my DSA courses in Java. I think a strongly typed language like Java that also requires explicit memory management (if you restrict yourself to using only Arrays) is ideal because you can not ignore things that are abstracted by the language. In python or JS the standard array class is more like ArrayList and it automatically reallocates space when needed. This is hidden from you and you do not realize the additional computations that are occurring and thus you do not learn as well.
If you look inside this repo, they don’t rely on the standard array class for the linked-list or the stack. Given that, what’s wrong with Javascript?
My first DSA class was Scheme, btw, and it was absolutely fantastic, one of the best classes I had. Worrying about memory management is important to learn eventually as a CS major, but certainly is not necessary for an introduction to algorithms and structures. It all depends on what you want, right?
My first DSA class was Scheme, btw, and it was absolutely fantastic, one of the best classes I had. Worrying about memory management is important to learn eventually as a CS major, but certainly is not necessary for an introduction to algorithms and structures. It all depends on what you want, right?
> If you look inside this repo
I actually looked in the repo & I believe some of it is incorrect. For instance, the signature insert(value, rawIndex) in [1] makes no pedagogical sense. Quoting from [2] - "There is no real concept of index in a linked list...Certainly none of the methods provided on the class accept indexes....Thinking of a linked list as a list can be misleading. It's more like a chain"
He's then using this linked list as a base layer to implement Queue & Stack - which is correct - but doesn't ever use the insert with rawIndex functionality in either enqueue() or push() - so one wonders what the point of that index even was. Traditionally, a linked list allows you to insert before/after a node. i.e. addBefore(node,value) (see [2] ) He doesn't implement addBefore & addAfter.
Instead, he provides a whole bunch of non-canonical helpers like reverse(), toArray(), deleteTail() etc - these are typical LC-Easy problems that don't belong inside the data structure.
My own introduction to these things was a C course called "Data Structures in C" in the traditional CS curriculum, and yes, you would have to malloc a new node, get back a pointer with a memory address, & the process of pointing the next pointer of the current node to this new node so that the memory address of the next value was explicitly "linked" to the current value and hence linked list etc...I guess much of that terminology is lost on the new generation in the absence of pointers & memory addresses.
The canonical exercise in those days was - Show that a linked list does not store objects in contiguous memory, unlike an array. So to solve this, you would traverse the list from the head node & print the actual addresses of the memory locations along the way, proving that the vals aren't stored contiguously. I wonder what that exercise would mean in JS land.
That said, yeah its a good starting point & I applaud the effort.
[1]https://github.com/trekhleb/javascript-algorithms/blob/maste... [2] https://stackoverflow.com/a/7777687
I actually looked in the repo & I believe some of it is incorrect. For instance, the signature insert(value, rawIndex) in [1] makes no pedagogical sense. Quoting from [2] - "There is no real concept of index in a linked list...Certainly none of the methods provided on the class accept indexes....Thinking of a linked list as a list can be misleading. It's more like a chain"
He's then using this linked list as a base layer to implement Queue & Stack - which is correct - but doesn't ever use the insert with rawIndex functionality in either enqueue() or push() - so one wonders what the point of that index even was. Traditionally, a linked list allows you to insert before/after a node. i.e. addBefore(node,value) (see [2] ) He doesn't implement addBefore & addAfter.
Instead, he provides a whole bunch of non-canonical helpers like reverse(), toArray(), deleteTail() etc - these are typical LC-Easy problems that don't belong inside the data structure.
My own introduction to these things was a C course called "Data Structures in C" in the traditional CS curriculum, and yes, you would have to malloc a new node, get back a pointer with a memory address, & the process of pointing the next pointer of the current node to this new node so that the memory address of the next value was explicitly "linked" to the current value and hence linked list etc...I guess much of that terminology is lost on the new generation in the absence of pointers & memory addresses.
The canonical exercise in those days was - Show that a linked list does not store objects in contiguous memory, unlike an array. So to solve this, you would traverse the list from the head node & print the actual addresses of the memory locations along the way, proving that the vals aren't stored contiguously. I wonder what that exercise would mean in JS land.
That said, yeah its a good starting point & I applaud the effort.
[1]https://github.com/trekhleb/javascript-algorithms/blob/maste... [2] https://stackoverflow.com/a/7777687
> I actually looked in the repo & I believe some of it is incorrect. For instance, the signature insert(value, rawIndex) in [1] makes no pedagogical sense. Quoting from [2] - "There is no real concept of index in a linked list...Certainly none of the methods provided on the class accept indexes....Thinking of a linked list as a list can be misleading. It's more like a chain"
Java's LinkedList implements List, and supports index insertion. I'm not arguing it's "right", but I am arguing it's not "incorrect". It's a design decision, there are pros and cons to it (as your second link points out, C# went a different route), but I think it's a totally valid option.
Java's LinkedList implements List, and supports index insertion. I'm not arguing it's "right", but I am arguing it's not "incorrect". It's a design decision, there are pros and cons to it (as your second link points out, C# went a different route), but I think it's a totally valid option.
Java is anything but explicit memory management. If you really want to understand and work with memory management it’s C/C++
Typed arrays and array buffers have been a thing in JS for longer than many of today's crop of programmers have even been writing code. (For longer than this repo has existed, at least.)
And I don't know any language called "Node".
(That isn't to say that this project is a particularly good example of how to write algorithms-focused code. It isn't.)
And I don't know any language called "Node".
(That isn't to say that this project is a particularly good example of how to write algorithms-focused code. It isn't.)
congrats on being a pedant! "I write all my production code in the javascript runtime environment called Node.js"
You act as if I'm trying to place some unreasonable standard for verbosity upon you. In reality, it doesn't take that, and it would have sufficed to have just said "JS" where you originally wrote "Node".
The JS-is-not-Node aside was not exactly the most important part of my last comment, anyway.
The JS-is-not-Node aside was not exactly the most important part of my last comment, anyway.
[deleted]
> requires explicit memory management (if you restrict yourself to using only Arrays)
Did you mean C++?
Did you mean C++?
Everything in javascript except primatives are objects. Classes are objects, functions are objects, the runtime environment is an object. Not only is everything an object, but everything is mutable in an unlimited way.
And so how does this reflect on whether JS is a good language for demonstrating algorithms? What does it matter if something is an object? How would limiting mutability make a repo of algorithm examples any better? How are these things meaningfully different from other programming languages in this context?
JS runs on any device regular users might want to use. If done right it’s the best language for what it was built for.
Right, it's the best language because it's available almost anywhere, not because it's well designed or a good teaching language.
Its purpose seems understanding and showing implementations of data structures, in this sense JavaScript is used like pseudocode. No sane person would implement something efficient outside of C++ or C.
I would like to point out that such a resource is useful for reference purposes (only).
If you want to really understand an algorithm/a data structure, you have got to read it up and get your hands dirty and implement it yourself. There is no way around this.
This is a bit like taking notes in classes. The notes themselves are (nowadays mostly) almost worthless, with easy access to textbooks and other resources. The fact of taking the notes is what actually counts.
If you want to really understand an algorithm/a data structure, you have got to read it up and get your hands dirty and implement it yourself. There is no way around this.
This is a bit like taking notes in classes. The notes themselves are (nowadays mostly) almost worthless, with easy access to textbooks and other resources. The fact of taking the notes is what actually counts.
Sometimes you don’t want to understand it or go through “find all bugs you’ve introduced again” cycle. In that case, off-the-shelf or abstract solution is much better.
> implement it yourself ...
... in C or something that allows you to get to the nitty gritty details.
Or if the DS are immutable, do it in Haskell or similar.
... in C or something that allows you to get to the nitty gritty details.
Or if the DS are immutable, do it in Haskell or similar.
Another useful resource is Functional Jargon Explained (in Javascript): https://github.com/hemanth/functional-programming-jargon
As someone that knows enough cat theory and fp to scoff at most formal presentations (including all of the famous hypebeast ones hn loves to recommend), I have to say bravo to that guy (person) for doing something I've thought of doing many times (and doing it very well!).
My strongly held belief is that FP/category theory is a language game (in the wittgenstein sense) played for its own sake.
If you don't know fp and you're curious/impressed by all the jargon and I told you functor/monad/applicative is all just a means to runtime operator overloading would you still be as impressed?
And if you do know fp and I say the same to you, if your response is I'm wrong, can you please give me a concrete example for something that Applicative (or one of those other things) can do that runtime operator overloading can't? And don't allude to purity or laziness because those are orthogonal. Here I'm talking about specifically what `lift` and `bind` enable you to compute. Further preempting the very common responses: equational reasoning is an artifact of the type system that enforces various "contracts". You can enforce the same contracts in whatever imperative language (at runtime, at compile time, whatever).
My strongly held belief is that FP/category theory is a language game (in the wittgenstein sense) played for its own sake.
If you don't know fp and you're curious/impressed by all the jargon and I told you functor/monad/applicative is all just a means to runtime operator overloading would you still be as impressed?
And if you do know fp and I say the same to you, if your response is I'm wrong, can you please give me a concrete example for something that Applicative (or one of those other things) can do that runtime operator overloading can't? And don't allude to purity or laziness because those are orthogonal. Here I'm talking about specifically what `lift` and `bind` enable you to compute. Further preempting the very common responses: equational reasoning is an artifact of the type system that enforces various "contracts". You can enforce the same contracts in whatever imperative language (at runtime, at compile time, whatever).
I think this is more in the lines of mixing up concepts (the language features that enable implementing functors etc. in Haskell with functors as used in programming). I liked the JavaScript monad example in the grandparent, even if it was underwhelming. It is similar to Douglas Crockford's presentation of monads (using JavaScript, but with more interesting examples like promises).
Type classes (as a language construct) are a way of doing ad-hoc polymorphism (read run-time operator overloading) more principled, and other language features can be used in place of them to implement an _interface_ for monads, functors, etc. One example is Scala's for expressions which boil down to a series of map, flatMap, filter and forEach calls so they work with any type that implements the subset of them you need without using type classes. If you want static typing and dynamic dispatch for stuff like monads then you'd want something like type classes or F-bounded polymorphism (what I allude to with the Mappable interface below) to have that.
So, from what I see saying "run-time operator overloading can do what monads, etc. can do" would lead to "function pointers and closures can already do dynamic dispatch, what's the point of run-time operator overloading then?". Type classes are a way to have your cake and statically type-check it too (and they aren't the only way).
Just to clarify, functors, applicatives, and monads are basically interfaces for polymorphic (generic) types with useful properties (which aren't checked by the language unless you're going out of your way to use something like Agda, so that's not the point) and they turn out to model accessing and changing data in a context in a nice way. You can just call them Mappable, Liftable, and Joinable and ship them in a Java library.
I agree the language game part of it, the idea for them comes from category theory but they are different from what category theorists had in mind, and the jargon could be toned down to emphasize what they are useful for. I think the big idea is that a list (or an option) isn't the only thing that has a meaningful map and flatMap implementation, which is much simpler than "a monad is just a monoidal object in the category of endofunctors over Haskell types, what's the problem?"
Type classes (as a language construct) are a way of doing ad-hoc polymorphism (read run-time operator overloading) more principled, and other language features can be used in place of them to implement an _interface_ for monads, functors, etc. One example is Scala's for expressions which boil down to a series of map, flatMap, filter and forEach calls so they work with any type that implements the subset of them you need without using type classes. If you want static typing and dynamic dispatch for stuff like monads then you'd want something like type classes or F-bounded polymorphism (what I allude to with the Mappable interface below) to have that.
So, from what I see saying "run-time operator overloading can do what monads, etc. can do" would lead to "function pointers and closures can already do dynamic dispatch, what's the point of run-time operator overloading then?". Type classes are a way to have your cake and statically type-check it too (and they aren't the only way).
Just to clarify, functors, applicatives, and monads are basically interfaces for polymorphic (generic) types with useful properties (which aren't checked by the language unless you're going out of your way to use something like Agda, so that's not the point) and they turn out to model accessing and changing data in a context in a nice way. You can just call them Mappable, Liftable, and Joinable and ship them in a Java library.
I agree the language game part of it, the idea for them comes from category theory but they are different from what category theorists had in mind, and the jargon could be toned down to emphasize what they are useful for. I think the big idea is that a list (or an option) isn't the only thing that has a meaningful map and flatMap implementation, which is much simpler than "a monad is just a monoidal object in the category of endofunctors over Haskell types, what's the problem?"
>I think this is more in the lines of mixing up concepts (the language features that enable implementing functors etc. in Haskell with functors as used in programming).
You know how you can identify an fp person? They'll condescend to you and dismiss what you say.
>Type classes (as a language construct) are a way of doing ad-hoc polymorphism (read run-time operator overloading)
You're glossing over what I'm saying and drawing some superficial analogy that I am not - I'm not talking parametric polymorphism, I'm talking about monadic evaluation ie evaluation within a context. I'm talking about the same thing as dynamic binding, which is also used to implement the same exact things as monads (see the collapsing interpreters paper by Amin and Rompf).
So no I'm not confused and I'm not conflating, I am in fact making a strong claim. Again, my proof is exactly using the same language: a morphism between runtime operator overloading and lift/bind.
To give a more abstruse argument, compare Conal Elliot's compiling to categories and jax (which is immediately recognized as a monadic interpreter framework).
You know how you can identify an fp person? They'll condescend to you and dismiss what you say.
>Type classes (as a language construct) are a way of doing ad-hoc polymorphism (read run-time operator overloading)
You're glossing over what I'm saying and drawing some superficial analogy that I am not - I'm not talking parametric polymorphism, I'm talking about monadic evaluation ie evaluation within a context. I'm talking about the same thing as dynamic binding, which is also used to implement the same exact things as monads (see the collapsing interpreters paper by Amin and Rompf).
So no I'm not confused and I'm not conflating, I am in fact making a strong claim. Again, my proof is exactly using the same language: a morphism between runtime operator overloading and lift/bind.
To give a more abstruse argument, compare Conal Elliot's compiling to categories and jax (which is immediately recognized as a monadic interpreter framework).
I misinterpreted what you said then, sorry about that.
The examples you give were helpful to understand what you mean by "runtime operator overloading"--specifically, the Amin & Rompf paper. It's been a while since I read it but looking at it again reminded me of the similar terminology they use. I agree that having a multi-staged language gives you the benefits of using monads (as in abstracting away/carrying around context).
> You know how you can identify an fp person? They'll condescend to you and dismiss what you say.
Just to note, I don't have a strong preference towards trying to do everything with a monad, stacking them, etc. and I am definitely not an "fp person".
The examples you give were helpful to understand what you mean by "runtime operator overloading"--specifically, the Amin & Rompf paper. It's been a while since I read it but looking at it again reminded me of the similar terminology they use. I agree that having a multi-staged language gives you the benefits of using monads (as in abstracting away/carrying around context).
> You know how you can identify an fp person? They'll condescend to you and dismiss what you say.
Just to note, I don't have a strong preference towards trying to do everything with a monad, stacking them, etc. and I am definitely not an "fp person".
> if your response is I'm wrong
I've actually seen people criticise the definition and implementation of monads there because they apparently don't conform to monadic laws :)
As a guy who's tried and failed to get into Haskell a few times, I say: so what :)
I've actually seen people criticise the definition and implementation of monads there because they apparently don't conform to monadic laws :)
As a guy who's tried and failed to get into Haskell a few times, I say: so what :)
Yes monads in Haskell aren't "lawful" but they're still useful, which you rightly point out does indirectly reaffirm my claim.
As far as sorting goes, I made a visualizer a while ago https://xosh.org/VisualizingSorts/sorting.html which additionally let's you visualize your own algo and share it via url.
This is really cool. It inspires me to try and visualize my old AOC solutions
One can spend an enjoyable afternoon re-implementing some of these using the equivalent of lisp's cons as a node:
let node = (a,b) => (bool) => bool?a:b;
Tutorials such as this one seem geared more towards college DSA courses rather than actual production code. For example, the code for traversing a tree in any order is implemented using recursion, but this is not what production code would do, as for any large amount of data the stack would be exhausted as recursive depth limits are exceeded. Thus, real-world code always requires the creation of a dynamically allocated stack or queue on the heap to store the values at each node.
I don't know if there are similar issues with say, the presenation of hash tables, but it does cause a certain lack of confidence. This kind of gap between academic presentation of concepts and real-world production approaches is fairly common - but why not always teach the latter, I wonder?
I imagine 'baby steps' is the argument, but it could also be called teaching bad practices. Incidentally, ChatGPT continues to astound:
> "What would a code snippet for traversing a binary search tree in in-order in Javascript using a dynamically allocated heap approach look like?"
I don't know if there are similar issues with say, the presenation of hash tables, but it does cause a certain lack of confidence. This kind of gap between academic presentation of concepts and real-world production approaches is fairly common - but why not always teach the latter, I wonder?
I imagine 'baby steps' is the argument, but it could also be called teaching bad practices. Incidentally, ChatGPT continues to astound:
> "What would a code snippet for traversing a binary search tree in in-order in Javascript using a dynamically allocated heap approach look like?"
> For example, the code for traversing a tree in any order is implemented using recursion, but this is not what production code would do,
I think this is much too strong of a generalization. For small trees, a recursive traversal is clearer & easier to modify, and I would prefer to ship a recursive traversal vs. an iterative one.
In fact, part of my job at Google was optimizing a particular (recursive) tree traversal in Search. Every time you search on Google, that traversal happens many thousands of times behind the scenes :).
I think this is much too strong of a generalization. For small trees, a recursive traversal is clearer & easier to modify, and I would prefer to ship a recursive traversal vs. an iterative one.
In fact, part of my job at Google was optimizing a particular (recursive) tree traversal in Search. Every time you search on Google, that traversal happens many thousands of times behind the scenes :).
Also, Stack: [] Hash table: {} Queue: []. It’d be nice if Linkedlist and others (neural network) were made part of the language.
For other languages, see https://github.com/tayllan/awesome-algorithms — resources to learn and/or practice algorithms
Cmd+F Rust
0 results
>:(
0 results
>:(
That's surprising. Anyway check these out:
* https://github.com/EbTech/rust-algorithms
* https://github.com/TheAlgorithms/Rust
* https://github.com/EbTech/rust-algorithms
* https://github.com/TheAlgorithms/Rust
The primeagen has a great free DSA course using js on front end masters too.
https://frontendmasters.com/courses/algorithms/
https://frontendmasters.com/courses/algorithms/
I hear almost exactly this same discussion over roughly the same points about every coding language I have encountered. Well, in the forums of those languages...
Seems like this might be worth bookmarking in case I ever want to learn Javascript; reading implementations of algorithms I've written before in other languages seems like it might be helpful.
Are there similar resources for other languages? I'd like python, lua, tcl, and dart...
Likely not , maybe python, well definitely python you'd think.
Likely not , maybe python, well definitely python you'd think.
The number of stars on that repo!
Wow, no kidding! This has to be one of them most popular repos there is?
Are these considered the best possible implementations of relevant algorithms in JS?
I wish these were in their own repositories, it's a bit unwieldy to follow issues/PRs in a monorepo. Also would make sense to publish them on NPM for reuse...
I wish these were in their own repositories, it's a bit unwieldy to follow issues/PRs in a monorepo. Also would make sense to publish them on NPM for reuse...
These implementations are nicely written for learning purposes, but look inefficient.
For example many of the data structures are implemented with a LinkedList, but the allocations and pointer chasing is likely slower than just using arrays.
For example many of the data structures are implemented with a LinkedList, but the allocations and pointer chasing is likely slower than just using arrays.
As a relative novice, I notice that a few animation libraries rely on linked lists for sequencing animations, and, as I understand it, React uses a linked list to implement the queue created from the Hooks calls in a component; is there no benefit to a linked list over an array that counters the downside of pointer chasing?
Libraries and frameworks generally use intrusive linked lists where the pointers are embedded inside the objects. That enables a lot of useful properties (like traversal) with minimal overhead. That's how the DOM and Layout is implemented in browsers as well.
Link lists that use separate nodes (like the project in TFA) are rarely the best choice due to the performance trade offs and way modern CPUs work.
This article explains it well: https://www.data-structures-in-practice.com/intrusive-linked...
See also:
https://github.com/trekhleb/javascript-algorithms/blob/bbbfd...
https://github.com/trekhleb/javascript-algorithms/blob/bbbfd...
Vs what React does:
https://github.com/facebook/react/blob/657698e48d5b093b4ea5a...
Link lists that use separate nodes (like the project in TFA) are rarely the best choice due to the performance trade offs and way modern CPUs work.
This article explains it well: https://www.data-structures-in-practice.com/intrusive-linked...
See also:
https://github.com/trekhleb/javascript-algorithms/blob/bbbfd...
https://github.com/trekhleb/javascript-algorithms/blob/bbbfd...
Vs what React does:
https://github.com/facebook/react/blob/657698e48d5b093b4ea5a...
Very helpful, thank you
I realize you mentioned hooks not react in general, that code is here:
https://github.com/facebook/react/blob/657698e48d5b093b4ea5a...
You can see the linked list insertion right below that too.
You can see the linked list insertion right below that too.
Thank you!
I would love to see HNSW in JS.
I tend to think of Javascript as the language that fulfills the promises that BASIC never did.
If every student walking into a computer science course only knew Javascript, that would still be a massive improvement over the past where half the students didn't know any programming language at all or only some vastly underpowered ones like Logo or BASIC.