Здравствуйте, nikov, Вы писали:

N>Если у меня нет возможности анализировать код алгоритма, а только его поведение, то про очень многие алгоритмы нельзя доказать, что они неправильные. Например

N>

N>subs = subs
N>

N>А если еще запретить смотреть на результаты, так и вообще...

Код не поможет. Я мог бы взять какую-нибудь нерешенную математическую задачу, которую
можно вычислительно проверять для последовательности чисел и поставить условие —
если эта гипотеза неверна для текущего N, то переключаемся на алгоритм Булата.

Здравствуйте, deniok, Вы писали:

Q>>Я не должен ничего опровергать. Я утверждаю, что мой алгоритм решает поставленную задачу.

D>А я утверждаю, что он решает другую, несовместимую задачу (выдача одноэлементных последовательностей).
D>Для проверки мы запускаем его и видим, что мое утверждение столь же обосновано, сколь твое

Ну да, мой алгоритм решает обе задачи, хе-хе. Бесконечность она такая штука...

Здравствуйте, Quintanar, Вы писали:

Q>Здравствуйте, deniok, Вы писали:

Q>>>Я не должен ничего опровергать. Я утверждаю, что мой алгоритм решает поставленную задачу.

D>>А я утверждаю, что он решает другую, несовместимую задачу (выдача одноэлементных последовательностей).
D>>Для проверки мы запускаем его и видим, что мое утверждение столь же обосновано, сколь твое

Q>Ну да, мой алгоритм решает обе задачи, хе-хе. Бесконечность она такая штука...

К сожалению такого не бывает. Решения у этих задач разные, так что больше одной не выйдет.

Здравствуйте, Буравчик, Вы писали:

Б>Ошибка в выделенном. Должно быть [ [x] ]

Семён Семёныч!!! Вот что значит — могущество копипаста. А я, блин, понадеялся на скорость слепого набора. Действительно, слепого

Здравствуйте, Кодт, Вы писали:

К>Нужно избавляться от арифметики.

Вот так получилось:

subs [] = [[]]
subs (x:xs) = [] : [x] : liftM2 (flip ($)) (tail (subs xs)) [id, (x:)]

Здравствуйте, nikov, Вы писали:

N>Вот так получилось:
И, если убрать еще небольшое дублирование кода,

subs [] = [[]]
subs (x:xs) = liftM2 (flip ($)) ([] : tail (subs xs)) [id, (x:)]

Здравствуйте, nikov, Вы писали:

N>И, если убрать еще небольшое дублирование кода,

Нашел подходящий стандартный комбинатор:

import Control.Applicative

subs [] = [[]]
subs (x:xs) = [] : tail (subs xs) <**> [id, (x:)]

Здравствуйте, Quintanar, Вы писали:

H>>Надо написать функцию, которая, получив на вход список (конечный или бесконечный), вернет список всех его конечных подпоследовательностей. Для бесконечного исходного списка подпоследовательностей должно быть, естественно, бесконечно много. Помогите, пожалуйста.

Q>Для бесконечного списка — это несчетное множество, что делает задачу несколько бессмысленной.

А по-моему, счётное.

Каждой подпоследовательности поставим в соответствие двоичную дробь вида 0.xyz.... где i-й разряд выставлен в 1, если этот i-й элемент списка включён в подпоследовательность, и 0, если не включён.
У конечной подпоследовательности, очевидно, конечное количество единичек, и после последней единички идут одни нули.
Таким образом, всем конечным подпоследовательностям соответствуют конечные двоичные дроби — это подмножество рациональных чисел, а рациональные числа счётны.

Ну а если мы воспользуемся тем, что последовательность кодируется конечным двоичным вектором, то отзеркалим дробь 0.xy...z1 --> 1z...yx.0 и получим натуральное число.
Несложно показать, что такие натуральные числа взаимно-однозначно определяют последовательности — т.е. любому числу соответствует какая-то уникальная последовательность, и любой последовательности соответствует какое-то уникальное число.
Отсюда очень просто написать функцию

nth_subseq :: Integer -> [a] -> [a]

nth_subseq 0 _ = []
nth_subseq k (x:xs) = if odd k then x:rest else rest where rest = nth_subseq (k`div`2) xs
nth_subseq _ _ = error "index out of range"

Здравствуйте, Кодт, Вы писали:

H>>>Надо написать функцию, которая, получив на вход список (конечный или бесконечный), вернет список всех его конечных подпоследовательностей. Для бесконечного исходного списка подпоследовательностей должно быть, естественно, бесконечно много. Помогите, пожалуйста.

Q>>Для бесконечного списка — это несчетное множество, что делает задачу несколько бессмысленной.

К>А по-моему, счётное.

я думаю, он перепутал с подмножествами. здесь же бе всяких хистростев имеем N^2, где N — мощность счётного множества. для подмножеств же будет несчётное 2^N

Здравствуйте, BulatZiganshin, Вы писали:

BZ>я думаю, он перепутал с подмножествами. здесь же бе всяких хистростев имеем N^2, где N — мощность счётного множества. для подмножеств же будет несчётное 2^N

Конечные/бесконечные подпоследовательности списка-как-последовательности суть конечные/бесконечные (соответственно) подмножества списка-как-множества.
И ровно тем же способом проецируются на [0;1] и [0..]

Здравствуйте, hexamino, Вы писали:

H>Надо написать функцию, которая, получив на вход список (конечный или бесконечный), вернет список всех его конечных подпоследовательностей. Для бесконечного исходного списка подпоследовательностей должно быть, естественно, бесконечно много. Помогите, пожалуйста.

filterM (const [False,True])

Здравствуйте, Аноним, Вы писали:

А>filterM (const [False,True])

Это не работает с бесконечными списками.

А вот так будет работать:

subs xs = [ start ++ [x] | (ys, x:_) <- zip (inits xs) (tails xs), start <- filterM (const [False,True]) ys ]