tensort 0.1.0.0 → 0.2.0.0

raw patch · 25 files changed

+1241/−324 lines, 25 filesdep +QuickCheckdep ~basedep ~mtldep ~random

Dependencies added: QuickCheck

Dependency ranges changed: base, mtl, random, time

Files

• CHANGELOG.md +21/−1
• README.md +746/−0
• app/Main.hs +28/−38
• src/Data/Tensort/OtherSorts/Mergesort.hs +16/−16
• src/Data/Tensort/OtherSorts/Quicksort.hs +7/−7
• src/Data/Tensort/Robustsort.hs +8/−8
• src/Data/Tensort/Subalgorithms/Bubblesort.hs +5/−5
• src/Data/Tensort/Subalgorithms/Exchangesort.hs +31/−0
• src/Data/Tensort/Subalgorithms/Permutationsort.hs +5/−5
• src/Data/Tensort/Subalgorithms/ReverseExchangesort.hs +0/−29
• src/Data/Tensort/Subalgorithms/Supersort.hs +9/−9
• src/Data/Tensort/Tensort.hs +28/−25
• src/Data/Tensort/Utils/Check.hs +5/−5
• src/Data/Tensort/Utils/ComparisonFunctions.hs +10/−10
• src/Data/Tensort/Utils/Compose.hs +97/−0
• src/Data/Tensort/Utils/Convert.hs +7/−7
• src/Data/Tensort/Utils/RandomizeList.hs +1/−1
• src/Data/Tensort/Utils/Reduce.hs +4/−4
• src/Data/Tensort/Utils/Render.hs +15/−15
• src/Data/Tensort/Utils/Tensor.hs +0/−101
• src/Data/Tensort/Utils/Types.hs +27/−21
• tensort.cabal +52/−16
• test/Main.hs +65/−1
• test/SortSpec.hs +18/−0
• test/TestCheck.hs +36/−0

@@ -2,4 +2,24 @@  ## 0.1.0.0 -- 2024-05-30 -* First version. Released to an eager world.+* First version. Released to an eager world!++## 0.2.0.0 -- 2024-05-31++* Add Logarithmic Tensort++* Rename and update Exchangesort++* Simplify code and structure++* Cleanup exports++* Cleanup Types++* Improve documentation++* Add to package file++* Expand supported dependency versions++* Add tests

