4_2.hs

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

{-Ф-ция parts2' <xs> <prev1> <prev2> <l1> <l2> <maxl>
        xs = оставшийся список, подлежащий распределению по двум подспискам
        prev1 и prev2 = последние элементы подсписков (в силу условия возрастания, в список НЕЛЬЗЯ брать элементы МЕНЬШЕ предыдущего)
        l1 и l2 = длины подсписков. Должны быть равны ПОЛОВИНЕ ЭЛЕМЕНТОВ исходного списка 
        maxl = Число, половина количества элементов исходного списка
-}
{-если количество элементов заведомо нечетно, то раскладывать не имеет смысла.
  иначе первый элемент "кидается" в любой список (первый по умолчанию).
  Далее бежим по списку и раскидываем элементы туда, куда подходят.  
  Для пустого второго списка минимальное значение = -(бесконечность)
-}

parts2 (x:xs) = if (mod (length (x:xs)) 2 == 0) then parts2' xs x (-1/0) 1 0 (div (length (x:xs)) 2) 
                else False
parts2' [] _ _ l1 l2 _ = l1 == l2 -- Когда закончили разбирать список, проверяем одинаковое количество элементов в подсписках

parts2' (x:xs) prev1 prev2 l1 l2 maxl =
  if (l1>maxl || l2>maxl) then False --если набрали больше половины элементов, False
  else
    --если следующий элемент можно поместить в любой из двух подсписков, учитываем оба варианта
    if (x>prev1 && x>prev2) then parts2' xs x prev2 (l1+1) l2 maxl || parts2' xs prev1 x l1 (l2+1) maxl
    else
      --если подходит только в один подсписок, добавляем его туда (далее 2 случая в зависимости от подходящего списка):
      if (x>prev1) then parts2' xs x prev2 (l1+1) l2 maxl
      else
        if (x>prev2) then parts2' xs prev1 x l1 (l2+1) maxl
        else False -- если никуда не подходит, False