Optionen trading card game pokemon online deck code22 comments
Optionen trading card
Like the section on lists, this gives a nice little explanation on how to deal with inserts to a tree data structure when the data is immutable in as efficient a way as possible. The most brute force solution to this would be to create a complete duplicate of the tree save for the newly added value, this section shows that, while copying is necessary, only the search path from the root to the new element needs to be copied. The new tree will then reference as much of the old tree as possible; minimizing both copies and memory used.
What this post will cover: A BST has two possible values: So a discriminated union captures this set and a tuple can store the value and 2 children. Leading, as with the list, to a recursive type:. A requirement for a BST is that 'a must have a total ordering: The above definition does not capture this requirement and so we can make a Tree of any type.
In F this can be captured using a constraint on the type:. I changed the name of the type from Tree to BinarySearchTree to capture the more focused nature of the type when a constraint is added. The Tree can be use to create any type of binary tree structure, with the constraint the type becomes focused specifically on ordering and searching. The updated name helps to reflect this focus. This type could also be put into a module named BinarySearchTree to capture that information and then keep the type named simply Tree.
As a note, there is another option with F for capturing the comparability requirement. When we write our insert and search functions, the F compiler with infer that, for those functions, 'a must have the comparison constraint.
This decouples the use of the tree from the type definition. If we want the type to capture only the structure of a binary tree, then this approach makes sense.
However, if we want the type to capture both the structure and the purpose searching then this approach seems like it will be fragile and confusing. I initially thought that there was a third option: It seemed likely that the F compiler would infer that 'a must have the comparison constraint. Testing proved that this is not the case and, in fact, the compiler throws an error because Tree must explicitly have the comparison constraint in order for the member methods to work.
Checking membership in the tree is the first of the two absolutely necessary functions for our BST. I rarely used the function expression in the past so this is helping me to get a feel for this as a part of my toolbox. Leaving out the parameters in the function definition is the point free style of programming. However, it fits well with the function expression since the focus is the patterns that are being matched and that documents the parameters well enough.
The insert function is a little more complex than isMember: This is called the search path. As it moves, insert makes a copy of each node on the search path.
The nodes are copied so that they can store the path to the new value, the nodes on the search path are the minimum number of nodes that need to be copied.
And of course, because data is immutable, we have to copy some nodes in order to make our insert. The brown nodes are the copied nodes on the search path, the dashed lines represent the new links in those nodes.
In this problem, we have to update isMember to reduce the number of conditions in the execution path. While the last pattern matching expression has only one conditional rather than two, it also has an additional pattern match check and so it seems unlikely that the number of condition checks is actually reduced.
The worst part is, that pattern match check must get executed every time. My second attempt became less idiomatic but it successfully reduces the number of required conditionals:. In other languages, I almost never do this not counting the ternary operator in the C family. However, the current insert function will still copy all the nodes on the search path. This problem Okasaki has us fix that by throwing a fault if the value is already in the tree. This will bubble a break up through the recursive path and break the execution path before any copies are made:.
Finally, we combine this update with the update to isMember to optimize insertion even more:. Leading, as with the list, to a recursive type: