54 lines
2.3 KiB
Plaintext
54 lines
2.3 KiB
Plaintext
|
# binary_tree takes a comparison function and returns a record (like a JS
|
||
|
|
# object) as a module for handling binary trees of values of the same type
|
||
|
|
# as compare's arguments.
|
||
|
|
def binary_tree(compare) =
|
||
|
|
# Backticks here indicate that leaf is a constructor for a tagged union
|
||
|
|
# (variant) type.
|
||
|
|
let empty = `leaf
|
||
|
|
and insert(tree, value) = when tree is
|
||
|
|
`leaf => `branch({left=`leaf, value = value, right=`leaf),
|
||
|
|
`branch({left, value=value2, right) => when compare(value, value2) is
|
||
|
|
`eq => `branch({left, value, right}),
|
||
|
|
`lt =>
|
||
|
|
let new_left = insert(left, value)
|
||
|
|
in `branch({left=new_left, value=value2, right}),
|
||
|
|
`gt =>
|
||
|
|
let new_right = insert(right, value)
|
||
|
|
in `branch({left, value=value2, new_right})
|
||
|
|
and find(tree, needle) = when tree is
|
||
|
|
`leaf => `nothing,
|
||
|
|
`branch({left, value, right}) => when compare(needle, value) is
|
||
|
|
`eq => `some(value),
|
||
|
|
`lt => find(left, needle),
|
||
|
|
`gt => find(right, needle),
|
||
|
|
and func_we_dont_care_about() = print("ignore me")
|
||
|
|
in {empty, insert, find}
|
||
|
|
|
||
|
|
# Prints "`some(2)".
|
||
|
|
def do_tree_things() =
|
||
|
|
# Assume that int_compare is in the stdlib or something.
|
||
|
|
# Notice that we can ignore a record field. I want to make record
|
||
|
|
# syntax basically the same as in JS.
|
||
|
|
let {insert, empty, find, ...stuff_we_dont_need} = binary_tree(int_compare)
|
||
|
|
# I invented this fancy partial-application syntax with _, and then found
|
||
|
|
# that Scala does it the same way. Also note the pipe operator from Elm.
|
||
|
|
and _ = empty |> insert(_, 5) |> insert(_, 2) |> insert(_, 10)
|
||
|
|
|> find(2) |> print
|
||
|
|
in stuff_we_dont_need
|
||
|
|
|
||
|
|
# Prints "`some(2)\nignore me".
|
||
|
|
def main() = do_tree_things().func_we_dont_care_about()
|
||
|
|
|
||
|
|
|
||
|
|
# I'd better be able to make type inference work, or else the user might have
|
||
|
|
# to annotate binary_tree like this:
|
||
|
|
binary_tree : fn('a, 'a) -> Record{
|
||
|
|
empty: recurse T in Union{leaf, branch of Record{left: T, value: 'a, right: T},
|
||
|
|
insert: fn(recurse T in Union{leaf, branch of Record{left: T, value: 'a, right: T}, 'a) ->
|
||
|
|
recurse T in Union{leaf, branch of Record{left: T, value: 'a, right: T},
|
||
|
|
find: fn(recurse T in Union{leaf, branch of Record{left: T, value: 'a, right: T}, 'a) ->
|
||
|
|
Union{some of 'a, nothing},
|
||
|
|
func_we_dont_care_about: fn() -> Record{}
|
||
|
|
}
|
||
|
|
# Though it might be possible to introduce a way to factor out the tree type,
|
||
|
|
# which is the big thing starting with "recurse T".
|