I created a simple sorted Btree and I’m wondering how you could create a map function for this data structure to ensure the order of the mapped data. I created a map func(below) and I’m wondering if this is a correct way of doing it.
module MyBtree =
struct
type 'a btree = Empty | Btree of ('a * 'a btree * 'a btree)
let empty = Empty
let rec add data bt =
match bt with
| Empty -> Btree(data, Empty, Empty)
| Btree (d, left, right) ->
if (data < d)
then
Btree(d, add data left, right)
else if (data > d)
then
Btree(d, left, add data right)
else
bt
(*...*)
let map func bt =
let rec mapAux func bt newBt =
match bt with
| Empty -> newBt
| Btree (d, left, right) ->
mapAux func right (mapAux func left (add (func d) newBt)) in
mapAux func bt empty
end