1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97

{-# LANGUAGE BangPatterns #-}

import Data.List (intercalate)

-- Тип для представления пары значений
data TwoVal = TwoVal !Int !Int
  deriving (Show, Eq)

-- Тип для пары с флагом обмена
data TwoValAndStatus = TwoValAndStatus 
  { isSwapped :: !Bool
  , twoVal    :: !TwoVal
  } deriving (Show, Eq)

-- Тип для массива (используем список для идиоматичности Haskell)
type Array = [Int]

-- Тип для массива с состоянием сортировки
data ArrayAndStatus = ArrayAndStatus
  { hasSwap :: !Bool
  , position :: !Int
  , array :: !Array
  } deriving (Show, Eq)

-- Сортировка двух элементов с возвратом статуса обмена
sort2 :: TwoVal -> TwoValAndStatus
sort2 (TwoVal a b)
  | a > b     = TwoValAndStatus True (TwoVal b a)
  | otherwise = TwoValAndStatus False (TwoVal a b)

-- Чтение пары значений из массива по позиции
readTwoVal :: Array -> Int -> Maybe TwoVal
readTwoVal arr pos
  | pos < length arr - 1 = Just $ TwoVal (arr !! pos) (arr !! (pos + 1))
  | otherwise = Nothing

-- Сохранение значения в массив по индексу
storeVal :: Array -> Int -> Int -> Array
storeVal arr val pos = 
  take pos arr ++ [val] ++ drop (pos + 1) arr

-- Сохранение пары значений в массив
storeTwoVal :: Array -> TwoVal -> Int -> Array
storeTwoVal arr (TwoVal a b) pos =
  storeVal (storeVal arr a pos) b (pos + 1)

-- Рекурсивная функция сортировки пузырьком
bubbleSortRec :: ArrayAndStatus -> ArrayAndStatus
bubbleSortRec state@(ArrayAndStatus swap pos arr)
  | pos >= length arr - 1 = 
      if not swap
        then state  -- Сортировка завершена!
        else bubbleSortRec $ ArrayAndStatus False 0 arr  -- Новый проход
  | otherwise = 
      case readTwoVal arr pos of
        Nothing -> state
        Just pair -> -- ← Переименовали переменную здесь
          let sortResult = sort2 pair
              newArr = storeTwoVal arr (twoVal sortResult) pos -- ← Используем селектор twoVal
              newSwap = swap || isSwapped sortResult
          in bubbleSortRec $ ArrayAndStatus newSwap (pos + 1) newArr

-- Основная функция сортировки
bubbleSort :: Array -> Array
bubbleSort arr = array $ bubbleSortRec $ ArrayAndStatus False 0 arr

-- Более идиоматичная версия для Haskell (альтернативная реализация)
bubbleSortIdiomatic :: Ord a => [a] -> [a]
bubbleSortIdiomatic = untilFixed bubblePass
  where
    bubblePass [] = []
    bubblePass [x] = [x]
    bubblePass (x:y:xs)
      | x > y     = y : bubblePass (x:xs)
      | otherwise = x : bubblePass (y:xs)
    
    untilFixed f x = let fx = f x
                     in if fx == x then x else untilFixed f fx

-- Функция для красивого вывода
showArray :: Show a => [a] -> String
showArray = intercalate ", " . map show

-- Главная функция
main :: IO ()
main = do
  let initialArray = [8, 2, 4, 1, 3, 5, 7, 0, 6, 9]
  let sortedArray = bubbleSort initialArray
  
  putStrLn "input"
  putStrLn $ showArray initialArray
  
  putStrLn "\nsort:"
  putStrLn $ showArray sortedArray
  
  putStrLn "\nsort2:"
  putStrLn $ showArray $ bubbleSortIdiomatic initialArray