@@ -0,0 +1,746 @@+# Tensort++Tensort is a tensor-based sorting algorithm that is tunable to adjust to +the priorities of the task at hand.++This project started as an exploration of what a sorting algorithm that +prioritizes robustness would look like. As such it also describes and provides+implementations of Robustsort, a group of Tensort variants designed to +prioritize Robustness in conditions defined in David H. Ackley's+[Beyond Efficiency](https://www.cs.unm.edu/~ackley/be-201301131528.pdf).++Note: This project is still under construction. The Library is +functional but I have yet to add documentation and benchmarking.+There's likely a lot of room for improvement in the code as well.++## Table of Contents++- [Introduction](#introduction)+  - [Inspiration](#inspiration)+  - [Why?](#why)+  - [Why Haskell?](#why-haskell)+- [Project structure](#project-structure)+- [Algorithms overview](#algorithms-overview)+  - [Tensort](#tensort-1)+    - [Preface](#preface)+    - [Structure](#structure)+    - [Algorithm](#algorithm)+    - [What are the benefits?](#what-are-the-benefits)+    - [Logarithmic Tensort](#logarithmic-tensort)+  - [Robustsort](#robustsort)+    - [Preface](#preface-1)+    - [Overview](#overview)+    - [Examining Bubblesort](#examining-bubblesort)+    - [Exchangesort](#exchangesort)+    - [Introducing Supersort](#introducing-supersort)+    - [Permutationsort](#permutationsort)+    - [Supersort Adjudication](#supersort-adjudication)+  - [Magicsort](#magicsort)+    - [Supersort adjudication with Magic](#supersort-adjudication-with-magic)+  - [A note on Robustsort and Bogosort](#a-note-on-robustsort-and-bogosort)+- [Comparing it all](#comparing-it-all)+- [Library](#library)++## Introduction++### Inspiration++  - [Beyond Efficiency](https://www.cs.unm.edu/~ackley/be-201301131528.pdf) by +  David H. Ackley+    +  - Future of Coding's +  [podcast episode](https://futureofcoding.org/episodes/070) on the same paper++### Why?++Because near the end of ^that podcast episode, +[Ivan Reese](https://github.com/ivanreese) said "Why are we +comparing Bubblesort versus Quicksort and Mergesort? Well, because no one's +made Robustsort yet." And I thought, "Why not?"++### But why would anyone care about this in the first place?++[Ackley](https://www.cs.unm.edu/~ackley/be-201301131528.pdf) has some really +compelling things to say about this, and I'd highly recommend you read that +paper!++Or listen to [this podcast](https://futureofcoding.org/episodes/070)!++If you want my elevator pitch, it's because we eventually want to build+[Dyson Spheres](https://en.wikipedia.org/wiki/Dyson_sphere). Doing so will +likely involve massively distributed systems being constantly pelted by +radiation. In circumstances like that, robustnesss is key.++Another other example I like to consider is artificial cognition. When working +in a non-determinative system (or a system so complex as to be considered+non-determinative), it can be helpful to have systems in place to make sure +that the answer we come to is really valid.++Incidentally, while I was preparing for this project, we experienced +[the strongest solar storm to reach Earth in 2 decades](https://science.nasa.gov/science-research/heliophysics/how-nasa-tracked-the-most-intense-solar-storm-in-decades/). +I don't know for certain whether the solar activity caused any computer errors, +but we had some anomalies at work and certainly joked about them being caused by+the Sun.++Also during the same period, +[one of the Internet's root-servers glitched out for unexplained reasons](https://arstechnica.com/security/2024/05/dns-glitch-that-threatened-internet-stability-fixed-cause-remains-unclear/).++As Ackley mentions, as a culture we have tended to prioritize correctness and +efficiency to the exclusion of robustness. The rate of our technological +progression precludes us from continuing to do so.++### Why Haskell?++[Obviously](https://www.youtube.com/shorts/LGZKXZQeEBg).++## Project structure++- `src/` contains the Tensort library+    +- `app/` contains the suite for comparing different sorting algorithms in terms of robustness and time efficiency++## Algorithms overview++This README assumes some general knowledge of basic sorting algoritms. If you+would like a refresher, I recommend +[this video](https://www.youtube.com/watch?v=kgBjXUE_Nwc) which touches on +Bubblesort, MergeSort, and Bogosort, and +[this video](https://www.youtube.com/watch?v=XE4VP_8Y0BU) which discusses+Quicksort.++It also assumes you've read +[Beyond Efficiency](https://www.cs.unm.edu/~ackley/be-201301131528.pdf) by +David H. Ackley. Go read it!++Please note that we will discuss a few algorithms that I've either made up or +am just not familiar with by other names. If any of these algorithms have +previously been named, please let me know. Prior to this project I really +only had a rudimentary understanding of Insertionsort, Quicksort, Mergesort,+Bubblesort and Bogosort, so it's entirely possible that I've reinvented a few +things that already exist.++It also may be helpful to note that this project was originally undertaken in+an endeavor to come up with a solution naively, for the practice, before +researching other algorithms built to tackle the same problem. I did very +briefly check out Ackley's +[Demon Horde Sort](https://www.youtube.com/watch?v=helScS3coAE&t=260s), +but only enough (about 5 seconds of that video) to verify that it is different +from this algorithm. I've been purposefully avoiding learning much about Demon +Horde Sort before publishing v1.0.0.0 of this package, but Ackley is way +smarter than me so if you do actually want a real, professional approach to +robust sorting, Demon Horde Sort is likely the place to look.++The algorithms used here that I have made up or renamed are, in order of +introduction, Tensort, Robustsort, Permutationsort, and Magicsort. Get ready!++### Tensort++#### Preface++Tensort is my attempt to write the most robust O(n log n) sorting algorithm +possible while avoiding anything that Ackley might consider a "cheap hack." +My hope is that it will be, if not competitive with Bubblesort in robustness, +at least a major improvement over Quicksort and Mergesort. ++Again, I'm not well-studied in sorting algorithms, so this may well be known +already under another name. After settling on this algorithm, I looked into +several other sorting algorithms for comparison and found a few that I think +are similar - significantly Blocksort, Bucketsort, and Patiencesort. If you are +familiar with these algorithms, you may recognize that they each have a +structure that aids in understanding them.++Tensort uses an underlying structure as well. We will discuss this structure +before going over the algorithm's actual steps. If this doesn't make sense yet,+fear not!++<!-- [image1] -->++#### Structure++  - Bit <- Element of the list to be sorted+    +  - Byte <- List of Bits++  - Bytesize <- Maximum length of a Byte+    +  - Tensor <- Tuple of a Register list and a Memory list+    +  - Memory <- List of Bytes or Tensors contained in the current Tensor.+    +  - Register <- List of Records referencing each Byte or Tensor in Memory+    +  - Record <- Tuple of the Address and the TopBit of the referenced Byte or Tensor+    +  - Address <- Pointer to a Byte or Tensor in Memory+    +  - TopBit <- Value of the Bit at the top of the stack in a Byte or Tensor++  - TensorStack <- A top-level Tensor along with all the Bits, Bytes, and Tensors it contains+    +  - SubAlgorithm <- The sorting sub-algorithm used at various stages++In Tensort, the smallest unit of information is a Bit. Each Bit stores one +element of the list to be sorted. A group of Bits is known as a Byte. ++A Byte is a list of Bits. The maximum length of a Byte is set according to an +argument passed to Tensort. In practice, almost all Bytes will be of maximum +length until the final steps of Tensort. Several Bytes are grouped together +in a Tensor.++A Tensor is a tuple with two elements: Register and Memory.++Memory is the second element in a Tensor tuple. It is a list of Bytes or +other Tensors. The length of this Memory list is equal to the Bytesize.++A Register is the first element in a Tensor tuple. It is a list of Records, +each of which has an Address pointing to an element in its Tensor's Memory +and a copy of the TopBit in the referenced element. These Records are arranged +in the order that the elements of the Tensor's Memory are sorted (this will be +clarified soon).++A TensorStack is a top-level Tensor along with all the Bits, Bytes, and +Tensors it contains. Once the Tensors are fully built, the total number +of TensorStacks will equal the Bytesize, but before that point there will +be many more TensorStacks.++The sorting SubAlgorithm will be used any time we sort something within +Tensort. The choice of this SubAlgorithm is very important. For reasons that +will become clear soon, the SubAlgorithm for Standard Tensort will be +Bubblesort, but the major part of Tensort's tunability is  the ability to +substitute another sorting algorithm based on current priorities.++Now, on to the algorithm!++#### Algorithm++The first step in Tensort is to randomize the input list. I'll explain why we +do this in more detail later - for now just know that it's easier for Tensort +to make mistakes when the list is already nearly sorted.++  1. Randomize the input list of elements (Bits)++  2. Assemble Bytes by sorting the Bits using the SubAlgorithm. After this, we +    will do no more write operations on the Bits until the final steps. Instead, we +    will make copies of the Bits and sort the copies alongside their pointers.++  3. Assemble TensorStacks by creating Tensors from the Bytes. Tensors are +    created by grouping Bytes together (setting them as the Tensor's +    second element), making Records from their top bits, sorting the records, and +    then recording the Pointers from the Records (after being sorted) as the +    Tensor's first element.++  4. Reduce the number of TensorStacks by creating a new layer of Tensors from +    the Tensors created in Step 3. These new Tensors are created by grouping +    the first layer of Tensors together (setting them as the new Tensor's +    second element), making Records from their top Bits, sorting the Records, and +    then recording the Pointers from the Records +    (after being sorted) as the Tensor's first element.++  5. Continue in the same manner as in Step 4 until the number of TensorStacks +    equals the Bytesize++  6. Assemble a top Register by Making Records from the Top Bits on each +    TensorStack and sort the Records.++  7. Remove the Top Bit from the top Byte in the top TensorStack and add it +    to the final Sorted List. If the top Byte has more than one But in it stll, +    Re-sort the Byte for good measure (technically this is +    running the algorithm on different arguments - if anyone wants to me about +    this I'll update this README)++  8. If the top Byte in the top TensorStack is empty, remove the Record that +    points to it from its Tensor's Register. If the Tensor is empty, remove+    the Record that points to it from its Tensor's Register. Do this recursively +    until the Tensor is not empty or the top of the TensorStack is reached. If the +    entire TensorStack is empty of Bits, remove its Record from the top Register. If +    all TensorStacks are empty of Bits, return the final Sorted List. Otherwise, +    re-sort the top Register++  9. Otherwise (the top Byte (or a Tensor that contains it) is not empty), +    update the top Byte's (or Tensor's) Record with its +    new Top Bit and re-sort its Tensor's Register. Then jump up a level to +    the Tensor that contains that Tensor and update the top Tensor's Record+    with its new Top Bit and re-sort its Register. Do this recursively until+    the whole TensorStack is rebalanced. Then update the TensorStack's Record in the +    top Register with its new Top Bit and re-sort the top Register.++Now that we know all the steps, it's easier to see why we randomize the list+as the beginning step. This way, if the list is already nearly +sorted, values close to each other don't get stuck under each other in their +Byte. Ideally, we want the top Bits from all TensorStacks to be close to +each other. Say for example, the first three elements in a 1,000,000-element +list are 121, 122, 123, and 124. If we don't randomize the list, these 3 +elements get grouped together in the first byte. That's all well and good if +everything performs as expected, but if something unexpected happens +during an operation where we intend to add 124 to the final list  +and we add a different element instead, three of the best-case elements to have+mistakenly added (121, 122, and 123) are impossible to have been selected.++#### What are the benefits?++The core idea of Tensort is breaking the input into smaller pieces along an +ever-expanding rank, and sorting the smaller pieces. Once we understand the+overall structure, we can design the SubAlgorithm (and Bytesize) to suit our +needs.++Standard Tensort leverages the robustness of Bubblesort while reducing the time +required by never Bubblesorting the entire input. ++We are able to do this because A) Bubblesort is really good at making sure the +last element is in the final position of a list, and B) at each step of Tensort +the only element we *really* care about is the last element in a given list +(or to look at it another way, the TopBit of a given Tensor).++#### Logarithmic Tensort++When using standard Tensort (i.e. using Bubblesort as the SubAlgoritm), as the +Bytesize approaches the square root of the number of elements in the +input list, its time efficiency approaches O(n^2).++Standard Tensort is most time efficient when the Bytesize is close +to the natural log of the number of elements in the input list. A logarithmic +Bytesize is likely to be ideal for most use cases of standard Tensort.++Alright! Now we have a simple sorting algorithm absent of cheap hacks that is +both relatively fast and relatively robust. I'm pretty happy with that!++<!-- [image2] -->++Now for some cheap hacks!++### Robustsort++#### Preface++In Beyond Efficiency, Ackley augmented Mergesort and Quicksort with what he +called "cheap hacks" in order to give them a boost in robustness to get them to +compare with Bubblesort. This amounted to adding a quorum system to the +unpredictable comparison operator and choosing the most-agreed-upon answer. ++I agree that adding a quorum for the unpredictable comparison operator is a bit +of a cheap hack, or at least a post-hoc solution to a known problem. Instead of +retrying a specific component again because we know it to be unpredictable, +let's build redundancy into the system at the (sub-)algorithmic level. A simple +way to do this is by asking different components the same question and see if +they agree.++Robustsort is my attempt to make the most robust sorting algorithm possible +utilizing some solution-checking on the (sub-)algorithmic level while still:++  - Keeping runtime somewhat reasonable++  - Never re-running a sub-algorithm that is expected to act deterministicly +      on the same arguments looking for a non-deterministic result (i.e. expect +      that if a components gives a wrong answer, running it again won't somehow +      yield a right answer)++  - Using a minimal number of different sub-algorithms (i.e. doesn't just +      use every O(n log n) sorting algorithm I can think of and compare all +      their results)++With those ground rules in place, let's get to Robustsort!++#### Overview++Once we have Tensort in our toolbox, the road to Robustsort is pretty simple. +Robustsort is a 3-bit Tensort with a custom SubAlgorithm that compares other +sub-algorithms. For convenience, we will call this custom SubAlgorithm +Supersort. We use a 3-bit Tensort here because there's something +magical that happens around these numbers.++Robust sorting algorithms tend to be +slow. Bubblesort, for example, has an average time efficiency of O(n^2), +compared with Quicksort and Mergesort, which both have an average of (n log n).++Here's the trick though: with small numbers the difference between these values +is minimal. For example, when n=4, Mergesort will make 6 comparisons, while +Bubblesort will make 12. A Byte holding 4 Bites is both small enough to run +the Bubblesort quickly and large enough to allow multiple opportunities for a +mistake to be corrected. Since we don't as much built-in parallelism in +Tensort, it can make sense to weight more heavily on the side of making more +checks.++In Robustsort, however, we have parallelism built into the Supersort +SubAlgorithm, so we can afford to make less checks during this step. +We choose a Bytesize of +3 because a list of+3 Bits has some special properties. For one thing, sorting at +this length greatly reduces the time it takes to run our slow-but-robust +algorithms. For example, at this size, Bubblesort will make only 6 comparisons. +Mergesort still makes 6 as well.++In addition, when making a mistake while sorting 3 elements, the mistake +will displace an element by only 1 or 2 positions at the, no matter which +algorithm is used.++This is all to say that using a 3-bit byte size allows us to have our pick of +algorithms to compare with!++Note: One might ask why we don't use a Bytesize of 2, since it would be even faster+and still have the same property of displacing an element by only 1 or 2+positions. Well, how many different algorithms can you use to sort 2 elements?+At this length, most algorithms function equivalently (in terms of the +sub-operations performed) and in my mind running two such algorithms is +equivalent to re-running a single algorithm (which violates the requirements +of this project).++#### Examining Bubblesort++Before moving further, let's talk a little about Bubblesort, and why we're +using it in our SubAlgorithm.++As a reminder, Bubblesort will make an average of 6 comparisons when sorting+a 3-element list.++We've said before that Bubblesort is likely to put the last element in the +correct position. Let's examine this in the context of Bubblesorting a +3-element list.++Our implementation of Bubblesort (which mirrors Ackley's) will perform three+iterations over a 3-element list. After the second iteration, if everything+goes as planned, the list will be sorted and the final iteration is an extra+verification step. Therefore, to simplify the analysis, we will consider+what happens with a faulty comparator during the final iteration, assuming the+list has been correctly sorted up to that point.++Given a Byte of [1,2,3], here are the chances of various outcomes from using a +faulty comparator that gives a random result 10% of the time:++    81% <- [1,2,3] (correct - no swaps made)++    9% <- [2,1,3] (faulty first swap)++    9% <- [1,3,2] (faulty second swap)++    1% <- [2,3,1] (faulty first and second swap)++In these cases, 90% of the time the Top Bit will be in the correct position, +and in the other cases it will be off by one position, and in no case will the +Byte be reverse sorted.++#### Exchangesort++When choosing an algorithm to compare with Bubblesort, we want something with +substantially different logic, for the sake of robustness. We do, +however, want something similar to Bubblesort in that it compares our elements +multiple times. And, as mentioned above, the element that is most important to +our sorting is the top (biggest) element, by a large degree.++With these priorities in mind, the comparison algorithm we choose shall be +Exchangesort. If you're not familiar with this algorithm, I'd recommend+checking out [this video](https://youtu.be/wqibJMG42Ik?feature=shared&t=143). ++The Exchangesort we use is notable in two ways. Firstly, it is a Reverse +Exchangesort, as explained in that video.++Secondly, the algorithm as described in the video only compares selected element +with elements that appear after (or before, as in Reverse Exchangesort) it in +the list, swapping them if the compared element is larger. This functions +similarly to an optimized Bubblesort where after the each round the last +element compared that round is no longer compared in following rounds. Our +implementation will compare the selected element with all other elements in the +list, swapping them if the element that appears later is larger. Ackley +uses an unoptimized Bubblesort in Beyond Efficiency, so I feel comfortable +using this variation for our Exchangesort.++Exchangesort will also make an average of 6 comparisons when sorting a+3-element list.++As with Bubblesort, Exchangesort will perform three iterations over a 3-element+list, with the final iteration being redundant.++Given a Byte of [1,2,3], here are the chances of various outcomes from using a +faulty comparator that gives a random result 10% of the time:++    81% <- [1,2,3] (correct - no swaps made)++    9% <- [2,1,3] (faulty first swap)++    9% <- [3,2,1] (faulty second swap)++    1% <- [3,1,2] (faulty first and second swap)++In these cases, 90% of the time the Top Bit will have the correct value. +Notably there is a 9% chance that the Byte will be reverse sorted, but we will +exploit this trait later on in the Supersort SubAlgorithm. Note also that the +only possible outcomes shared between this example and the Bubblesort example+are the correct outcome and [2,1,3], which retains the TopBit with the correct +value.++#### Introducing Supersort++Supersort is a SubAlgorithm that compares the results of two different+sorting algorithms, in our case Bubblesort and Exchangesort. If both +algorithms agree on the result, that result is used. ++Looking at our analysis on Bubblesort and Exchangesort, we can +approximate the chances of various outcomes when comparing the results of +running these two algorithms in similar conditions:++    65.61% <- [1,2,3], [1,2,3] (Agree Correctly)++    7.29% <- [1,2,3], [2,1,3] (Disagree - TopBit agrees correctly)++    7.29% <- [1,2,3], [3,2,1] (Disagree Fully)++    7.29% <- [2,1,3], [1,2,3] (Disagree - TopBit agrees correctly)++    7.29% <- [1,3,2], [1,2,3] (Disagree Fully)++    0.81% <- [2,1,3], [2,1,3] (Agree Incorrectly - TopBit correct)++    0.81% <- [2,1,3], [3,2,1] (Disagree Fully)++    0.81% <- [1,3,2], [2,1,3] (Disagree Fully)++    0.81% <- [1,3,2], [3,2,1] (Disagree Fully)++    0.09% <- [2,1,3], [3,1,2] (Disagree Fully)++    0.09% <- [1,3,2], [3,1,2] (Disagree - TopBit agrees incorrectly)++    0.09% <- [2,3,1], [2,1,3] (Disagree Fully)+  +    0.09% <- [2,3,1], [3,2,1] (Disagree - TopBit agrees incorrectly)++    0.01% <- [2,3,1], [3,1,2] (Disagree Fully)++In total, that makes:++    65.61% <- Agree Correctly++    17.2% <- Disagree Fully++    14.58% <- Disagree - TopBit agrees correctly++    0.81% <- Agree Incorrectly - TopBit correct++    0.18% <- Disagree - TopBit agrees incorrectly++    [no outcome] <- Agree with TopBit incorrect++The first thing that might stand out is that around 34% of the time, these +sub-algorithms will disagree with each other. What happens then?++Well, in that case we run a third sub-algorithm to compare the results with: +Permutationsort.++#### Permutationsort++Permutationsort is a simple, brute-force sorting algorithm. As a first step we +generate all the different ways the elements could possibly be arranged in the +list. Then we loop over this list of permutations until we find one that is in +the right order. We check if a permutation is in the right order by comparing+the first two elements, if they are in the right order comparing the next two+elements, and so on until we either find two elements that are out of order or+we confirm that the list is in order.++Permutationsort will also make an average of 7 comparisons when sorting a +3-element list. This is slightly more than the other algorithms examined but+it's worth it because A) the spread of outcomes is favorable for our needs, and +B) it uses logic that is completely different from Bubblesort and Exchangesort. +Using different manners of reasoning to reach an agreed-upon answer greatly +increases the robustness of the system.++Given a Byte of [1,2,3], here are the chances of various outcomes from using a+faulty comparator that gives a random result 10% of the time:++    ~68.67% <- [1,2,3] (correct)++    ~7.63% <- [2,1,3] (faulty first comparator)+  +    ~7.63% <- [3,1,2] (faulty first comparator)++    ~7.63% <- [1,3,2] (faulty second comparator)++    ~7.63% <- [2,3,1] (faulty second comparator)++    ~0.85% <- [3,2,1] (faulty first and second comparator)++In these cases, 76.6% of the time the Top Bit will be in the correct position. +Notably the least likely outcome is a reverse-sorted Byte and the other +possible incorrect outcomes are in even distribution with each other.++#### Supersort Adjudication++Supposing that our results from Bubblesort and Exchangesort disagree +and we now have our result from Permutationsort, how do we choose which to+use?++First we check to see whether the result from Permutationsort agrees with+the results from either Bubblesort or Exchangesort. To keep things +simple, let's just look at the raw chances that +Permutationsort will agree on results with Bubblesort or Exchangesort.++Permutationsort and Bubblesort:++    ~55.62% <- [1,2,3] (Correct)++    ~0.69% <- [2,1,3] (Correct TopBit)++    ~0.69% <- [1,3,2] (Incorrect)++    ~0.08% <- [2,3,1] (Incorrect)++Permutationsort and Exchangesort:++    ~55.62% <- [1,2,3] (Correct)++    ~0.69% <- [2,1,3] (Correct TopBit)++    ~0.08% <- [3,1,2] (Incorrect)++    ~0.08% <- [3,2,1] (Reverse)++As we can see, it is very unlikely that Permutationsort will agree with+either Bubblesort or Exchangesort incorrectly. It is even less likely+that they will do so when the TopBit is incorrect. However, there are many +cases in which they do not agree, so let's handle those.++If there is no agreed-upon result between these three algorithms, we will look +at the top bit only.++First we check if the results from Bubblesort and Exchangesort agree on the +TopBit. This is because the chance is very unlikely +(0.18%) that they will agree on an incorrect TopBit. If they do agree, we use +the result from Bubblesort (as it will not return a reverse-sorted list).++If they do not agree, we will check the TopBit results from Bubblesort and +Permutationsort. This is because it is unlikely +(~0.92%) that they will agree on an incorrect TopBit, and the chance of them +incorrectly agreeing on the highest Bit as the TopBit is even lower (~0.16%). +If they do agree, we use the result from Bubblesort.++If they do not agree, we will check the TopBit results from Exchangesort +and Permutationsort. The chance that they will agree on an +incorrect TopBit is about 1.55%, with the chances of them incorrectly agreeing+on the highest Bit as the TopBit also around 0.16%. If they do agree, we use+the result from Exchangesort.++If after all this adjudication we still do not have an agreed-upon result, we+will use the result from Bubblesort.++Now obviously we have made some approximations in our analysis (and I may have+made some mistakes in my calculations), but in general I think we can conclude +that it is very unlikely that this Supersort process will return an incorrect +result, and that if an incorrect result is returned, it is very likely to still +have a correct TopBit.++We now have the basic form of Robustsort: a 3-bit Tensort with a Supersort +adjudicating Bubblesort, Exchangesort, and Permutationsort as its+SubAlgorithm.++Well that's pretty cool! But I wonder... can we make this more robust, if +we relax the rules just a little more?++<!-- (image3) -->++Of course we can! And we will. To do so, we will simply replace Permutationsort+with another newly-named sorting algorithm: Magicsort!++### Magicsort++For our most robust iteration of Robustsort we will relax the requirement on+never re-running the same deterministic sub-algorithm in one specific context.+Magicsort is an algorithm that will re-run Permutationsort only if it disagrees +with an extremely reliable algorithm algorithm - one that's so good it's robust +against logic itself...++<!-- (image4) -->++Bogosort!++<!-- (image5) -->++Magicsort simply runs both Permutationsort and Bogosort on the same input and +checks if they agree. If they do, the result is used and if not, both +algorithms are run again. This process is repeated until the two algorithms+agree on a result.++Strong-brained readers may have already deduced that Permutationsort functions+nearly identically to Bogosort. Indeed, their approximate analysis results are+the same. Magicsort is based on the idea that if you happen to pull the right +answer out of a hat once, it might be random chance, but if you do it twice,+it might just be magic!++Given a Byte of [1,2,3], here are the approximate chances of various outcomes +from Magicsort using a faulty comparator that gives a random result 10% of the +time:++    ~95.27% <- [1,2,3] (Correct)++    ~1.18% <- [2,1,3] (Correct TopBit)++    ~1.18% <- [1,3,2] (Incorrect)++    ~1.18% <- [3,1,2] (Incorrect)++    ~1.18% <- [2,3,1] (Incorrect)++    ~0.02% <- [3,2,1] (Reverse)++The downside here is that Magisort can take a long time to run. I don't know +how many comparisons are made on average, but it's well over 14.++Thankfully, Magicsort will only be run in our algorithm if Bubblesort and+Exchangesort disagree on an answer. Overall the Robustsort we're building that +uses Magicsort will still have an average of O(n log n) time efficiency.++#### Supersort adjudication with Magic++Since we have replaced Permutationsort with Magicsort (which is far more robust +than Bubblesort or Exchangesort), we will adjust our adjudication+within the Supersort SubAlgorithm.++If Bubblesort and Exchangesort disagree, we will run Magicsort on the+input. If Magicsort agrees with either Bubblesort or Exchangesort, we+will use the result from Magicsort. Otherwise, if Magicsort agrees on the +TopBit with either Bubblesort or Exchangesort, we will use the result+from Magicsort. Otherwise, if Bubblesort and Exchangesort agree on the+TopBit, we will use the result from Bubblesort.++If no agreement is reached at this point, we abandon all logic and just use+Magicsort.++### A note on Robustsort and Bogosort++It is perfectly valid to use Bogosort in place of Permutationsort in Robustsort's +standard Supersort SubAlgorithm. It may be argued that doing so is even more +robust, since it barely even relies on logic. Here are some considerations to+keep in mind:++  - Permutationsort uses additional space and may take slightly longer on average +      due to computing all possible permutations of the input and storing them in a +      list.++  - Bogosort could theoretically run forever without returning a result, even +      when no errors occur.+  +## Comparing it all++Now let's take a look at how everything compares. Here is a graph showing the +benchmarking results in both in both robustness and time efficiency for +Quicksort, Mergesort, Standard Logarithmic Tensort, Robustsort (Permutations), +Robustsort (Bogo), Robustsort (Magic), and Bubblesort:++...Coming Soon!++## Library++This package contains implementations of each algorithm discussed above. +Notably, it provides the following:++  - Customizable Tensort++  - Standard Logarithmic Tensort++  - Standard Tensort with customizable Bytesize++  - Mundane Robustsort with Permutationsort adjudicator++  - Mundane Robustsort with Bogosort adjudicator++  - Magic Robustsort++Check the code in `src/` or the documentation on Hackage/Hoogle (Coming Soon!) +for more details.

