4_1.hs

{--
Задача 4-1
Одеров Роман, 545 гр.
--}



parts [x] = True 	-- очевидно, один элемент сам по себе упорядоченный
parts xs = p 2 xs (length xs) --начинаем с шагом 2 идти по массиву и проверять двойки элементов на упорядоченность.

-- Потом шаг увеличиваем след.образом:

p c xs len_xs = if (c*2 > len_xs) then chkGrowth len_xs len_xs xs else -- Если шаг стал больше половины,
												--то уже не найдем одинаковые части массива. Есть смысл рассмотреть лишь его целиком
					if (mod len_xs c /= 0) then p (c+1) xs len_xs -- Если длина массива не делится на шаг, то сразу увеличиваем шаг на 1
						else chkGrowth c c xs || p (c+1) xs len_xs -- Если можно разделить массив, то проверяем упорядоченность с текущим шагом
																	-- и не забываем учесть возможность успеха в следующих разложениях

--ф-ция проверки упорядоченности кусков массива длины step.
chkGrowth _ _ [] = True
chkGrowth s step (xs) = if (s > 1) then --на текущем этапе s - сколько осталось элементов текущего кусочка. Step - хранит начальный размер кусочка. 
														-- xs - остаток массива, который надо перебрать.
							if ((head xs) < head(tail xs)) then
								chkGrowth (s-1) step (tail xs)
							else False
						else chkGrowth step step (tail xs) -- когда s = 1, остался лишь один элемент, который сравнили с предыдущим на прошлом шаге
															-- Т.о. начинаем новый кусочек и отсчет опять начинается со step (со след.элемента)

{-
chkGrowth [] = True
chkGrowth (x:xs) = chkGr x xs
chkGr x [] = True
chkGr x xs = if xs==[] then True else
				if x < head(xs) then chkGr (head xs) (tail xs)
				else False
-}