search

coalton-lang / coalton

Coalton is an efficient, statically typed functional programming language that supercharges Common Lisp.
https://coalton-lang.github.io/
MIT License
1.12k stars 67 forks source link

`tree:insert` results in a red branch, where it should result in a black branch like `tree:insert-or-replace` #1173

Open YarinHeffes opened 1 month ago

YarinHeffes commented 1 month ago

The line (coalton (tree:insert-or-replace tree:empty 0)) results in #.(TREE::BRANCH TREE::COLOR/BLACK #.TREE:EMPTY 0 #.TREE:EMPTY) whereas the line (coalton (unwrap (tree:insert tree:empty 0))) results in #.(TREE::BRANCH TREE::COLOR/RED #.TREE:EMPTY 0 #.TREE:EMPTY)

This causes issues when removing elements after having inserted several elements via tree:insert: (coalton (tree:remove (unwrap (tree:insert (unwrap (tree:insert tree:empty 0)) 1)) 0)) results in the error: Attempt to `remove-max` on an empty tree.

This issue also affects map:insert.

This issue can be addressed by applying the as-black function before returning the evaluation of the insert function, such as (map as-black (ins tre)) however, there may be more to this issue, and it may be an issue for other functions as well, including replace.

stylewarning commented 1 month ago

CC @gefjon