# HG changeset patch
# User Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
# Date 1415682091 -32400
# Node ID 1aefea69f71b7564c07dd8697d717fe37f3bdc52
# Parent  cb5c190aa45d9b887a3c70c847ed70f0ea937df6
Implement bubble sort by delta

diff -r cb5c190aa45d -r 1aefea69f71b delta.hs
--- a/delta.hs	Tue Nov 11 13:28:55 2014 +0900
+++ b/delta.hs	Tue Nov 11 14:01:31 2014 +0900
@@ -14,8 +14,11 @@
 value :: (Delta a) -> a
 value (Delta _ x _ _) = x
 
-similar :: (Delta a) -> a
-similar (Delta _ _ _ y) = y
+deltaLeft :: (Delta a) -> a
+deltaLeft (Delta _ x _ _) = x
+
+deltaRight :: (Delta a) -> a
+deltaRight (Delta _ _ _ y) = y
 
 instance (Eq a) => Eq (Delta a) where
     s == ss = (value s) == (value ss)
@@ -27,6 +30,10 @@
 fmapS :: (Show a) => (a -> b) -> Delta a -> Delta b
 fmapS f (Delta lx x ly y) = Delta (lx ++ [(show x)]) (f x) (ly ++ [(show y)]) (f y)
 
+-- not proof
+fmapSS :: (Show a) => (a -> b) -> (a -> b) -> Delta a -> Delta b
+fmapSS f g (Delta lx x ly y) = Delta (lx ++ [(show x)]) (f x) (ly ++ [(show y)]) (g y)
+
 instance Applicative Delta where
     pure f                                      = Delta [] f [] f
     (Delta lf f lg g) <*> (Delta lx x ly y) = Delta (lf ++ lx) (f x) (lg ++ ly) (g y)
@@ -64,10 +71,23 @@
 primeCount x = generator x >>= primeFilter >>= count
 
 bubbleSort :: [Int] -> Delta [Int]
-bubbleSort [] = returnS []
-bubbleSort xs = fmapS (\x -> (replicate maxNumCount maxNum) ++ x) (bubbleSort remainList)
+bubbleSort = rightReverse . bubbleSortDelta . returnS
+
+bubbleSortDelta :: Delta [Int] -> Delta [Int]
+bubbleSortDelta (Delta lx [] ly []) = (Delta lx [] ly [])
+bubbleSortDelta xs = fmapSS (\x -> (replicate maxNumCount maxNum) ++ x)
+                            (\y -> (replicate minNumCount minNum) ++ y)
+                            (bubbleSortDelta $ fmapSS remainListMax remainListMin xs)
     where
-        maxNum      = maximum xs
-        remainList  = filter (/= maxNum) xs
-        maxNumCount = (length xs) - (length remainList)
+        leftValue      = deltaLeft xs
+        rightValue     = deltaRight xs
+        maxNum         = maximum leftValue
+        minNum         = minimum rightValue
+        remainListMax  = filter (/= maxNum)
+        remainListMin  = filter (/= minNum)
+        maxNumCount    = (length leftValue)  - (length $ remainListMax leftValue)
+        minNumCount    = (length rightValue) - (length $ remainListMin rightValue)
 
+
+rightReverse :: Delta [Int] -> Delta [Int]
+rightReverse d = fmapSS id reverse d