@@ -4,71 +4,61 @@ import Data.Tensort.OtherSorts.Quicksort (quicksort) import Data.Tensort.Robustsort (robustsortB, robustsortM, robustsortP) import Data.Tensort.Subalgorithms.Bubblesort (bubblesort)-import Data.Tensort.Tensort (tensortBasic2Bit, tensortBasic3Bit, tensortBasic4Bit)+import Data.Tensort.Tensort (tensortB4, tensortBL) import Data.Tensort.Utils.RandomizeList (randomizeList)-import Data.Tensort.Utils.Types (Sortable (..), fromSortInt)+import Data.Tensort.Utils.Types (Sortable (..), fromSortBit) import Data.Time.Clock -unsortedInts :: [Int]-unsortedInts = [2, 5, 10, 4, 15, 11, 7, 14, 16, 6, 13, 3, 8, 9, 12, 1]--unsortedInts52 :: Sortable-unsortedInts52 = randomizeList (SortInt [1 .. 52]) 143--unsortedInts1000 :: Sortable-unsortedInts1000 = randomizeList (SortInt [1 .. 1000]) 143--unsortedInts10000 :: Sortable-unsortedInts10000 = randomizeList (SortInt [1 .. 10000]) 143+unsortedBits :: [Int]+unsortedBits = [2, 5, 10, 4, 15, 11, 7, 14, 16, 6, 13, 3, 8, 9, 12, 1] -unsortedInts100000 :: Sortable-unsortedInts100000 = randomizeList (SortInt [1 .. 100000]) 143+genUnsortedBits :: Int -> Sortable+genUnsortedBits n = randomizeList (SortBit [1 .. n]) 143  main :: IO () main = do-  printTime unsortedInts52-  printTime unsortedInts1000-  printTime unsortedInts10000-  printTime unsortedInts100000+  printTimes (map genUnsortedBits [52, 1000, 10000, 50000, 100000]) +printTimes :: [Sortable] -> IO ()+printTimes [] = return ()+printTimes (x : xs) = do+  printTime x+  printTimes xs+ printTime :: Sortable -> IO () printTime l = do   putStr " Algorithm   | Time         | n ="-  startTensort2Bit <- getCurrentTime-  putStrLn (" " ++ show (length (tensortBasic2Bit (fromSortInt l))))-  endTensort2Bit <- getCurrentTime-  putStr (" Tensort2Bit | " ++ show (diffUTCTime endTensort2Bit startTensort2Bit) ++ " | ")-  startTensort3Bit <- getCurrentTime-  putStrLn ("    " ++ show (length (tensortBasic3Bit (fromSortInt l))))-  endTensort3Bit <- getCurrentTime-  putStr (" Tensort3Bit | " ++ show (diffUTCTime endTensort3Bit startTensort3Bit) ++ " | ")-  startTensort4Bit <- getCurrentTime-  putStrLn ("    " ++ show (length (tensortBasic4Bit (fromSortInt l))))-  endTensort4Bit <- getCurrentTime-  putStr (" Tensort4Bit | " ++ show (diffUTCTime endTensort4Bit startTensort4Bit) ++ " | ")+  startTensortB4 <- getCurrentTime+  putStrLn (" " ++ show (length (tensortB4 (fromSortBit l))))+  endTensortB4 <- getCurrentTime+  putStr (" Tensort4Bit | " ++ show (diffUTCTime endTensortB4 startTensortB4) ++ " | ")+  startTensortBL <- getCurrentTime+  putStrLn ("    " ++ show (length (tensortBL (fromSortBit l))))+  endTensortBL <- getCurrentTime+  putStr (" tensortBL   | " ++ show (diffUTCTime endTensortBL startTensortBL) ++ " | ")   startRSortP <- getCurrentTime-  putStrLn ("    " ++ show (length (robustsortP (fromSortInt l))))+  putStrLn ("    " ++ show (length (robustsortP (fromSortBit l))))   endRSortP <- getCurrentTime   putStr (" RobustsortP | " ++ show (diffUTCTime endRSortP startRSortP) ++ " | ")   startRSortB <- getCurrentTime-  putStrLn ("    " ++ show (length (robustsortB (fromSortInt l))))+  putStrLn ("    " ++ show (length (robustsortB (fromSortBit l))))   endRSortB <- getCurrentTime   putStr (" RobustsortB | " ++ show (diffUTCTime endRSortB startRSortB) ++ " | ")   startRSortM <- getCurrentTime-  putStrLn ("    " ++ show (length (robustsortM (fromSortInt l))))+  putStrLn ("    " ++ show (length (robustsortM (fromSortBit l))))   endRSortM <- getCurrentTime   putStr (" RobustsortM | " ++ show (diffUTCTime endRSortM startRSortM) ++ " | ")   startMergesort <- getCurrentTime-  putStrLn ("    " ++ show (length (fromSortInt (mergesort l))))+  putStrLn ("    " ++ show (length (fromSortBit (mergesort l))))   endMergesort <- getCurrentTime   putStr (" Mergesort   | " ++ show (diffUTCTime endMergesort startMergesort) ++ " | ")   startQuicksort <- getCurrentTime-  putStrLn ("    " ++ show (length (fromSortInt (quicksort l))))+  putStrLn ("    " ++ show (length (fromSortBit (quicksort l))))   endQuicksort <- getCurrentTime   putStr (" Quicksort   | " ++ show (diffUTCTime endQuicksort startQuicksort) ++ " | ")   startBubblesort <- getCurrentTime-  putStrLn ("    " ++ show (length (fromSortInt (bubblesort l))))+  putStrLn ("    " ++ show (length (fromSortBit (bubblesort l))))   endBubblesort <- getCurrentTime   putStr (" Bubblesort  | " ++ show (diffUTCTime endBubblesort startBubblesort) ++ " | ")-  putStrLn ("    " ++ show (length (fromSortInt (bubblesort l))))+  putStrLn ("    " ++ show (length (fromSortBit (bubblesort l))))   putStrLn "----------------------------------------------------------"

