Install Bun, followed by
bun main.ts
Install .NET SDK, and run
dotnet new --install Microsoft.DotNet.Web.Spa.ProjectTemplates::*
dotnet new console -lang "F#" -n TreeDemo
Copy Program.fs to TreeDemo/Program.fs and run
dotnet clean
dotnet build
dotnet run
There should be 0 errors and 0 warnings.
If you want to toggle F# types, install VS Code Ionide plugin. You may find "Cannot Toggle Types with Keys" useful.
TypeScript took five iterations, F# worked instantly afterwards.
Implement a tree with CRUD operations in TypeScript. Use only recursive types, not a built in list or map. Use functional style, sum types, exhaustive switch with the type never to achieve null safety.
Rewrite it so that each node can contain any number of children. Add DFS and BFS traversal functions and use them to visualize a tree compactly with utf8 line symbols. Write a function to create a random tree of a given maximal depth and maximal num of children per node. Write a demo which creates that random tree, then performs say a hundred random CRUD operations and times the execution.
Make sure vertical lines connecting the nodes at the same tree depth are not broken and visualization is vertically as compact as possible. Use a "90 degree rotated capital T" utf8 symbol and others to fill all the gaps.
Rewrite visualization function so that there are no empty spaces that may occupy entire line in cli. Right now your vertical connections are "broken lines".
You are indenting from left to right correctly, but you are not placing the nodes of the same tree depth vertically as compactly as possible at times. A visualized tree has empty stripes which are just entire empty lines in the terminal which should be deleted to get compactness and connectivity. You are placing utf8 connectors correctly more or less, but occassionally a node at the same tree depth goes one line below than it should, leaving the entire empty line at cli.
Rewrite this in F#. Use idiomatic FP, as much immutability as possible, null safety.
-
TypeScript:
const findValue = <T>(tree: Tree<T>, value: T): T | null => {
-
The same line in F#:
let rec findValue tree value =
-
F# with types automatically inferred upon user request:
val findValue: tree : Tree<'a> -> value: 'a (requires equality ) -> option<'a>
-
It would certainly be interesting to study more of type inference in action (F#, Rust, Roc?), witness various levels of it, edge cases.
-
This demo code does not reveal the cons of type inference, e.g. nasty compiler errors. Gleam uses only generic types for a reason.
-
Type annotations are typically written manually in TypeScript and Rust.
-
F# looks better, but TypeScript is not bad at all here.
-
TypeScript shows what would happen to Go if we removed pointers, added sum types, imposed default non-nullability on reference types, without going all the way with type constructors and pattern matching.
-
Compare the codes yourself and see whether you find TypeScript disgusting, or a decent approximation. The problem is that the answer is unlikely to be found in small code demos. It lies in a deeper experience with type inference and compiler errors. F#/Roc vs Gleam... ChatGPT might have some answers too.
-
I was hoping for some immutable trees as mentioned in Sect. 3.4.1 Persistence and Immutability in A History of Clojure (2020). However, ChatGPT would not do that with a simple prompt formulated above. It would have to be pushed harder, likely with a lot of iterations.