Mercurial > hg > Members > atton > delta_monad

changeset 142:861e35665469

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add sort example using Delta/DeltaM
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Wed, 25 Feb 2015 14:23:19 +0900
parents 957496efbe5d
children f241d521bf65
files .hgignore haskell/Example/Delta.hs haskell/Example/DeltaM.hs
diffstat 3 files changed, 68 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/.hgignore	Sun Feb 15 17:44:20 2015 +0900
+++ b/.hgignore	Wed Feb 25 14:23:19 2015 +0900
@@ -1,5 +1,7 @@
 syntax: glob
 
+.DS_Store
+
 *.swp
 *.*~
 *.agdai
--- a/haskell/Example/Delta.hs	Sun Feb 15 17:44:20 2015 +0900
+++ b/haskell/Example/Delta.hs	Wed Feb 25 14:23:19 2015 +0900
@@ -20,3 +20,28 @@
 
 numberCount :: Int -> Delta Int
 numberCount x = generator x >>= numberFilter >>= count
+
+sort :: [Int] -> Delta [Int]
+sort xs = deltaFromList [ bubbleSort  xs,
+                          singleSort  xs,
+                          swapPair    xs,
+                          identity,
+                          nil
+                        ]
+    where
+        nil = []
+        identity = xs
+
+        swapPair  []        = []
+        swapPair  [x]       = [x]
+        swapPair  (x:xx:xs) = (min x xx) : (max x xx) : xs
+
+        singleSort []        = []
+        singleSort xs        = (minimum xs) : (singleSort (filter (/= (minimum xs)) xs))
+
+        bubbleSort []       = []
+        bubbleSort xs       = let
+                minVal  = minimum xs
+                minVals = replicate (length (filter (== minVal) xs)) minVal
+            in
+                minVals ++ (bubbleSort (filter (/= (minimum xs)) xs))
--- a/haskell/Example/DeltaM.hs	Sun Feb 15 17:44:20 2015 +0900
+++ b/haskell/Example/DeltaM.hs	Wed Feb 25 14:23:19 2015 +0900
@@ -44,3 +44,44 @@
 
 numberCountM :: Int -> DeltaWithLog Int
 numberCountM x = generatorM x >>= numberFilterM >>= countM
+
+
+-- example : sort
+
+sort :: [Int] -> DeltaWithLog [Int]
+sort xs = DeltaM $ deltaFromList [ --bubbleSort xs,
+                          singleSort xs,
+                          returnW $ swapPair xs,
+                          identity,
+                          nil
+                        ]
+    where
+        nil = returnW []
+
+        identity = returnW xs
+
+        swapPair  []        = []
+        swapPair  [x]       = [x]
+        swapPair  (x:xx:xs) = (min x xx) : (max x xx) : xs
+
+        singleSort []        = returnW []
+        singleSort xs        = do
+                tell [show xs]
+                res <- do
+                    remanVals <- singleSort $ filter (/= (minimum xs)) xs
+                    return $ (minimum xs) : remanVals
+                tell [ show res ]
+                return res
+
+        bubbleSort []       = returnW []
+        bubbleSort xs       = let
+                minVal  = minimum xs
+                minVals = replicate (length (filter (== minVal) xs)) minVal
+            in
+                do
+                    tell [show xs]
+                    res <- do
+                            remainVals <- bubbleSort $ filter (/= minVal) xs
+                            return $ minVals ++ remainVals
+                    tell [show res]
+                    return res