@@ -1,29 +1,29 @@ module Data.Tensort.OtherSorts.Mergesort (mergesort) where -import Data.Tensort.Utils.ComparisonFunctions (lessThanInt, lessThanRecord)-import Data.Tensort.Utils.Types (Record, Sortable (..))+import Data.Tensort.Utils.ComparisonFunctions (lessThanBit, lessThanRecord)+import Data.Tensort.Utils.Types (Record, Sortable (..), Bit)  mergesort :: Sortable -> Sortable-mergesort (SortInt xs) = SortInt (mergesortInts xs)+mergesort (SortBit xs) = SortBit (mergesortBits xs) mergesort (SortRec xs) = SortRec (mergesortRecs xs) -mergesortInts :: [Int] -> [Int]-mergesortInts = mergeAllInts . map (: [])+mergesortBits :: [Bit] -> [Bit]+mergesortBits = mergeAllBits . map (: [])   where-    mergeAllInts [] = []-    mergeAllInts [x] = x-    mergeAllInts [x, y] = mergeInts x y-    mergeAllInts remaningElements = mergeAllInts (mergePairs remaningElements)+    mergeAllBits [] = []+    mergeAllBits [x] = x+    mergeAllBits [x, y] = mergeBits x y+    mergeAllBits remaningElements = mergeAllBits (mergePairs remaningElements) -    mergePairs (x : y : remaningElements) = mergeInts x y : mergePairs remaningElements+    mergePairs (x : y : remaningElements) = mergeBits x y : mergePairs remaningElements     mergePairs x = x -mergeInts :: [Int] -> [Int] -> [Int]-mergeInts [] y = y-mergeInts x [] = x-mergeInts (x : xs) (y : ys)-  | lessThanInt x y = x : mergeInts xs (y : ys)-  | otherwise = y : mergeInts (x : xs) ys+mergeBits :: [Bit] -> [Bit] -> [Bit]+mergeBits [] y = y+mergeBits x [] = x+mergeBits (x : xs) (y : ys)+  | lessThanBit x y = x : mergeBits xs (y : ys)+  | otherwise = y : mergeBits (x : xs) ys  mergesortRecs :: [Record] -> [Record] mergesortRecs = mergeAllRecs . map (: [])

@@ -1,14 +1,14 @@ module Data.Tensort.OtherSorts.Quicksort (quicksort) where -import Data.Tensort.Utils.ComparisonFunctions (greaterThanInt, greaterThanRecord, lessThanOrEqualInt, lessThanOrEqualRecord)-import Data.Tensort.Utils.Types (Sortable (..), fromSortInt, fromSortRec)+import Data.Tensort.Utils.ComparisonFunctions (greaterThanBit, greaterThanRecord, lessThanOrEqualBit, lessThanOrEqualRecord)+import Data.Tensort.Utils.Types (Sortable (..), fromSortBit, fromSortRec)  quicksort :: Sortable -> Sortable-quicksort (SortInt []) = SortInt []-quicksort (SortInt (x : xs)) =-  let lowerPartition = quicksort (SortInt [a | a <- xs, lessThanOrEqualInt a x])-      upperPartition = quicksort (SortInt [a | a <- xs, greaterThanInt a x])-   in SortInt (fromSortInt lowerPartition ++ [x] ++ fromSortInt upperPartition)+quicksort (SortBit []) = SortBit []+quicksort (SortBit (x : xs)) =+  let lowerPartition = quicksort (SortBit [a | a <- xs, lessThanOrEqualBit a x])+      upperPartition = quicksort (SortBit [a | a <- xs, greaterThanBit a x])+   in SortBit (fromSortBit lowerPartition ++ [x] ++ fromSortBit upperPartition) quicksort (SortRec []) = SortRec [] quicksort (SortRec (x : xs)) =   let lowerPartition = quicksort (SortRec [a | a <- xs, lessThanOrEqualRecord a x])

@@ -9,25 +9,25 @@ import Data.Tensort.Subalgorithms.Bubblesort (bubblesort) import Data.Tensort.Subalgorithms.Magicsort (magicsort) import Data.Tensort.Subalgorithms.Permutationsort (permutationsort)-import Data.Tensort.Subalgorithms.ReverseExchangesort (reverseExchangesort)+import Data.Tensort.Subalgorithms.Exchangesort (exchangesort) import Data.Tensort.Subalgorithms.Supersort (magicSuperStrat, mundaneSuperStrat, supersort) import Data.Tensort.Tensort (mkTSProps, tensort)-import Data.Tensort.Utils.Types (Sortable)+import Data.Tensort.Utils.Types (Sortable, Bit) -robustsortP :: [Int] -> [Int]+robustsortP :: [Bit] -> [Bit] robustsortP xs = tensort xs (mkTSProps 3 supersortP)  supersortP :: Sortable -> Sortable-supersortP xs = supersort xs (bubblesort, reverseExchangesort, permutationsort, mundaneSuperStrat)+supersortP xs = supersort xs (bubblesort, exchangesort, permutationsort, mundaneSuperStrat) -robustsortB :: [Int] -> [Int]+robustsortB :: [Bit] -> [Bit] robustsortB xs = tensort xs (mkTSProps 3 supersortB)  supersortB :: Sortable -> Sortable-supersortB xs = supersort xs (bubblesort, reverseExchangesort, bogosort, mundaneSuperStrat)+supersortB xs = supersort xs (bubblesort, exchangesort, bogosort, mundaneSuperStrat) -robustsortM :: [Int] -> [Int]+robustsortM :: [Bit] -> [Bit] robustsortM xs = tensort xs (mkTSProps 3 supersortM)  supersortM :: Sortable -> Sortable-supersortM xs = supersort xs (bubblesort, reverseExchangesort, magicsort, magicSuperStrat)+supersortM xs = supersort xs (bubblesort, exchangesort, magicsort, magicSuperStrat)

@@ -1,13 +1,13 @@ module Data.Tensort.Subalgorithms.Bubblesort (bubblesort) where -import Data.Tensort.Utils.ComparisonFunctions (lessThanInt, lessThanRecord)-import Data.Tensort.Utils.Types (Record, Sortable (..))+import Data.Tensort.Utils.ComparisonFunctions (lessThanBit, lessThanRecord)+import Data.Tensort.Utils.Types (Record, Sortable (..), Bit)  bubblesort :: Sortable -> Sortable-bubblesort (SortInt ints) = SortInt (foldr acc [] ints)+bubblesort (SortBit bits) = SortBit (foldr acc [] bits)   where-    acc :: Int -> [Int] -> [Int]-    acc x xs = bubblesortSinglePass x xs lessThanInt+    acc :: Bit -> [Bit] -> [Bit]+    acc x xs = bubblesortSinglePass x xs lessThanBit bubblesort (SortRec recs) = SortRec (foldr acc [] recs)   where     acc :: Record -> [Record] -> [Record]

