### changeset 47:1aefea69f71b

Implement bubble sort by delta
author Yasutaka Higa Tue, 11 Nov 2014 14:01:31 +0900 cb5c190aa45d 820af7cc8485 delta.hs 1 files changed, 27 insertions(+), 7 deletions(-) [+]
line wrap: on
line diff
```--- 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```