JavaScript-algorithms: Algorithms and data structures implemented in JavaScript
github.com
github.com
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.
Please elaborate, why is JavaScript a poor choice for demonstrating algorithms? Also what would be a better choice, and why?
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?
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
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.
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.)
The JS-is-not-Node aside was not exactly the most important part of my last comment, anyway.
Did you mean C++?
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.
"44" - 4 = 40
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?
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.
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 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.
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.)
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.
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.
"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?
...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.
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.
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.
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.
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?
>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.
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.
I’m in the same boat. My grey beard is frequently showing.
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.
... 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.
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'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 :)
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?"
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).
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".
let node = (a,b) => (bool) => bool?a:b;
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 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 :).
0 results
>:(
Likely not , maybe python, well definitely python you'd think.
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...
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.
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...
You can see the linked list insertion right below that too.