@@ -0,0 +1,31 @@+module Data.Tensort.Subalgorithms.Exchangesort (exchangesort) where++import Data.Tensort.Utils.ComparisonFunctions (greaterThanBit, greaterThanRecord)+import Data.Tensort.Utils.Types (Sortable (..))++exchangesort :: Sortable -> Sortable+exchangesort (SortBit bits) = SortBit (exchangesortIterable bits (length bits - 1) (length bits - 2) greaterThanBit)+exchangesort (SortRec recs) = SortRec (exchangesortIterable recs (length recs - 1) (length recs - 2) greaterThanRecord)++exchangesortIterable :: [a] -> Int -> Int -> (a -> a -> Bool) -> [a]+exchangesortIterable xs i j greaterThan = do+  if i < 0+    then xs+    else+      if j < 0+        then exchangesortIterable xs (i - 1) (length xs - 1) greaterThan+        else+          if ((i > j) && greaterThan (xs !! j) (xs !! i)) || ((j > i) && greaterThan (xs !! i) (xs !! j))+            then exchangesortIterable (swap xs i j) i (j - 1) greaterThan+            else exchangesortIterable xs i (j - 1) greaterThan++swap :: [a] -> Int -> Int -> [a]+swap xs i j = do+  let x = xs !! i+  let y = xs !! j+  let mini = min i j+  let maxi = max i j+  let left = take mini xs+  let middle = take (maxi - mini - 1) (drop (mini + 1) xs)+  let right = drop (maxi + 1) xs+  left ++ [y] ++ middle ++ [x] ++ right

@@ -2,16 +2,16 @@  import Data.List (permutations) import Data.Tensort.Utils.Check (isSorted)-import Data.Tensort.Utils.Types (Record, Sortable (..), fromSortInt, fromSortRec)+import Data.Tensort.Utils.Types (Record, Sortable (..), fromSortBit, fromSortRec, Bit)  permutationsort :: Sortable -> Sortable-permutationsort (SortInt xs) = SortInt (acc (permutations x) [])+permutationsort (SortBit xs) = SortBit (acc (permutations x) [])   where     x = xs-    acc :: [[Int]] -> [Int] -> [Int]-    acc [] unsortedPermutations = fromSortInt (permutationsort (SortInt unsortedPermutations))+    acc :: [[Bit]] -> [Bit] -> [Bit]+    acc [] unsortedPermutations = fromSortBit (permutationsort (SortBit unsortedPermutations))     acc (permutation : remainingPermutations) unsortedPermutations-      | isSorted (SortInt permutation) = permutation+      | isSorted (SortBit permutation) = permutation       | otherwise = acc remainingPermutations unsortedPermutations permutationsort (SortRec xs) = SortRec (acc (permutations x) [])   where

@@ -1,29 +0,0 @@-module Data.Tensort.Subalgorithms.ReverseExchangesort (reverseExchangesort) where--import Data.Tensort.Utils.ComparisonFunctions (greaterThanInt, greaterThanRecord)-import Data.Tensort.Utils.Types (Sortable (..))--reverseExchangesort :: Sortable -> Sortable-reverseExchangesort (SortInt ints) = SortInt (reverseExchangesortIterable ints (length ints - 1) (length ints - 2) greaterThanInt)-reverseExchangesort (SortRec recs) = SortRec (reverseExchangesortIterable recs (length recs - 1) (length recs - 2) greaterThanRecord)--reverseExchangesortIterable :: [a] -> Int -> Int -> (a -> a -> Bool) -> [a]-reverseExchangesortIterable xs i j greaterThan = do-  if i < 1-    then xs-    else-      if j < 0-        then reverseExchangesortIterable xs (i - 1) (i - 2) greaterThan-        else-          if greaterThan (xs !! j) (xs !! i)-            then reverseExchangesortIterable (swap xs i j) i (j - 1) greaterThan-            else reverseExchangesortIterable xs i (j - 1) greaterThan--swap :: [a] -> Int -> Int -> [a]-swap xs i j = do-  let x = xs !! i-  let y = xs !! j-  let left = take j xs-  let middle = take (i - j - 1) (drop (j + 1) xs)-  let right = drop (i + 1) xs-  left ++ [y] ++ middle ++ [x] ++ right

@@ -16,16 +16,16 @@     else superStrat (result1, result2, subAlg3 xs)  mundaneSuperStrat :: SupersortStrat-mundaneSuperStrat (SortInt result1, SortInt result2, SortInt result3) = do+mundaneSuperStrat (SortBit result1, SortBit result2, SortBit result3) = do   if result1 == result3 || result2 == result3-    then SortInt result3+    then SortBit result3     else       if last result1 == last result2 || last result1 == last result3-        then SortInt result1+        then SortBit result1         else           if last result2 == last result3-            then SortInt result2-            else SortInt result1+            then SortBit result2+            else SortBit result1 mundaneSuperStrat (SortRec result1, SortRec result2, SortRec result3) = do   if result1 == result3 || result2 == result3     then SortRec result3@@ -39,13 +39,13 @@ mundaneSuperStrat (_, _, _) = error "All three inputs must be of the same type."  magicSuperStrat :: SupersortStrat-magicSuperStrat (SortInt result1, SortInt result2, SortInt result3) = do+magicSuperStrat (SortBit result1, SortBit result2, SortBit result3) = do   if last result1 == last result3 || last result2 == last result3-    then SortInt result3+    then SortBit result3     else       if last result1 == last result2-        then SortInt result1-        else SortInt result3+        then SortBit result1+        else SortBit result3 magicSuperStrat (SortRec result1, SortRec result2, SortRec result3) = do   if last result1 == last result3 || last result2 == last result3     then SortRec result3

@@ -1,41 +1,44 @@ module Data.Tensort.Tensort   ( tensort,-    tensortBasic2Bit,-    tensortBasic3Bit,-    tensortBasic4Bit,+    tensortB4,+    tensortBN,+    tensortBL,     mkTSProps,   ) where  import Data.Tensort.Subalgorithms.Bubblesort (bubblesort)+import Data.Tensort.Utils.Compose (createInitialTensors) import Data.Tensort.Utils.Convert (rawBitsToBytes) import Data.Tensort.Utils.RandomizeList (randomizeList) import Data.Tensort.Utils.Reduce (reduceTensorStacks)-import Data.Tensort.Utils.Render (getSortedBitsFromMetastack)-import Data.Tensort.Utils.Tensor (getTensorStacksFromBytes)-import Data.Tensort.Utils.Types (Sortable (..), TensortProps (..), fromSortInt)--mkTSProps :: Int -> (Sortable -> Sortable) -> TensortProps-mkTSProps bSize subAlg = TensortProps {bytesize = bSize, subAlgorithm = subAlg}--tensortBasic2Bit :: [Int] -> [Int]-tensortBasic2Bit xs = tensort xs (mkTSProps 2 bubblesort)--tensortBasic3Bit :: [Int] -> [Int]-tensortBasic3Bit xs = tensort xs (mkTSProps 3 bubblesort)--tensortBasic4Bit :: [Int] -> [Int]-tensortBasic4Bit xs = tensort xs (mkTSProps 4 bubblesort)+import Data.Tensort.Utils.Render (getSortedBitsFromTensor)+import Data.Tensort.Utils.Types (Sortable (..), TensortProps (..), fromSortBit, SortAlg, Bit) --- | Sort a list of Ints using the Tensort algorithm+-- | Sort a list of Bits using the Tensort algorithm  -- | ==== __Examples__ -- >>> tensort (randomizeList [1..100] 143) 2 -- [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]-tensort :: [Int] -> TensortProps -> [Int]+tensort :: [Bit] -> TensortProps -> [Bit] tensort xs tsProps = do-  let bits = randomizeList (SortInt xs) 143-  let bytes = rawBitsToBytes (fromSortInt bits) tsProps-  let tensorStacks = getTensorStacksFromBytes bytes tsProps-  let metastack = reduceTensorStacks tensorStacks tsProps-  getSortedBitsFromMetastack metastack (subAlgorithm tsProps)+  let bits = randomizeList (SortBit xs) 143+  let bytes = rawBitsToBytes (fromSortBit bits) tsProps+  let tensorStacks = createInitialTensors bytes tsProps+  let topTensor = reduceTensorStacks tensorStacks tsProps+  getSortedBitsFromTensor topTensor (subAlgorithm tsProps)++mkTSProps :: Int -> SortAlg -> TensortProps+mkTSProps bSize subAlg = TensortProps {bytesize = bSize, subAlgorithm = subAlg}++tensortB4 :: [Bit] -> [Bit]+tensortB4 xs = tensort xs (mkTSProps 4 bubblesort)++tensortBN :: Int -> [Bit] -> [Bit]+tensortBN n xs = tensort xs (mkTSProps n bubblesort)++tensortBL :: [Bit] -> [Bit]+tensortBL xs = tensort xs (mkTSProps (calculateBytesize xs) bubblesort)++calculateBytesize :: [Bit] -> Int+calculateBytesize xs = ceiling (log (fromIntegral (length xs)) :: Double)

@@ -1,12 +1,12 @@ module Data.Tensort.Utils.Check (isSorted) where -import Data.Tensort.Utils.ComparisonFunctions (lessThanInt, lessThanRecord)+import Data.Tensort.Utils.ComparisonFunctions (lessThanOrEqualBit, lessThanOrEqualRecord) import Data.Tensort.Utils.Types (Sortable (..))  isSorted :: Sortable -> Bool-isSorted (SortInt []) = True-isSorted (SortInt [_]) = True-isSorted (SortInt (x : y : remainingElements)) = lessThanInt x y && isSorted (SortInt (y : remainingElements))+isSorted (SortBit []) = True+isSorted (SortBit [_]) = True+isSorted (SortBit (x : y : remainingElements)) = lessThanOrEqualBit x y && isSorted (SortBit (y : remainingElements)) isSorted (SortRec []) = True isSorted (SortRec [_]) = True-isSorted (SortRec (x : y : remainingElements)) = lessThanRecord x y && isSorted (SortRec (y : remainingElements))+isSorted (SortRec (x : y : remainingElements)) = lessThanOrEqualRecord x y && isSorted (SortRec (y : remainingElements))

