From 2d5c3288134f19088941c980e852521e9838db56 Mon Sep 17 00:00:00 2001 From: Ben Culkin Date: Sat, 24 Sep 2022 12:35:20 -0400 Subject: Various changes --- src/main/java/bjc/data/Tree.java | 127 ++++++++------------- src/main/java/bjc/funcdata/CList.java | 54 +++++++++ src/main/java/bjc/funcdata/CListLike.java | 13 +++ src/main/java/bjc/funcdata/CListStructure.java | 38 ++++++ .../bjc/funcdata/bst/TreeLinearizationMethod.java | 2 +- src/main/java/bjc/funcdata/theory/Category.java | 28 +++++ 6 files changed, 180 insertions(+), 82 deletions(-) create mode 100644 src/main/java/bjc/funcdata/CList.java create mode 100644 src/main/java/bjc/funcdata/CListLike.java create mode 100644 src/main/java/bjc/funcdata/CListStructure.java create mode 100644 src/main/java/bjc/funcdata/theory/Category.java (limited to 'src/main/java/bjc') diff --git a/src/main/java/bjc/data/Tree.java b/src/main/java/bjc/data/Tree.java index 3e16e02..784bf0e 100644 --- a/src/main/java/bjc/data/Tree.java +++ b/src/main/java/bjc/data/Tree.java @@ -14,67 +14,56 @@ import bjc.funcdata.bst.TreeLinearizationMethod; * * @author ben * - * @param - * The type of data contained in the tree nodes. + * @param The type of data contained in the tree nodes. * */ public interface Tree { /** * Append a child to this node. * - * @param child - * The child to append to this node. + * @param child The child to append to this node. */ void addChild(Tree child); /** * Append a child to this node. * - * @param child - * The child to append to this node. + * @param child The child to append to this node. */ void addChild(ContainedType child); /** * Prepend a child to this node. * - * @param child - * The child to prepend to this node. + * @param child The child to prepend to this node. */ void prependChild(Tree child); /** * Collapse a tree into a single version. * - * @param - * The intermediate type being folded. + * @param The intermediate type being folded. * - * @param - * The type that is the end result. + * @param The type that is the end result. * - * @param leafTransform - * The function to use to convert leaf values. + * @param leafTransform The function to use to convert leaf values. * - * @param nodeCollapser - * The function to use to convert internal nodes and + * @param nodeCollapser The function to use to convert internal nodes and * their children. * - * @param resultTransformer - * The function to use to convert a state to the + * @param resultTransformer The function to use to convert a state to the * returned version. * * @return The final transformed state. */ - ReturnedType collapse( - Function leafTransform, + ReturnedType collapse(Function leafTransform, BiFunction, NewType> nodeCollapser, Function resultTransformer); /** * Execute a given action for each of this tree's children. * - * @param action - * The action to execute for each child. + * @param action The action to execute for each child. */ void doForChildren(Consumer> action); @@ -82,13 +71,11 @@ public interface Tree { * Expand the nodes of a tree into trees, and then merge the contents of those * trees into a single tree. * - * @param mapper - * The function to use to map values into trees. + * @param mapper The function to use to map values into trees. * * @return A tree, with some nodes expanded into trees. */ - default Tree - flatMapTree(final Function> mapper) { + default Tree flatMapTree(final Function> mapper) { return topDownTransform(dat -> TopDownTransformResult.PUSHDOWN, node -> { if (node.getChildrenCount() > 0) { final Tree parent = node.transformHead(mapper); @@ -105,8 +92,7 @@ public interface Tree { /** * Get the specified child of this tree. * - * @param childNo - * The number of the child to get. + * @param childNo The number of the child to get. * * @return The specified child of this tree. */ @@ -142,64 +128,50 @@ public interface Tree { /** * Rebuild the tree with the same structure, but different nodes. * - * @param - * The type of the new tree. + * @param The type of the new tree. * - * @param leafTransformer - * The function to use to transform leaf tokens. + * @param leafTransformer The function to use to transform leaf tokens. * - * @param internalTransformer - * The function to use to transform internal tokens. + * @param internalTransformer The function to use to transform internal tokens. * * @return The tree, with the nodes changed. */ - Tree rebuildTree( - Function leafTransformer, + Tree rebuildTree(Function leafTransformer, Function internalTransformer); /** * Transform some of the nodes in this tree. * - * @param nodePicker - * The predicate to use to pick nodes to transform. + * @param nodePicker The predicate to use to pick nodes to transform. * - * @param transformer - * The function to use to transform picked nodes. + * @param transformer The function to use to transform picked nodes. */ - void selectiveTransform(Predicate nodePicker, - UnaryOperator transformer); + void selectiveTransform(Predicate nodePicker, UnaryOperator transformer); /** * Do a top-down transform of the tree. * - * @param transformPicker - * The function to use to pick how to progress. + * @param transformPicker The function to use to pick how to progress. * - * @param transformer - * The function used to transform picked subtrees. + * @param transformer The function used to transform picked subtrees. * * @return The tree with the transform applied to picked subtrees. */ - Tree topDownTransform( - Function transformPicker, + Tree topDownTransform(Function transformPicker, UnaryOperator> transformer); /** * Transform one of this nodes children. * - * @param - * The type of the transformed value. + * @param The type of the transformed value. * - * @param childNo - * The number of the child to transform. + * @param childNo The number of the child to transform. * - * @param transformer - * The function to use to transform the value. + * @param transformer The function to use to transform the value. * * @return The transformed value. * - * @throws IllegalArgumentException - * if the childNo is out of bounds (0 <= + * @throws IllegalArgumentException if the childNo is out of bounds (0 <= * childNo <= childCount()). */ TransformedType transformChild(int childNo, @@ -208,50 +180,44 @@ public interface Tree { /** * Transform the value that is the head of this node. * - * @param - * The type of the transformed value. + * @param The type of the transformed value. * - * @param transformer - * The function to use to transform the value. + * @param transformer The function to use to transform the value. * * @return The transformed value. */ - TransformedType - transformHead(Function transformer); + TransformedType transformHead(Function transformer); /** * Transform the tree into a tree with a different type of token. * - * @param - * The type of the new tree. + * @param The type of the new tree. * - * @param transformer - * The function to use to transform tokens. + * @param transformer The function to use to transform tokens. * * @return A tree with the token types transformed. */ - default Tree - transformTree(final Function transformer) { + default Tree transformTree(final Function transformer) { return rebuildTree(transformer, transformer); } + // TODO: Add method which traverses tree, but randomizes order children are + // visited in + + // TODO: Add method which allows parallel traversal of children. /** * Perform an action on each part of the tree. * - * @param linearizationMethod - * The way to traverse the tree. + * @param linearizationMethod The way to traverse the tree. * - * @param action - * The action to perform on each tree node. + * @param action The action to perform on each tree node. */ - void traverse(TreeLinearizationMethod linearizationMethod, - Consumer action); + void traverse(TreeLinearizationMethod linearizationMethod, Consumer action); /** * Find the farthest to right child that satisfies the given predicate. * - * @param childPred - * The predicate to satisfy. + * @param childPred The predicate to satisfy. * * @return The index of the right-most child that satisfies the predicate, or -1 * if one doesn't exist. @@ -261,8 +227,7 @@ public interface Tree { /** * Check if this tree contains any nodes that satisfy the predicate. * - * @param pred - * The predicate to look for. + * @param pred The predicate to look for. * * @return Whether or not any items satisfied the predicate. */ @@ -270,7 +235,8 @@ public interface Tree { Toggle tog = new OneWayToggle<>(false, true); traverse(TreeLinearizationMethod.POSTORDER, val -> { - if (pred.test(val)) tog.get(); + if (pred.test(val)) + tog.get(); }); return tog.get(); @@ -279,8 +245,7 @@ public interface Tree { /** * Set the head of the tree. * - * @param dat - * The value to set as the head of the tree. + * @param dat The value to set as the head of the tree. */ void setHead(ContainedType dat); } diff --git a/src/main/java/bjc/funcdata/CList.java b/src/main/java/bjc/funcdata/CList.java new file mode 100644 index 0000000..b9ee10e --- /dev/null +++ b/src/main/java/bjc/funcdata/CList.java @@ -0,0 +1,54 @@ +package bjc.funcdata; + +import java.util.function.UnaryOperator; + +import bjc.data.Either; +import bjc.data.Pair; +import bjc.functypes.Unit; + +public class CList implements CListLike { + private Either>> data; + + private CList() { + data = Either.left(Unit.UNIT); + } + + private CList(T data, CList rest) { + this.data = Either.right(Pair.pair(data, rest)); + } + + @Override + public boolean isEmpty() { + return data.isLeft(); + } + + @Override + public T head() { + return data.forceRight().getLeft(); + } + + @Override + public CList tail() { + return data.forceRight().getRight(); + } + + @Override + public CList prefix(T val) { + return new CList<>(val, this); + } + + public static UnaryOperator> prefixing(T val) { + return (lst) -> lst.prefix(val); + } + + public static CList empty() { + return new CList<>(); + } + public static CList of(T... vals) { + CList ret = empty(); + for (int i = vals.length - 1; i >= 0; i-- ) { + ret = ret.prefix(vals[i]); + } + return ret; + } +} diff --git a/src/main/java/bjc/funcdata/CListLike.java b/src/main/java/bjc/funcdata/CListLike.java new file mode 100644 index 0000000..ba17456 --- /dev/null +++ b/src/main/java/bjc/funcdata/CListLike.java @@ -0,0 +1,13 @@ +package bjc.funcdata; + +public interface CListLike { + + boolean isEmpty(); + + T head(); + + CListLike tail(); + + CListLike prefix(T val); + +} \ No newline at end of file diff --git a/src/main/java/bjc/funcdata/CListStructure.java b/src/main/java/bjc/funcdata/CListStructure.java new file mode 100644 index 0000000..1809273 --- /dev/null +++ b/src/main/java/bjc/funcdata/CListStructure.java @@ -0,0 +1,38 @@ +package bjc.funcdata; + +import bjc.data.Either; + +// pretty sure we want to implement CListLike, but not obvious how to implement +public class CListStructure implements CListLike>> { + private Either>> data; + + public boolean isAtomic() { + return data.isLeft(); + } + + @Override + public boolean isEmpty() { + return true; + } + + @Override + public Either> head() { + if (isAtomic()) return data.newRight(); + // ... Beats me + return null; + } + + @Override + public CListLike>> tail() { + // TODO Auto-generated method stub + return null; + } + + @Override + public CListLike>> prefix(Either> val) { + // TODO Auto-generated method stub + return null; + } + + // There are almost certainly other methods we want here, just not sure what +} diff --git a/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java b/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java index 65c013b..666834f 100644 --- a/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java +++ b/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java @@ -17,7 +17,7 @@ public enum TreeLinearizationMethod { */ POSTORDER, /** - * Visit the tree part itself, then the left side of tthis tree part and then + * Visit the tree part itself, then the left side of this tree part and then * the right part. */ PREORDER diff --git a/src/main/java/bjc/funcdata/theory/Category.java b/src/main/java/bjc/funcdata/theory/Category.java new file mode 100644 index 0000000..730465d --- /dev/null +++ b/src/main/java/bjc/funcdata/theory/Category.java @@ -0,0 +1,28 @@ +package bjc.funcdata.theory; + +import java.util.Set; +import java.util.function.Function; + +import bjc.data.Pair; +import bjc.esodata.PairMap; + +// NOTE: haskell uses Category cat: ... where the parameter is the arrow type +public interface Category { + Arrow identity(Element elem); + Arrow compose(Arrow left, Arrow right); +} +// Java objects would form a category as Category, Function> + +class FuncCategory implements Category, Function> { + @Override + public Function identity(Class elem) { + return (vl) -> vl; + } + + @Override + public Function compose(Function left, Function right) { + // right.compose((Function) left); + return null; + } + +} \ No newline at end of file -- cgit v1.2.3