[x(i) + x(i+1) : x(i) + x(i+1) + x(i+2) : x(i) + x(i+1) + x(i+2) + x(i+3) : ...]
i = 0..length

M>[x(i) + x(i+1) : x(i) + x(i+1) + x(i+2) : x(i) + x(i+1) + x(i+2) + x(i+3) : ...]
M>i = 0..length
M>

M>У меня есть как бы пару идей. Как сортировать и выводить я знаю А вот ввод и нахождение сумм — . Вернее, как минимум сегодня, нет времени над этим подумать А решить хочется сегодня

M>Не швырнете в меня кодом? Или кусками кода

[1,2,15,20]

yourFunc :: [Int]->[Int]
yourFunc x = x

main = getLine >>= putStrLn.show.yourFunc.read

plus_elts :: (Num elt)
    => [elt] -- суммы с прошлого раза
    -> [elt] -- данные из исходного массива
    -> [elt] -- новые суммы

plus_elts [_] [] = 0 -- ниже дадим гарантию, что списки отличаются на 1 элемент
plus_elts (x:xs) (y:ys) = (x+y):(plus_elts xs ys)

list2sums :: (Num elt)
    => [elt] -- исходный массив
    -> [[elt]] -- массив сумм, начиная с суммы пар

list2sums []  = [] -- два дефолтных случая, когда просто нечего делать
list2sums [_] = [] -- впрочем, этот случай является завершением рекурсии ниже
list2sums d = list2sums' d (tail d) -- складываем со сдвигом: [1,2,3,...] + [2,3,4,...]
  where
    -- вход: список сумм с прошлого раза (s) и хвост массива исходных данных (d)
    -- выход: список списков сумм n-ок, начиная со следующей
    -- предусловие: (length s) == (length d)+1
    -- постусловие: голова результата (передаваемая дальше) s', (length s')==(length d)==(length s)-1
    list2sums' s [] = [] -- нечего больше складывать (кстати, можно проверить, что s содержит ровно один элемент)
    list2sums' s d =
      let s' = (plus_elts s d) -- length s' == length d
      in s' : (list2sums' s' (tail d)) 
  -- первый раз мы вызвали list2sums' где s - входные данные, т.е. суммы групп по одному :)

src = x1 : x2 : x3 : ...

s1 = x1+x2 : x1+x2+x3 : x1+x2+x3+x4 : ...

s2 =            x2+x3 :    x2+x3+x4 : ...
   =         s11-x1   : s12-x1      : ... = (tail s1) `decrement_by` (head x)

s3 =                          x3+x4 : ...
   =                    s21-x2      : ... = (tail s2) `decrement_by` (head (tail x))

причём
s1 = x1+x2 : (s1_1+x3) : (s1_2+x4) : ...

integrator f x0 []      = []
integrator f x0 (x1:xs) = x0' : integrator x0' xs
  where x0'= x0 `f` x1
-- как-то можно выразить через foldr. как именно? лень думать, однако.

-- первая серия - это список частичных сумм
partialsums (x1:xs) = integrator (+) x1 xs

-- все серии
allsums []   = [] -- нет данных
allsums [x1] = [] -- недостаточно данных
allsums xs   = s1 : integrator s1 iter xs
  where
    s1 = partialsums xs
    -- и собственно операция скрещивания
    sk `iter` xk = (tail sk) `decrement_by` xk
    s `decrement_by` x = map (\si -> si-x) s

ssum n l = (sum l1): ssum (n+1) l2 
  where (l1,l2)= splitAt n l

f = fromInt.sort.(ssum 2).toInt.words -- или .lines, если по строкам

main = interact f