@@ -1,29 +1,29 @@ module Data.Tensort.Utils.ComparisonFunctions-  ( lessThanInt,+  ( lessThanBit,     lessThanRecord,-    greaterThanInt,+    greaterThanBit,     greaterThanRecord,-    lessThanOrEqualInt,+    lessThanOrEqualBit,     lessThanOrEqualRecord,   ) where -import Data.Tensort.Utils.Types (Record)+import Data.Tensort.Utils.Types (Record, Bit) -lessThanInt :: Int -> Int -> Bool-lessThanInt x y = x < y+lessThanBit :: Bit -> Bit -> Bool+lessThanBit x y = x < y  lessThanRecord :: Record -> Record -> Bool lessThanRecord x y = snd x < snd y -greaterThanInt :: Int -> Int -> Bool-greaterThanInt x y = x > y+greaterThanBit :: Bit -> Bit -> Bool+greaterThanBit x y = x > y  greaterThanRecord :: Record -> Record -> Bool greaterThanRecord x y = snd x > snd y -lessThanOrEqualInt :: Int -> Int -> Bool-lessThanOrEqualInt x y = x <= y+lessThanOrEqualBit :: Bit -> Bit -> Bool+lessThanOrEqualBit x y = x <= y  lessThanOrEqualRecord :: Record -> Record -> Bool lessThanOrEqualRecord x y = snd x <= snd y

@@ -0,0 +1,97 @@+module Data.Tensort.Utils.Compose+  ( createInitialTensors,+    createTensor,+  )+where++import Data.Tensort.Utils.Split (splitEvery)+import Data.Tensort.Utils.Types (Byte, Memory (..), Record, SortAlg, Sortable (..), Tensor, TensortProps (..), fromSortRec, Bit)++-- | Convert a list of Bytes to a list of TensorStacks.++-- | This is accomplished by making a Tensor for each Byte, converting that+--   Tensor into a TensorStack (these are equivalent terms - see type+--   definitions for more info) and collating the TensorStacks into a list++-- | ==== __Examples__+--  >>> createInitialTensors [[2,4],[6,8],[1,3],[5,7]] 2+--  [([(0,3),(1,7)],ByteMem [[1,3],[5,7]]),([(0,4),(1,8)],ByteMem [[2,4],[6,8]])]+createInitialTensors :: [Byte] -> TensortProps -> [Tensor]+createInitialTensors bytes tsProps = foldr acc [] (splitEvery (bytesize tsProps) bytes)+  where+    acc :: [Byte] -> [Tensor] -> [Tensor]+    acc byte tensorStacks = tensorStacks ++ [getTensorFromBytes byte (subAlgorithm tsProps)]++-- | Create a Tensor from a Memory+--   Aliases to getTensorFromBytes for ByteMem and getTensorFromTensors for+--   TensorMem+createTensor :: Memory -> SortAlg -> Tensor+createTensor (ByteMem bytes) subAlg = getTensorFromBytes bytes subAlg+createTensor (TensorMem tensors) subAlg = getTensorFromTensors tensors subAlg++-- | Convert a list of Bytes to a Tensor++-- | We do this by loading the list of Bytes into the new Tensor's Memory+--   and adding a sorted Register containing References to each Byte in Memory++-- | Each Record contains an Address pointing to the index of the referenced+--   Byte and a TopBit containing the value of the last (i.e. highest) Bit in+--   the referenced Byte++-- | The Register is sorted by the TopBits of each Record++-- | ==== __Examples__+--  >>> getTensorFromBytes [[2,4,6,8],[1,3,5,7]]+--  ([(1,7),(0,8)],ByteMem [[2,4,6,8],[1,3,5,7]])+getTensorFromBytes :: [Byte] -> SortAlg -> Tensor+getTensorFromBytes bytes subAlg = do+  let register = acc bytes [] 0+  let register' = fromSortRec (subAlg (SortRec register))+  (register', ByteMem bytes)+  where+    acc :: [Byte] -> [Record] -> Int -> [Record]+    acc [] register _ = register+    acc ([] : remainingBytes) register i = acc remainingBytes register (i + 1)+    acc (byte : remainingBytes) register i = acc remainingBytes (register ++ [(i, last byte)]) (i + 1)++-- | Create a TensorStack with the collated and sorted References from the+--   Tensors as the Register and the original Tensors as the data++-- | ==== __Examples__+-- >>> getTensorFromTensors [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(1,14),(0,17)],ByteMem [[16,17],[12,14]])]+-- ([(1,17),(0,18)],TensorMem [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(1,14),(0,17)],ByteMem [[16,17],[12,14]])])+getTensorFromTensors :: [Tensor] -> SortAlg -> Tensor+getTensorFromTensors tensors subAlg = (fromSortRec (subAlg (SortRec (getRegisterFromTensors tensors))), TensorMem tensors)++-- | For each Tensor, produces a Record by combining the top bit of the+--  Tensor with an index value for its Address++-- | Note that this output is not sorted. Sorting is done in the+--   getTensorFromTensors function++-- | ==== __Examples__+-- >>> getRegisterFromTensors [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(0,14),(1,17)],ByteMem [[12,14],[16,17]]),([(0,3),(1,7)],ByteMem [[1,3],[5,7]]),([(0,4),(1,8)],ByteMem [[2,4],[6,8]])]+-- [(0,18),(1,17),(2,7),(3,8)]+getRegisterFromTensors :: [Tensor] -> [Record]+getRegisterFromTensors tensors = acc tensors []+  where+    acc :: [Tensor] -> [Record] -> [Record]+    acc [] records = records+    acc (([], _) : remainingTensors) records = acc remainingTensors records+    acc (tensor : remainingTensors) records = acc remainingTensors (records ++ [(i, getTopBitFromTensorStack tensor)])+      where+        i = length records++-- | Get the top Bit from a TensorStack++-- | The top Bit is the last Bit in the last Byte referenced in the last record+--   of the Tensor referenced in the last record of the last Tensor of...+--   and so on until you reach the top level of the TensorStack++-- | This is also expected to be the highest value in the TensorStack++-- | ==== __Examples__+-- >>> getTopBitFromTensorStack (([(0,28),(1,38)],TensorMem [([(0,27),(1,28)],TensorMem [([(0,23),(1,27)],ByteMem [[21,23],[25,27]]),([(0,24),(1,28)],ByteMem [[22,24],[26,28]])]),([(1,37),(0,38)],TensorMem [([(0,33),(1,38)],ByteMem [[31,33],[35,38]]),([(0,34),(1,37)],ByteMem [[32,14],[36,37]])])]))+-- 38+getTopBitFromTensorStack :: Tensor -> Bit+getTopBitFromTensorStack (register, _) = snd (last register)

@@ -1,7 +1,7 @@ module Data.Tensort.Utils.Convert (rawBitsToBytes) where  import Data.Tensort.Utils.Split (splitEvery)-import Data.Tensort.Utils.Types (Byte, Sortable (..), TensortProps (..), fromSortInt)+import Data.Tensort.Utils.Types (Byte, Sortable (..), TensortProps (..), fromSortBit, Bit)  -- | Convert a list of Bits to a list of Bytes of given bytesize, bubblesorting --   each byte.@@ -9,13 +9,13 @@ -- | ==== __Examples__ --   >>> rawBitsToBytes [5,1,3,7,8,2,4,6] 4 --   [[2,4,6,8],[1,3,5,7]]--- rawBitsToBytes :: [Int] -> Int -> [Byte]+-- rawBitsToBytes :: [Bit] -> Int -> [Byte] -- rawBitsToBytes bits bytesize = foldr acc [] (splitEvery bytesize bits) --   where---     acc :: [Int] -> [Byte] -> [Byte]---     acc byte bytes = bytes ++ [fromSortInt (bubblesort (SortInt byte))]-rawBitsToBytes :: [Int] -> TensortProps -> [Byte]+--     acc :: [Bit] -> [Byte] -> [Byte]+--     acc byte bytes = bytes ++ [fromSortBit (bubblesort (SortBit byte))]+rawBitsToBytes :: [Bit] -> TensortProps -> [Byte] rawBitsToBytes bits tsProps = foldr acc [] (splitEvery (bytesize tsProps) bits)   where-    acc :: [Int] -> [Byte] -> [Byte]-    acc byte bytes = bytes ++ [fromSortInt (subAlgorithm tsProps (SortInt byte))]+    acc :: [Bit] -> [Byte] -> [Byte]+    acc byte bytes = bytes ++ [fromSortBit (subAlgorithm tsProps (SortBit byte))]

@@ -5,5 +5,5 @@ import System.Random.Shuffle (shuffle')  randomizeList :: Sortable -> Int -> Sortable-randomizeList (SortInt xs) seed = SortInt (shuffle' xs (length xs) (mkStdGen seed))+randomizeList (SortBit xs) seed = SortBit (shuffle' xs (length xs) (mkStdGen seed)) randomizeList (SortRec xs) seed = SortRec (shuffle' xs (length xs) (mkStdGen seed))

@@ -1,8 +1,8 @@ module Data.Tensort.Utils.Reduce (reduceTensorStacks) where +import Data.Tensort.Utils.Compose (createTensor) import Data.Tensort.Utils.Split (splitEvery)-import Data.Tensort.Utils.Tensor (createTensorStack)-import Data.Tensort.Utils.Types (TensorStack, TensortProps (..))+import Data.Tensort.Utils.Types (Memory (..), TensorStack, TensortProps (..))  -- | Take a list of TensorStacks and group them together in new --   TensorStacks, each containing bytesize number of Tensors (former@@ -17,7 +17,7 @@ reduceTensorStacks tensorStacks tsProps = do   let newTensorStacks = reduceTensorStacksSinglePass tensorStacks tsProps   if length newTensorStacks <= bytesize tsProps-    then createTensorStack newTensorStacks (subAlgorithm tsProps)+    then createTensor (TensorMem newTensorStacks) (subAlgorithm tsProps)     else reduceTensorStacks newTensorStacks tsProps  -- | Take a list of TensorStacks  and group them together in new@@ -32,4 +32,4 @@ reduceTensorStacksSinglePass tensorStacks tsProps = foldr acc [] (splitEvery (bytesize tsProps) tensorStacks)   where     acc :: [TensorStack] -> [TensorStack] -> [TensorStack]-    acc tensorStack newTensorStacks = newTensorStacks ++ [createTensorStack tensorStack (subAlgorithm tsProps)]+    acc tensorStack newTensorStacks = newTensorStacks ++ [createTensor (TensorMem tensorStack) (subAlgorithm tsProps)]

@@ -1,26 +1,26 @@-module Data.Tensort.Utils.Render (getSortedBitsFromMetastack) where+module Data.Tensort.Utils.Render (getSortedBitsFromTensor) where  import Data.Maybe (isNothing)-import Data.Tensort.Utils.Tensor (createTensor)-import Data.Tensort.Utils.Types (Memory (..), SortAlg, Sortable (..), Tensor, TensorStack, fromJust, fromSortInt)+import Data.Tensort.Utils.Compose (createTensor)+import Data.Tensort.Utils.Types (Memory (..), SortAlg, Sortable (..), Tensor, TensorStack, fromJust, fromSortBit, Bit)  -- | Compile a sorted list of Bits from a list of TensorStacks  -- | ==== __Examples__---  >>> getSortedBitsFromMetastack ([(0,5),(1,7)],ByteMem [[1,5],[3,7]])+--  >>> getSortedBitsFromTensor ([(0,5),(1,7)],ByteMem [[1,5],[3,7]]) --  [1,3,5,7]---  >>> getSortedBitsFromMetastack ([(0,8),(1,18)],TensorMem [([(0,7),(1,8)],TensorMem [([(0,3),(1,7)],ByteMem [[1,3],[5,7]]),([(0,4),(1,8)],ByteMem [[2,4],[6,8]])]),([(1,17),(0,18)],TensorMem [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(0,14),(1,17)],ByteMem [[12,14],[16,17]])])])+--  >>> getSortedBitsFromTensor ([(0,8),(1,18)],TensorMem [([(0,7),(1,8)],TensorMem [([(0,3),(1,7)],ByteMem [[1,3],[5,7]]),([(0,4),(1,8)],ByteMem [[2,4],[6,8]])]),([(1,17),(0,18)],TensorMem [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(0,14),(1,17)],ByteMem [[12,14],[16,17]])])]) --  [1,2,3,4,5,6,7,8,11,12,13,14,15,16,17,18]-getSortedBitsFromMetastack :: TensorStack -> SortAlg -> [Int]-getSortedBitsFromMetastack metastackRaw subAlg = acc metastackRaw []+getSortedBitsFromTensor :: TensorStack -> SortAlg -> [Bit]+getSortedBitsFromTensor tensorRaw subAlg = acc tensorRaw []   where-    acc :: TensorStack -> [Int] -> [Int]-    acc metastack sortedBits = do-      let (nextBit, metastack') = removeTopBitFromTensor metastack subAlg-      if isNothing metastack'+    acc :: TensorStack -> [Bit] -> [Bit]+    acc tensor sortedBits = do+      let (nextBit, tensor') = removeTopBitFromTensor tensor subAlg+      if isNothing tensor'         then nextBit : sortedBits         else do-          acc (fromJust metastack') (nextBit : sortedBits)+          acc (fromJust tensor') (nextBit : sortedBits)  -- | For use in compiling a list of Tensors into a sorted list of Bits --@@ -30,7 +30,7 @@ -- | ==== __Examples__ --   >>> removeTopBitFromTensor  ([(0,5),(1,7)],ByteMem [[1,5],[3,7]]) --   (7,Just ([(1,3),(0,5)],ByteMem [[1,5],[3]]))-removeTopBitFromTensor :: Tensor -> SortAlg -> (Int, Maybe Tensor)+removeTopBitFromTensor :: Tensor -> SortAlg -> (Bit, Maybe Tensor) removeTopBitFromTensor (register, memory) tsProps = do   let topRecord = last register   let topAddress = fst topRecord@@ -39,7 +39,7 @@     then (topBit, Nothing)     else (topBit, Just (createTensor (fromJust memory') tsProps)) -removeBitFromMemory :: Memory -> Int -> SortAlg -> (Int, Maybe Memory)+removeBitFromMemory :: Memory -> Int -> SortAlg -> (Bit, Maybe Memory) removeBitFromMemory (ByteMem bytes) i subAlg = do   let topByte = bytes !! i   let topBit = last topByte@@ -54,7 +54,7 @@       let bytes' = take i bytes ++ [topByte'] ++ drop (i + 1) bytes       (topBit, Just (ByteMem bytes'))     _ -> do-      let topByte'' = fromSortInt (subAlg (SortInt topByte'))+      let topByte'' = fromSortBit (subAlg (SortBit topByte'))       let bytes' = take i bytes ++ [topByte''] ++ drop (i + 1) bytes       (topBit, Just (ByteMem bytes')) removeBitFromMemory (TensorMem tensors) i subAlg = do

@@ -1,101 +0,0 @@-module Data.Tensort.Utils.Tensor-  ( getTensorStacksFromBytes,-    createTensor,-    getTensorFromBytes,-    createTensorStack,-  )-where--import Data.Tensort.Utils.Split (splitEvery)-import Data.Tensort.Utils.Types (Byte, Memory (..), Record, SortAlg, Sortable (..), Tensor, TensorStack, TensortProps (..), fromSortRec)---- | Convert a list of Bytes to a list of TensorStacks.---- | This is accomplished by making a Tensor for each Byte, converting that---   Tensor into a TensorStack (these are equivalent terms - see type---   definitions for more info) and collating the TensorStacks into a list---- | ==== __Examples__---  >>> getTensorStacksFromBytes [[2,4],[6,8],[1,3],[5,7]] 2---  [([(0,3),(1,7)],ByteMem [[1,3],[5,7]]),([(0,4),(1,8)],ByteMem [[2,4],[6,8]])]-getTensorStacksFromBytes :: [Byte] -> TensortProps -> [TensorStack]-getTensorStacksFromBytes bytes tsProps = foldr acc [] (splitEvery (bytesize tsProps) bytes)-  where-    acc :: [Byte] -> [TensorStack] -> [TensorStack]-    acc byte tensorStacks = tensorStacks ++ [getTensorFromBytes byte (subAlgorithm tsProps)]---- | Create a Tensor from a Memory---   Aliases to getTensorFromBytes for ByteMem and createTensorStack for---   TensorMem---- | I expect to refactor to simplify this before initial release-createTensor :: Memory -> SortAlg -> Tensor-createTensor (ByteMem bytes) subAlg = getTensorFromBytes bytes subAlg-createTensor (TensorMem tensors) subAlg = createTensorStack tensors subAlg---- | Convert a list of Bytes to a Tensor---- | We do this by loading the list of Bytes into the new Tensor's Memory---   and adding a sorted Register containing References to each Byte in Memory---- | Each Record contains an Address pointing to the index of the referenced---   Byte and a TopBit containing the value of the last (i.e. highest) Bit in---   the referenced Byte---- | The Register is bubblesorted by the TopBits of each Record---- | ==== __Examples__---  >>> getTensorFromBytes [[2,4,6,8],[1,3,5,7]]---  ([(1,7),(0,8)],ByteMem [[2,4,6,8],[1,3,5,7]])-getTensorFromBytes :: [Byte] -> SortAlg -> Tensor-getTensorFromBytes bytes subAlg = do-  let register = acc bytes [] 0-  let register' = fromSortRec (subAlg (SortRec register))-  (register', ByteMem bytes)-  where-    acc :: [Byte] -> [Record] -> Int -> [Record]-    acc [] register _ = register-    acc ([] : remainingBytes) register i = acc remainingBytes register (i + 1)-    acc (byte : remainingBytes) register i = acc remainingBytes (register ++ [(i, last byte)]) (i + 1)---- | Create a TensorStack with the collated and bubblesorted References from the---   Tensors as the Register and the original Tensors as the data---- | ==== __Examples__--- >>> createTensorStack [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(1,14),(0,17)],ByteMem [[16,17],[12,14]])]--- ([(1,17),(0,18)],TensorMem [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(1,14),(0,17)],ByteMem [[16,17],[12,14]])])-createTensorStack :: [Tensor] -> SortAlg -> TensorStack-createTensorStack tensors subAlg = (fromSortRec (subAlg (SortRec (getRegisterFromTensors tensors))), TensorMem tensors)---- | For each Tensor, produces a Record by combining the top bit of the---  Tensor with an index value for its Address---- | Note that this output is not sorted. Sorting is done in the---   createTensorStack function---- | ==== __Examples__--- >>> getRegisterFromTensors [([(0,13),(1,18)],ByteMem [[11,13],[15,18]]),([(0,14),(1,17)],ByteMem [[12,14],[16,17]]),([(0,3),(1,7)],ByteMem [[1,3],[5,7]]),([(0,4),(1,8)],ByteMem [[2,4],[6,8]])]--- [(0,18),(1,17),(2,7),(3,8)]-getRegisterFromTensors :: [Tensor] -> [Record]-getRegisterFromTensors tensors = acc tensors []-  where-    acc :: [Tensor] -> [Record] -> [Record]-    acc [] records = records-    acc (([], _) : remainingTensors) records = acc remainingTensors records-    acc (tensor : remainingTensors) records = acc remainingTensors (records ++ [(i, getTopBitFromTensorStack tensor)])-      where-        i = length records---- | Get the top Bit from a TensorStack---- | The top Bit is the last Bit in the last Byte referenced in the last record---   of the Tensor referenced in the last record of the last Tensor of...---   and so on until you reach the top level of the TensorStack---- | This is also expected to be the highest value in the TensorStack---- | ==== __Examples__--- >>> getTopBitFromTensorStack (([(0,28),(1,38)],TensorMem [([(0,27),(1,28)],TensorMem [([(0,23),(1,27)],ByteMem [[21,23],[25,27]]),([(0,24),(1,28)],ByteMem [[22,24],[26,28]])]),([(1,37),(0,38)],TensorMem [([(0,33),(1,38)],ByteMem [[31,33],[35,38]]),([(0,34),(1,37)],ByteMem [[32,14],[36,37]])])]))--- 38-getTopBitFromTensorStack :: Tensor -> Int-getTopBitFromTensorStack (register, _) = snd (last register)

@@ -8,13 +8,12 @@ --   defined here. Since these packages are only for sorting Ints currently, --   every data type is a structure of Ints ---   I know this might sound confusing, but in a recursive algorithm like this---   it's helpful to have different names for the same type of data depending---   on how it's being used, while still being able to use the same data in---   multiple contexts- -- | A Bit is a single element of the list to be sorted. For --   our current purposes that means it is an Int++-- | NOTE: To Self: at this point it's likely simple enough to refactor this+--   to sort any Ord, not just Ints. Consider using the `Bit` type synonym+--   in the code, then changing this to alias `Bit` to `Ord` or `a` type Bit = Int  -- | A Byte is a list of Bits standardized to a fixed maximum length (Bytesize)@@ -30,36 +29,36 @@ --   Tensor type TopBit = Bit --- | A Record is an element in a Tensor or Metatensor's Register+-- | A Record is an element in a Tensor's Register --   containing an Address pointer and a TopBit value  -- | A Record's Address is an index number pointing to a Byte or Tensor in---   the Tensor/Metatensor's Memory+--   the Tensor's Memory  -- | A Record's TopBit is a copy of the last (i.e. highest) Bit in the Byte or --   Tensor that the Record references type Record = (Address, TopBit)  -- | A Register is a list of Records allowing for easy access to data in a---   Tensor or Metatensor's Memory+--   Tensor's Memory type Register = [Record] --- | We use a Sortable type sort between Ints and Records+-- | We use a Sortable type sort between Bits and Records  -- | In the future this may be expanded to include other data types and allow---   for sorting other types of besides Ints+--   for sorting other types of besides Ints. data Sortable-  = SortInt [Int]+  = SortBit [Bit]   | SortRec [Record]   deriving (Show, Eq, Ord) -fromSortInt :: Sortable -> [Int]-fromSortInt (SortInt ints) = ints-fromSortInt (SortRec _) = error "This is for sorting Integers - you gave me Records"+fromSortBit :: Sortable -> [Bit]+fromSortBit (SortBit bits) = bits+fromSortBit (SortRec _) = error "This is for sorting Bits - you gave me Records"  fromSortRec :: Sortable -> [Record] fromSortRec (SortRec recs) = recs-fromSortRec (SortInt _) = error "This is for sorting Records - you gave me Integers"+fromSortRec (SortBit _) = error "This is for sorting Records - you gave me Bits"  type SortAlg = Sortable -> Sortable @@ -68,22 +67,29 @@ type SupersortStrat = (Sortable, Sortable, Sortable) -> Sortable  -- | A Memory contains the data to be sorted, either in the form of Bytes or---   Tensors+--   Tensors.++-- | Technically the Memory is a tensor field, but it seems +--   less confusing to just call it Memory data Memory   = ByteMem [Byte]   | TensorMem [Tensor]   deriving (Show, Eq, Ord) --- | A Tensor is a Metatensor that only contains Bytes in its memory--- | The Memory is a list of the Bytes or Tensors that the Tensor---   contains.+-- | A Tensor contains data to be sorted in a structure allowing for+--   easy access. It consists of a Register and its Memory. --- | The Register is a list of Records referencing the top Bits in Memory+-- | The Memory is a list of the Bytes or other Tensors that this Tensor+--   contains. Technically the Memory is a tensor field, but it seems +--   less confusing to just call it Memory.++-- | The Register is a list of Records referencing the top Bits in Memory.+ type Tensor = (Register, Memory)  -- | A TensorStack is a top-level Tensor. In the final stages of Tensort, the --   number of TensorStacks will equal the bytesize, but before that time there---   are expected to be many more TensorStacks+--   are expected to be many more TensorStacks. type TensorStack = Tensor  fromJust :: Maybe a -> a

@@ -20,14 +20,41 @@ -- PVP summary:     +-+------- breaking API changes --                  | | +----- non-breaking API additions --                  | | | +--- code changes with no API change-version:            0.1.0.0+version:            0.2.0.0 +tested-with:        GHC==9.8.2, +                    GHC==9.6.4, +                    GHC==9.4.8,+                    GHC==9.2.8,+                    GHC==9.2.1,+                    GHC==9.0.2,+                    GHC==8.10.7,+                    GHC==8.8.4,+                    GHC==8.6.5,+                    GHC==8.4.4,+                    GHC==8.2.2,+                    GHC==8.0.2,+                    GHC==7.10.3,+                    GHC==7.6.3,+                    GHC==7.4.2,+                    GHC==7.0.4,+                    GHC==7.0.1,+ -- A short (one-line) description of the package.-synopsis:           Reasonably robust sorting in O(n log n) time+synopsis:           Tunable sorting for responsive robustness and beyond!  -- A longer description of the package.-description:        An exploration of robustness in algorithms for sorting integers, inspired by [Beyond Efficiency](https://www.cs.unm.edu/~ackley/be-201301131528.pdf) by David H. Ackley+description:        A tunable tensor-based structure for sorting algorithms +                    along with various sample configurations. Birthed from an +                    exploration of robustness in algorithms for sorting +                    integers, inspired by +                    [Beyond Efficiency](https://www.cs.unm.edu/~ackley/be-201301131528.pdf) +                    by David H. Ackley and +                    [Beyond Efficiency by Dave Ackley](https://futureofcoding.org/episodes/070) +                    by Future of Coding. +homepage: https://github.com/kaBeech/tensort+ -- The license under which the package is released. license:            MIT @@ -49,11 +76,16 @@ build-type:         Simple  -- Extra doc files to be distributed with the package, such as a CHANGELOG or a README.-extra-doc-files:    CHANGELOG.md+extra-doc-files:    README.md,+                    CHANGELOG.md  -- Extra source files to be distributed with the package, such as examples, or a tutorial module. -- extra-source-files: +source-repository head+    type:           git+    location:       https://github.com/kaBeech/tensort+ common warnings     ghc-options: -Wall @@ -67,7 +99,7 @@                       Data.Tensort.Robustsort,                       Data.Tensort.Utils.Types,                       Data.Tensort.Subalgorithms.Bubblesort,-                      Data.Tensort.Subalgorithms.ReverseExchangesort,+                      Data.Tensort.Subalgorithms.Exchangesort,                       Data.Tensort.Subalgorithms.Permutationsort,                       Data.Tensort.Subalgorithms.Bogosort,                       Data.Tensort.Subalgorithms.Supersort,@@ -75,13 +107,13 @@                       Data.Tensort.OtherSorts.Mergesort,                       Data.Tensort.OtherSorts.Quicksort,                       Data.Tensort.Utils.RandomizeList,+                      Data.Tensort.Utils.Check,      -- Modules included in this library but not exported.-    other-modules:    Data.Tensort.Utils.Check,-                      Data.Tensort.Utils.Split,+    other-modules:    Data.Tensort.Utils.Split,                       Data.Tensort.Utils.ComparisonFunctions,                       Data.Tensort.Utils.Convert,-                      Data.Tensort.Utils.Tensor,+                      Data.Tensort.Utils.Compose,                       Data.Tensort.Utils.Reduce,                       Data.Tensort.Utils.Render, @@ -89,9 +121,9 @@     -- other-extensions:      -- Other library packages from which modules are imported.-    build-depends:    base ^>=4.18.2.0,-                      mtl >= 2.3.1 && < 2.4,-                      random >= 1.2.1 && < 1.3,+    build-depends:    base >=4.3.0.0 && <= 4.19.1.0,+                      mtl >= 2.2.2  && < 2.4,+                      random >= 1.0.0.3 && < 1.3,                       random-shuffle >= 0.0.4 && < 0.1,      -- Directories containing source files.@@ -115,9 +147,9 @@      -- Other library packages from which modules are imported.     build-depends:-        base ^>=4.18.2.0,+        base,         tensort,-        time >= 1.12.2 && < 1.13,+        time >= 1.2.0.3 && < 1.13,      -- Directories containing source files.     hs-source-dirs:   app@@ -133,7 +165,9 @@     default-language: Haskell2010      -- Modules included in this executable, other than Main.-    -- other-modules:+    other-modules:    TestCheck,+                      SortSpec,+                            -- LANGUAGE extensions used by modules in this package.     -- other-extensions:@@ -149,5 +183,7 @@      -- Test dependencies.     build-depends:-        base ^>=4.18.2.0,-        tensort+        base,+        tensort,+        mtl,+        QuickCheck >= 2.15 && < 2.16,

@@ -1,4 +1,68 @@ module Main (main) where +import Data.Tensort.OtherSorts.Mergesort (mergesort)+import Data.Tensort.OtherSorts.Quicksort (quicksort)+import Data.Tensort.Robustsort (robustsortB, robustsortM, robustsortP)+import Data.Tensort.Subalgorithms.Bogosort (bogosort)+import Data.Tensort.Subalgorithms.Bubblesort (bubblesort)+import Data.Tensort.Subalgorithms.Exchangesort (exchangesort)+import Data.Tensort.Subalgorithms.Magicsort (magicsort)+import Data.Tensort.Subalgorithms.Permutationsort (permutationsort)+import Data.Tensort.Subalgorithms.Supersort (magicSuperStrat, mundaneSuperStrat, supersort)+import Data.Tensort.Tensort (mkTSProps, tensort, tensortB4, tensortBL, tensortBN)+import Data.Tensort.Utils.Types (Sortable (..))+import SortSpec (result_is_sorted_bits, result_is_sorted_records, result_is_sorted_records_short)+import TestCheck (check)++-- | This suite of QuickCheck tests contains  a guard that will cause the test+--   `suite to fail if any of the individual tests fail main :: IO ()-main = putStrLn "Test suite not yet implemented."+main = do+  putStrLn "Running test suite!"+  putStrLn "Quicksort returns a sorted array..."+  check (result_is_sorted_records quicksort)+  putStrLn "True!"+  putStrLn "Mergesort returns a sorted array..."+  check (result_is_sorted_records mergesort)+  putStrLn "True!"+  putStrLn "Bubblesort returns a sorted array..."+  check (result_is_sorted_records bubblesort)+  putStrLn "True!"+  putStrLn "Exchangesort returns a sorted array..."+  check (result_is_sorted_records exchangesort)+  putStrLn "True!"+  putStrLn "Permutationsort returns a sorted array..."+  check (result_is_sorted_records permutationsort)+  putStrLn "True!"+  putStrLn "Bogosort returns a sorted array..."+  check (result_is_sorted_records bogosort)+  putStrLn "True!"+  putStrLn "Magicsort returns a sorted array..."+  -- check (result_is_sorted_records_short magicsort)+  let magicRes = magicsort (SortBit [5, 2, 3, 1, 4])+  print magicRes+  check (magicRes == SortBit [1, 2, 3, 4, 5])+  putStrLn "True!"+  putStrLn "Standard Logaritmic Tensort returns a sorted array..."+  let logRes = tensortBL [5, 2, 3, 1, 4]+  print logRes+  check (logRes == [1, 2, 3, 4, 5])+  -- check (result_is_sorted_bits tensortBL)+  putStrLn "True!"+  putStrLn "Standard 4-Bit Tensort returns a sorted array..."+  check (result_is_sorted_bits tensortB4)+  putStrLn "True!"+  -- TBA+  putStrLn "Standard Mundane Robustsort with Permutationsort adjudicator returns a sorted array..."+  check (result_is_sorted_bits robustsortP)+  putStrLn "True!"+  putStrLn "Standard Mundane Robustsort with Bogosort adjudicator returns a sorted array..."+  check (result_is_sorted_bits robustsortB)+  putStrLn "True!"+  putStrLn "Magic Robustsort returns a sorted array..."+  let magicRoboRes = magicsort (SortBit [5, 2, 3, 1, 4])+  print magicRoboRes+  check (magicRoboRes == SortBit [1, 2, 3, 4, 5])+  -- check (result_is_sorted_bits robustsortM)+  putStrLn "True!"+  putStrLn "All tests pass!"

@@ -0,0 +1,18 @@+module SortSpec (result_is_sorted_bits, result_is_sorted_records, result_is_sorted_records_short) where++import Data.Tensort.Utils.Check (isSorted)+import Data.Tensort.Utils.Types (Bit, Record, SortAlg, Sortable (..))+import Test.QuickCheck++result_is_sorted_bits :: ([Bit] -> [Bit]) -> [Bit] -> Property+result_is_sorted_bits sort unsortedList = (length unsortedList < 10) && not (null unsortedList) ==> isSorted (SortBit (sort unsortedList))++result_is_sorted_records :: SortAlg -> [Record] -> Property+result_is_sorted_records sort unsortedList = (length unsortedList < 10) && not (null unsortedList) ==> isSorted (sort (SortRec unsortedList))++result_is_sorted_records_short :: SortAlg -> [Record] -> Property+result_is_sorted_records_short sort unsortedList = (length unsortedList < 6) && not (null unsortedList) ==> isSorted (sort (SortRec unsortedList))++result_is_sorted_sortable :: SortAlg -> Sortable -> Property+result_is_sorted_sortable sort (SortBit unsortedList) = (length unsortedList < 10) && not (null unsortedList) ==> isSorted (sort (SortBit unsortedList))+result_is_sorted_sortable sort (SortRec unsortedList) = (length unsortedList < 10) && not (null unsortedList) ==> isSorted (sort (SortRec unsortedList))

@@ -0,0 +1,36 @@+module TestCheck (isPass, check) where++import Control.Monad (unless)+import System.Exit+import Test.QuickCheck++-- | Run a QuickCheck test and exit with a failure if it fails++-- | This is used so that the testing suite will fail if any QuickCheck tests+--   fail++-- | ==== __Examples__+--   >>> check (1 == 1)+--   ...+--   >>> check (1 == 2)+--   ...+--   ...exit with failure+check :: (Testable prop) => prop -> IO ()+check prop = do+  result <- quickCheckResult prop+  unless (isPass result) exitFailure++-- | Returns True if a test passes, and False otherwise++-- | ==== __Examples__+--   >>> isPass (Success {})+--   True+--   >>> isPass (GaveUp {})+--   False+--   >>> isPass (Failure {})+--   False+--   >>> isPass (_ {})+--   False+isPass :: Result -> Bool+isPass (Success {}) = True+isPass _ = False