packages feed

tensort 0.2.0.0 → 0.2.0.1

raw patch · 9 files changed

+132/−62 lines, 9 filesdep ~QuickCheckdep ~basedep ~timePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: QuickCheck, base, time

API changes (from Hackage documentation)

Files

CHANGELOG.md view
@@ -23,3 +23,13 @@ * Expand supported dependency versions  * Add tests++## 0.2.0.1 -- 2024-06-12++* Add guards for short lists in input++* Improve testing++* Improve documentation++* Add very basic benchmarking
README.md view
@@ -1,4 +1,4 @@-# Tensort+# Tensort [![Hackage](https://img.shields.io/hackage/v/tensort.svg)](https://hackage.haskell.org/package/tensort)  Tensort is a tensor-based sorting algorithm that is tunable to adjust to  the priorities of the task at hand.@@ -6,11 +6,11 @@ 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+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.+functional but I have yet to add much documentation and benchmarking. There's likely a lot of room for improvement in the code as well.  ## Table of Contents@@ -18,6 +18,7 @@ - [Introduction](#introduction)   - [Inspiration](#inspiration)   - [Why?](#why)+  - [But why would anyone care about this in the first place?](#but-why-would-anyone-care-about-this-in-the-first-place)   - [Why Haskell?](#why-haskell) - [Project structure](#project-structure) - [Algorithms overview](#algorithms-overview)@@ -46,34 +47,41 @@ ### Inspiration    - [Beyond Efficiency](https://www.cs.unm.edu/~ackley/be-201301131528.pdf) by -  David H. Ackley+  [David H. Ackley](https://github.com/DaveAckley)     -  - Future of Coding's -  [podcast episode](https://futureofcoding.org/episodes/070) on the same paper+  - [Beyond Efficiency by Dave Ackley](https://futureofcoding.org/episodes/070) +  by Future of Coding ([Lu Wilson](https://github.com/TodePond),+  [Jimmy Miller](https://github.com/jimmyhmiller),+  [Ivan Reese](https://github.com/ivanreese))  ### 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?"+Because near the end of [that podcast episode](https://futureofcoding.org/episodes/070), +[Ivan](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? +Well, a tunable sorting algorithm is a really cool thing to have!++This can have many different uses, one of which is prioritizing robustness.+ [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!+compelling things to say about why prioritizing robustness is important and +useful, 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 +If you want my elevator pitch, it's because we eventually want to build things+like [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 +Another example I like to consider is artificial cognition. When working +in a non-deterministic system (or a system so complex as to be considered+non-deterministic), 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 @@ -742,5 +750,5 @@    - Magic Robustsort -Check the code in `src/` or the documentation on Hackage/Hoogle (Coming Soon!) +Check the code in `src/` or the documentation on Hackage/Hoogle for more details.
app/Main.hs view
@@ -9,15 +9,13 @@ import Data.Tensort.Utils.Types (Sortable (..), fromSortBit) import Data.Time.Clock -unsortedBits :: [Int]-unsortedBits = [2, 5, 10, 4, 15, 11, 7, 14, 16, 6, 13, 3, 8, 9, 12, 1]- genUnsortedBits :: Int -> Sortable genUnsortedBits n = randomizeList (SortBit [1 .. n]) 143  main :: IO () main = do-  printTimes (map genUnsortedBits [52, 1000, 10000, 50000, 100000])+  -- Eventually I hope to turn that 14 into a 20+  printTimes (map (genUnsortedBits . (2 ^)) [3 .. 14])  printTimes :: [Sortable] -> IO () printTimes [] = return ()@@ -35,7 +33,7 @@   startTensortBL <- getCurrentTime   putStrLn ("    " ++ show (length (tensortBL (fromSortBit l))))   endTensortBL <- getCurrentTime-  putStr (" tensortBL   | " ++ show (diffUTCTime endTensortBL startTensortBL) ++ " | ")+  putStr (" TensortBL   | " ++ show (diffUTCTime endTensortBL startTensortBL) ++ " | ")   startRSortP <- getCurrentTime   putStrLn ("    " ++ show (length (robustsortP (fromSortBit l))))   endRSortP <- getCurrentTime@@ -57,8 +55,8 @@   endQuicksort <- getCurrentTime   putStr (" Quicksort   | " ++ show (diffUTCTime endQuicksort startQuicksort) ++ " | ")   startBubblesort <- getCurrentTime-  putStrLn ("    " ++ show (length (fromSortBit (bubblesort l))))+  putStrLn ("     " ++ show (length (fromSortBit (bubblesort l))))   endBubblesort <- getCurrentTime   putStr (" Bubblesort  | " ++ show (diffUTCTime endBubblesort startBubblesort) ++ " | ")-  putStrLn ("    " ++ show (length (fromSortBit (bubblesort l))))+  putStrLn ("    " ++ show (length (fromSortBit l)))   putStrLn "----------------------------------------------------------"
src/Data/Tensort/Subalgorithms/Magicsort.hs view
@@ -5,12 +5,18 @@  import Data.Tensort.Subalgorithms.Bogosort (bogosort) import Data.Tensort.Subalgorithms.Permutationsort (permutationsort)-import Data.Tensort.Utils.Types (Sortable)+import Data.Tensort.Utils.Types (Sortable (..))  magicsort :: Sortable -> Sortable magicsort xs = do   let result1 = permutationsort xs   let result2 = bogosort xs-  if result1 == result2+  if verifyResults result1 result2     then result1     else magicsort xs++verifyResults :: Sortable -> Sortable -> Bool+verifyResults (SortBit xs) (SortBit ys) = xs == ys+verifyResults (SortRec xs) (SortRec ys) = map snd xs == map snd ys+verifyResults (SortBit _) (SortRec _) = False+verifyResults (SortRec _) (SortBit _) = False
src/Data/Tensort/Tensort.hs view
@@ -13,7 +13,7 @@ import Data.Tensort.Utils.RandomizeList (randomizeList) import Data.Tensort.Utils.Reduce (reduceTensorStacks) import Data.Tensort.Utils.Render (getSortedBitsFromTensor)-import Data.Tensort.Utils.Types (Sortable (..), TensortProps (..), fromSortBit, SortAlg, Bit)+import Data.Tensort.Utils.Types (Bit, SortAlg, Sortable (..), TensortProps (..), fromSortBit)  -- | Sort a list of Bits using the Tensort algorithm @@ -21,6 +21,7 @@ -- >>> 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 :: [Bit] -> TensortProps -> [Bit]+tensort [] _ = [] tensort xs tsProps = do   let bits = randomizeList (SortBit xs) 143   let bytes = rawBitsToBytes (fromSortBit bits) tsProps@@ -38,6 +39,9 @@ tensortBN n xs = tensort xs (mkTSProps n bubblesort)  tensortBL :: [Bit] -> [Bit]+tensortBL [] = []+tensortBL [x] = [x]+tensortBL [x, y] = if x <= y then [x, y] else [y, x] tensortBL xs = tensort xs (mkTSProps (calculateBytesize xs) bubblesort)  calculateBytesize :: [Bit] -> Int
src/Data/Tensort/Utils/Types.hs view
@@ -68,9 +68,6 @@  -- | A Memory contains the data to be sorted, either in the form of Bytes or --   Tensors.---- | Technically the Memory is a tensor field, but it seems ---   less confusing to just call it Memory data Memory   = ByteMem [Byte]   | TensorMem [Tensor]@@ -80,11 +77,9 @@ --   easy access. It consists of a Register and its 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.+--   contains.  -- | 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
tensort.cabal view
@@ -20,7 +20,7 @@ -- PVP summary:     +-+------- breaking API changes --                  | | +----- non-breaking API additions --                  | | | +--- code changes with no API change-version:            0.2.0.0+version:            0.2.0.1  tested-with:        GHC==9.8.2,                      GHC==9.6.4, @@ -121,7 +121,7 @@     -- other-extensions:      -- Other library packages from which modules are imported.-    build-depends:    base >=4.3.0.0 && <= 4.19.1.0,+    build-depends:    base >=4.3.0.0 && <= 4.20.0.1,                       mtl >= 2.2.2  && < 2.4,                       random >= 1.0.0.3 && < 1.3,                       random-shuffle >= 0.0.4 && < 0.1,@@ -149,7 +149,7 @@     build-depends:         base,         tensort,-        time >= 1.2.0.3 && < 1.13,+        time >= 1.2.0.3 && < 1.15,      -- Directories containing source files.     hs-source-dirs:   app@@ -186,4 +186,4 @@         base,         tensort,         mtl,-        QuickCheck >= 2.15 && < 2.16,+        QuickCheck >= 2.14.3 && < 2.16,
test/Main.hs view
@@ -9,9 +9,9 @@ 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 Data.Tensort.Tensort (mkTSProps, tensort, tensortB4, tensortBL)+import Data.Tensort.Utils.Types (Bit, Sortable)+import SortSpec (result_is_sorted_bits, result_is_sorted_custom_bitsize, 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@@ -35,24 +35,20 @@   check (result_is_sorted_records permutationsort)   putStrLn "True!"   putStrLn "Bogosort returns a sorted array..."-  check (result_is_sorted_records bogosort)+  check (result_is_sorted_records_short 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])+  check (result_is_sorted_records_short magicsort)   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)+  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 Custom Bitsize Tensort returns a sorted array..."+  check result_is_sorted_custom_bitsize+  putStrLn "True!"   putStrLn "Standard Mundane Robustsort with Permutationsort adjudicator returns a sorted array..."   check (result_is_sorted_bits robustsortP)   putStrLn "True!"@@ -60,9 +56,36 @@   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)+  check (result_is_sorted_bits robustsortM)   putStrLn "True!"+  putStrLn "Custom Tensort returns a sorted array..."+  check (result_is_sorted_bits tensortCustomExample)+  putStrLn "True!"+  putStrLn "Custom Mundane Supersort returns a sorted array..."+  check (result_is_sorted_records_short supersortMundaneCustomExample)+  putStrLn "True!"+  putStrLn "Custom Magic Supersort returns a sorted array..."+  check (result_is_sorted_records_short supersortMagicCustomExample)+  putStrLn "True!"+  putStrLn "Custom Mundane Robustsort returns a sorted array..."+  check (result_is_sorted_bits robustsortMundaneCustomExample)+  putStrLn "True!"+  putStrLn "Custom Magic Robustsort returns a sorted array..."+  check (result_is_sorted_bits robustsortMagicCustomExample)+  putStrLn "True!"   putStrLn "All tests pass!"++tensortCustomExample :: [Bit] -> [Bit]+tensortCustomExample xs = tensort xs (mkTSProps 8 mergesort)++supersortMundaneCustomExample :: Sortable -> Sortable+supersortMundaneCustomExample xs = supersort xs (quicksort, magicsort, bubblesort, mundaneSuperStrat)++supersortMagicCustomExample :: Sortable -> Sortable+supersortMagicCustomExample xs = supersort xs (bogosort, permutationsort, magicsort, magicSuperStrat)++robustsortMundaneCustomExample :: [Bit] -> [Bit]+robustsortMundaneCustomExample xs = tensort xs (mkTSProps 3 supersortMundaneCustomExample)++robustsortMagicCustomExample :: [Bit] -> [Bit]+robustsortMagicCustomExample xs = tensort xs (mkTSProps 3 supersortMagicCustomExample)
test/SortSpec.hs view
@@ -1,18 +1,44 @@-module SortSpec (result_is_sorted_bits, result_is_sorted_records, result_is_sorted_records_short) where+module SortSpec+  ( result_is_sorted_bits,+    result_is_sorted_records,+    result_is_sorted_records_short,+    result_is_sorted_custom_bitsize,+  )+where +import Data.Tensort.Tensort (tensortBN) 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_bits sort unsortedList =+  within+    100000+    ( (length unsortedList < 10) ==>+        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 sort unsortedList =+  within+    100000+    ( (length unsortedList < 10) ==>+        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_records_short sort unsortedList =+  within+    100000+    ( (length unsortedList < 6) ==>+        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))+result_is_sorted_custom_bitsize :: Int -> [Bit] -> Property+result_is_sorted_custom_bitsize n unsortedList =+  within+    100000+    ( (length unsortedList < 15) && (n > 1) ==>+        isSorted (SortBit (tensortBN n unsortedList))+    )