f = (map fromInt).sort.(map ((ssum 2).toInt).words

M>[x(i) + x(i+1) : x(i) + x(i+1) + x(i+2) : x(i) + x(i+1) + x(i+2) + x(i+3) : ...]
M>i = 0..length
M>

sumn [] _ = []
sumn xs n = sum head : sumn tail n
    where (head, tail) = splitAt n xs

main = let num = 15
           xs = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
       in mapM_ (print . sumn xs) [2..num]

plus_elts :: (Num elt)
    => [elt] -- суммы с прошлого раза
    ->> [elt] -- данные из исходного массива
    ->> [elt] -- новые суммы

plus_elts [_] [] = 0 -- ниже дадим гарантию, что списки отличаются на 1 элемент
plus_elts (x:xs) (y:ys) = (x+y):(plus_elts xs ys)

GHC
— Could not deduce (Num [elt]) from the context (Num elt) Main.hs ArraySort/src line 9 04 December 2005 10:18:06 13
— Probable fix: — add (Num [elt]) to the type signature(s) for `plus_elts' — or add an instance declaration for (Num [elt]) — In the definition of `plus_elts': plus_elts [_] [] = 0 Main.hs ArraySort/src line 9 04 December 2005 10:18:06 14

Hugs
ERROR "D:\Mamut\EclipseWorkspace\ArraySort\src\Main.hs":9 — Cannot justify constraints in explicitly typed binding
*** Expression : plus_elts
*** Type : Num a => [a] -> [a] -> [a]
*** Given context : Num a
*** Constraints : Num [a]

К>>Если хочешь освоить Хаскелл — то вперёд, а если нужно по-быстрому за оставшийся день — то С++ в руки

M>Ну что ж. Буду думать, благо алгоритм уже разжеван и разве что в рот не положен Тем более, что время есть

-- тип "комбинация"...
type Combination = [Int] -- это упорядоченный список индексов комбинации
                         -- в принципе, мог быть и массив - но его порождать тяжелее

-- генератор комбинаций
combinations :: Int -> Int -> Int -> [Combination]
combinations n0 n1 k -- перебор k чисел из диапазона [n0..n1]
  | k==0      = [ [] ]                                       -- вырожденный случай
  | k==1      = [ [x] | x <- [n0..n1] ]                      -- банальный случай
  | otherwise = [ (x:xs) | x <- [n0..n1-(k-1)],              -- первое число
                           xs <- combinations (x+1) n1 (k-1) -- и перебор всех остальных
                ]

-- сумма данной комбинации элементов массива
sum :: (Num a) => Array a -> Combination -> a
sum arr inds = foldr fn ids
  where
    {- по смыслу:
       index `fn` total = (arr!index) + total
    что равно
       fn i t = (+) ((!) arr i) t
       fn i   = (+) ((!) arr i)
              = (+)(((!) arr)i)
              = (+)$((!) arr)i
       fn     = (+)$((!) arr)
    -}
    fn = (+)$((!)arr)

-- генератор сумм (до посинения)
gensums :: (Num a) => Array a -> Int -> [a]
gensums arr k = [ sum' comb | comb <- combinations n0 n1 k ] -- внёс поправку: combinations, а не permutations'
  where
    sum' = sum arr -- говорят, биндинг дешевле пассинга
    (n0,n1) = bounds arr

-- список сумм
listsums :: (Num a) => Array a -> [[a]]
listsums arr = [ gensums' k | k <- [1..n] ]
  where
    gensums' = gensums arr
    (n0,n1) = bounds arr
    k = n1-n0+1

-- и вот теперь, над этим списком будем надругиваться...
mergesums :: (Num a) => [[a]] -> [a]
-- (фантазия временно иссякла)

-- финальная функция
allsums :: (Num a) => Array a -> [a]
allsums {-arr-} = mergesums.listsums {-arr-}

main = do
  lst <- read <<= getStrLn -- через запятую, в квадратных скобках
  let arr = arrayList (1,length lst) lst
  print (allsums arr) -- тоже через запятую и в квадратных скобках
  return ()

mergesums :: (Cmp a) => [[a]] -> [a]

mergesums {-lsums-} = foldr merge2 [] {-lsums-}
  where
    merge2 :: [a] -> [a] -> [a]
    xs `merge2` [] = xs
    [] `merge2` ys = ys
    (x:xs) `merge2` (y:ys) | x<y       = x : (   xs  `merge2` (y:ys))
                           | otherwise = y : ((x:xs) `merge2`    ys )

             +--- gensums(1)
output <--merge2    +--- gensums(2)
             +---merge2     +--- gensums(3)
                    +--- merge2
                            .........  +--- gensums(n)
                               +--- merge2
                                       +--- [] (стартовое значение, переданное в foldr)

К>main = do
К>  lst <- read <<= getStrLn -- через запятую, в квадратных скобках
К>  let arr = arrayList (1,length lst) (sort lst)
                                    -- ~~~~~    ~
К>  print (allsums arr) -- тоже через запятую и в квадратных скобках
К>  return ()

M>Как оказалось, условие я и сам неправильно понял. Оказалось, что надо не просто суммы смежных двоек, троек и т.д., а все гораздо хуже Необходимо суммы всех возможных групп чисел вообще. Т.е. а1 + а2, а1 + а3, а1 + а4, ...., а1 + а2 + а3, а1 + а3 + а4, ..., а2 + а3, ..., а2 + а4 + а5, ...

M>И потом получившиеся суммы поставить в порядке возрастания. На вопрос "а нафига это надо", друг не ответил, сказал, что надо А я уже обещался помочь

perm :: [Int] -> [Int]
perm zs = perm' zs (tails zs)
    where perm' [] _ = []
          perm' _ [] = []
          perm' (x:xs) (y:ys) = map ((+) x . sum) ys ++ perm' xs ys