I am wondering how a #FunctionalProgramming based implementation of a Binary Search Tree would look like?

Has anyone tried it?

If we say that in functional programming has to be a function, then it could be a function which given "right" returns the right branch, and given "left" returns the left branch. But honestly I don't know. There are probably multiple ways

In Haskell you can do it with data types. Something along

data Tree a = Leaf a | Branch a

@Flamestro Oh right. I'm stupid

data Tree a = Branch (Tree a) (Tree a) | Leaf a | Empty

Maybe this?

@Flamestro Yesh that works as well

@Flamestro yup, you're correct, that would work for a general binary tree (though you forgot the type var on the definition side). To make it a BST you need to define insert and search.

data BST a = Node a (BST a) (BST a) | Leaf

Insert and search are fairly easy, assuming less-than corresponds to left

insert val Leaf = Node val Leaf Leaf
insert val (Node nodeVal left right)
| val < nodeVal = Node nodeVal (insert val left) right
| otherwise = Node nodeVal left (insert val right)

search val Leaf = false
search val (Node nodeVal left right)
| val == nodeVal = true
| val < nodeVal = search val left
| otherwise = search val right

Logic: inserting into a leaf means making a node with the value and two leaves; into a node means inserting either to the left or right subtrees of the node.

if you search a leaf your value is not in the tree, if you search a node either it has the value you want, or the value is possibly in the left or right subtrees.

However this kind of definition is a feature of algebraic data types (ADTs), not the more general class of functional programming (which basically just means that functions are values).

If you have impure FP (or FP with controlled side effects like Haskell's ST and IO monads) then data structures look just like their counterparts in other languages.

Pure FP data structures however generally means that you return a whole new data structure after an update operation, i.e. the old data structure isn't destroyed so it's still around, i.e. the data structure is _persistent_ (in practice this is terrible for efficiency so implementations generally optimize via value sharing or something).

So a simple (and terrible) way to do it in JS would be to make a regular BST and have insert() return a whole new copy of the tree with the value inserted, so you avoid destructive updates. Check out immutable.js for a better implementation (I think) (don't know much about JS, sorry)

opened devrant in browser to type this and wow the site is a lot better than the app

type tree = | Empty | Node of int * tree * tree;;

let _t = (*make a tree*);;

let rec find key tree =
match tree with
| Empty -> false
| Node (k, l, r) -> if k = key then true else find key l or find key r;;

@ganjaman that's O(n) search of a general binary tree, not O(log n) of a BST.

@RememberMe forgot the >< at the search part yeah, imagine its there

Woaw woaw woaw guys, I opened yo see what has happened to rant I posted and omg.

First of all, I don't know haskell 😅😂.

Can any one tell me in JS or something 😅😅😅