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

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

К>>>Тривиальная? Вон Булат с разбега дал красивое и неправильное решение. А nikov-у пришлось прибегнуть к арифметике.
T>>Это получение 2^n, по-моему. Вся сложность в трудности проверок.
К>Поясни. Не понял твою мысль насчёт трудности проверок.

Большой размер получающихся данных.

Как доказать, что subsequences [1..n] совпадает с первыми 2^n элементами subsequences [1..n+1].

T>>Второе: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v%3Asubsequences
T>>Проблемы могут быть с бесконечностью, тут уже начинаются нюансы.
К>Не просто могут быть, а сразу есть.
К>subsequences[0..] рожает [] и затем бесконечный поток одноэлементных списков [0],[1],...

Вот это, как раз, и есть нюанс.

Что лучше — бесконечный поток одноэлементных списков, или бесконечный поток каких-либо других списков?

И, кстати:

*Omega> Data.List.subsequences [1..1]
[[],[1]]
*Omega> Data.List.subsequences [1..2]
[[],[1],[2],[1,2]]
*Omega> Data.List.subsequences [1..3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
*Omega> Data.List.subsequences [1..4]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],
[2,3,4],[1,2,3,4]]
*Omega> Data.List.subsequences [1..5]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],
[2,3,4],[1,2,3,4],[5],[1,5],[2,5],[1,2,5],[3,5],[1,3,5],[2,3,5],[1,2,3,5],[4,5],
[1,4,5],[2,4,5],[1,2,4,5],[3,4,5],[1,3,4,5],[2,3,4,5],[1,2,3,4,5]]

Начало subsequences [1..n] совпадает с началом subsequences [1..n+1]. Поэтому я считаю, что ты проверял свои выкладки на каком-то неправильном subsequences.

Тот, что в Data.List, хороший. Тот, что использовал ты, не очень.

T>>Здесь может помочь http://hackage.haskell.org/package/control-monad-omega
К>Прикольно. А можешь избавить меня от труда по вчитыванию в предмет, и на пальцах рассказать и показать про эту монаду Омега? Буду премного благодарен.

Вот выражение:

do
    x <- list_a
    y <- list_b
    return $ f x y

Обычная монада списка сперва выберет все элементы из list_a, а потом все элементы из list_b. Если list_a бесконечен, то мы получим на выходе map (\x -> f x (head list_b)) list_a, элементы второго списка перебираться не будут.

diagonal позволяет выбирать элементы "по диагонали", перебирая пары "в ширину".

Для переборных алгоритмов самое то.

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

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

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

import Control.Applicative

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

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

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

sub (x:xs) = [[x]] ++ concatMap (\a -> [x:a,a]) (sub xs)
sub [] = []

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

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

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

Множество всех подмножеств счетного множества — несчетно. А множество конечных подмножеств счетного множества — счетно.

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

Q>Хмм, да. Но все равно смысла в такой постановке задачи мало — как я уже сказал, я могу возвращать
Q>сначала все одноэлементные подмножества. Это значительно проще, а условию не противоречит.

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

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

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

subs [] = [[]]
subs (x:xs) = liftM2 (flip ($)) ([] : 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"

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

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

Конечная подпоследовательность — подпоследовательность, содержащаяся в конце списка.

На конце списка всегда находится пустой список. [].

Единственная подпоследовательность, содержащаяся в пустом списке, это пустой список.

Поэтому решение твоей задачи просто:

subsequences [] = []
subsequences (x:xs) = subsequences xs

Для бесконечного входного списка точное число подпоследовательностей не определено (_|_). Определение выше этому соответствует, надо сказать.

Думаю, смело могу сказать, что моё решение самое простое и самое краткое.

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

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

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

finiteSublists :: [a] -> [[a]]
finiteSublists xs = concat f
  where f = [[]] : [map (++[x]) $ concat $ take (n+1) f | (x,n) <- zip xs [0..]]

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

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

План такой: для каждого элемента списка найти все последовательности головной части списка, не доходящей до него, плюс этот элемент.

splits :: [a] -> [([a],a)] -- разбивает на сочетания (префикс, голова суффикса)
splits xs = splits' [] xs where
    splits' _ [] = []
    splits' ys (z:zs) = (ys,z) : splits' (ys++[z]) zs

finites :: [a] -> [[a]]
finites xs =
    [[]] -- пустая есть всегда
    ++
    concat (map make' pairs') where
        make' (ys,z) = map (++[z]) (subsequences ys)
        pairs' = splits xs

subsequences xs = finites xs -- либо любой другой алгоритм (который может уже заложиться на то, что xs конечный)

Можно попробовать всё это добро выразить в линзах-бананах или ZF-нотации. Но, боюсь, понятность кода от этого проиграет.

Проверяем

test xs = do
    putStrLn $ "source is " ++ show xs
    let q___q = map (const '-') $ show xs
    putStrLn q___q
    let ss = finites xs
    mapM_ (putStrLn . show) ss
    putStrLn q___q

main = do
    test ""
    test "abcd"

на выходе

source is ""
--
""
--

source is "a"
---
""
"a"
---

source is "abcd"
------
""     -- первый (особый) случай

"a"    -- разбили на "",'a',...

"b"    -- разбили на "a",'b',...
"ab"

"c"    -- разбили на "ab",'c',...
"ac"
"bc"
"abc"

"d"    -- разбили на "abc",'d',...
"ad"
"bd"
"abd"
"cd"
"acd"
"bcd"
"abcd"
------ -- могли бы и дальше перебирать, но здесь суффикс внезапно иссяк

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

BZ>

BZ>sub (x:xs) = [[x]] ++ concatMap (\a -> [x:a,a]) (sub xs)
BZ>sub [] = []
BZ>

Не хватает пустой подпоследовательнсти.

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

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

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

T>Конечная подпоследовательность — подпоследовательность, содержащаяся в конце списка.

Нет, конечная — это содержащая конечное (не бесконечное) число элементов.

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

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

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

T>Конечная подпоследовательность — подпоследовательность, содержащаяся в конце списка.

T>На конце списка всегда находится пустой список. [].

T>Единственная подпоследовательность, содержащаяся в пустом списке, это пустой список.

Прикольный ответ, конечно, хотя автор имел в виду не такое понимание "конечных подпоследовательностей"
Но если принять Ваш вариант ТЗ, то вот решение короче:

f xs = []

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

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

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

T>>Конечная подпоследовательность — подпоследовательность, содержащаяся в конце списка.

G>Прикольный ответ, конечно, хотя автор имел в виду не такое понимание "конечных подпоследовательностей"
G>Но если принять Ваш вариант ТЗ, то вот решение короче:

G>

f xs = []

К сожалению, это не проходит для бесконечной последовательности.

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

T>К сожалению, это не проходит для бесконечной последовательности.

хм, тогда да...

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

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

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

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

T>>Конечная подпоследовательность — подпоследовательность, содержащаяся в конце списка.
H>Нет, конечная — это содержащая конечное (не бесконечное) число элементов.

Смотрим на http://hexamino.blogspot.com/ (из твоего профиля)

Видим там вот такое:

Дополнительные навыки: C++, Java, Scala, Haskell, F#, VB.NET, JavaScript, HTML, XML/XSLT, T-SQL; работа с базами данных, разработка web-приложений, обработка финансовых данных.

Я считаю, что ты наврал в рекламе самого себя, поскольку спрашиваешь решение тривиальной задачи.

Я считаю, что это плохо. Поэтому я не буду решать эту и другие задачи, которые ты здесь будешь излагать.

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

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

BZ>sub (x:xs) = [[x]] ++ concatMap (\a -> [x:a,a]) (sub xs)
BZ>sub [] = []

Что-то криво получается. С повторениями.
subs ['A'..] =
""
"A"
""
"AB"
"B"
"A"
""
"ABC"
"BC"
"AC"
"C"
"AB"
"B"
"A"
""
"ABCD"
"BCD"
"ACD"
"CD"
"ABD"
"BD"
"AD"
"D"
"ABC"
"BC"
"AC"
"C"
"AB"
"B"
"A"
""
...

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

T>Я считаю, что ты наврал в рекламе самого себя, поскольку спрашиваешь решение тривиальной задачи.

Тривиальная? Вон Булат с разбега дал красивое и неправильное решение. А nikov-у пришлось прибегнуть к арифметике.

Кстати, то, что ты назвал "конечной", вообще-то, "концевая".

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

T>Видим там вот такое:

Дополнительные навыки: C++, Java, Scala, Haskell, F#, VB.NET, JavaScript, HTML, XML/XSLT, T-SQL; работа с базами данных, разработка web-приложений, обработка финансовых данных.

T>Я считаю, что ты наврал в рекламе самого себя, поскольку спрашиваешь решение тривиальной задачи.

А что мне думать о тебе, после того, как ты даже не смог понять ее условие?
На самом деле, у меня было свое решение, но оно было более громоздкое, чем приведенные в этой ветке. К сожалению, Haskell — не мой основной навык, о чем я и написал в своем блоге.

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

К>

BZ>>sub (x:xs) = [[x]] ++ concatMap (\a -> [x:a,a]) (sub xs)
BZ>>sub [] = []
К>

К>Что-то криво получается. С повторениями.
К>subs ['A'..] =

sub /= subs

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

К>>Что-то криво получается. С повторениями.
К>>subs ['A'..] =

BZ>sub /= subs

Это я очепятался, когда писал сообщение. А sub всё равно рожает с повторениями.

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

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

T>>Я считаю, что ты наврал в рекламе самого себя, поскольку спрашиваешь решение тривиальной задачи.

К>Тривиальная? Вон Булат с разбега дал красивое и неправильное решение. А nikov-у пришлось прибегнуть к арифметике.

Это получение 2^n, по-моему. Вся сложность в трудности проверок.

Второе: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v%3Asubsequences

Проблемы могут быть с бесконечностью, тут уже начинаются нюансы.

Здесь может помочь http://hackage.haskell.org/package/control-monad-omega

К>Кстати, то, что ты назвал "конечной", вообще-то, "концевая".

Для автора исходного задания мне ничего не жалко.

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

N>

N>finiteSublists :: [a] -> [[a]]
N>finiteSublists xs = concat f
N>  where f = [[]] : [map (++[x]) $ concat $ take (n+1) f | (x,n) <- zip xs [0..]]
N>

Поскольку take::Int->..., то [0..] = [0::Int..] = [0..2^31-1]
В общем, не очень далеко уедем.
Нужно избавляться от арифметики.

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

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

Да мне самому не нравится. Не декларативно.

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

К>Это я очепятался, когда писал сообщение. А sub всё равно рожает с повторениями.

А у меня все работает

*Main Data.List> mapM_ (putStrLn.show) $ take 30 $ sub' ['A'..]
"A"
"AB"
"B"
"ABC"
"BC"
"AC"
"C"
"ABCD"
"BCD"
"ACD"
"CD"
"ABD"
"BD"
"AD"
"D"
"ABCDE"
"BCDE"
"ACDE"
"CDE"
"ABDE"
"BDE"
"ADE"
"DE"
"ABCE"
"BCE"
"ACE"
"CE"
"ABE"
"BE"
"AE"

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

К>>Тривиальная? Вон Булат с разбега дал красивое и неправильное решение. А nikov-у пришлось прибегнуть к арифметике.

T>Это получение 2^n, по-моему. Вся сложность в трудности проверок.

Поясни. Не понял твою мысль насчёт трудности проверок.

T>Второе: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v%3Asubsequences
T>Проблемы могут быть с бесконечностью, тут уже начинаются нюансы.

Не просто могут быть, а сразу есть.
subsequences[0..] рожает [] и затем бесконечный поток одноэлементных списков [0],[1],...

T>Здесь может помочь http://hackage.haskell.org/package/control-monad-omega

Прикольно. А можешь избавить меня от труда по вчитыванию в предмет, и на пальцах рассказать и показать про эту монаду Омега? Буду премного благодарен.

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

Б>А у меня все работает

Странно... видать, где-то я очепятнулся.

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

К>Странно... видать, где-то я очепятнулся.

Блин. Колдунство какое-то

sub (x:xs) = [[]] ++ concatMap (\a -> [x:a,a]) (sub xs)
sub [] = []

test fun xs = do
    putStrLn $ "source is " ++ show xs
    let q___q = map (const '-') $ show xs
    putStrLn q___q
    let ss = fun xs
    mapM_ (putStrLn . show) ss
    putStrLn q___q

main = do
    test sub ['A'..'Z']

Выводит с дырками.

А если вбить let sub[]=[]; sub(x:xs)=..... в интерпретаторе руками — то без дырок.
Ниччего не понимаю.

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

К>Блин. Колдунство какое-то

sub (x:xs) = [[]] ++ concatMap (\a -> [x:a,a]) (sub xs)
sub [] = []

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

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

К>Что-то криво получается. С повторениями.

что-то ты всё напутал. вот как у меня:

["A","AB","B","ABC","BC","AC","C","ABCD","BCD","ACD","CD","ABD","BD","AD","D","ABCDE","BCDE","ACDE","CDE","ABDE","BDE","ADE","DE","ABCE","B
CE","ACE","CE","ABE","BE","AE","E","ABCDEF","BCDEF","ACDEF","CDEF","ABDEF","BDEF","ADEF","DEF","ABCEF","BCEF","ACEF","CEF","ABEF","BEF","AE
F","EF","ABCDF","BCDF","ACDF","CDF","ABDF","BDF","ADF","DF","ABCF","BCF","ACF","CF","ABF","BF","AF","F","ABCDEFG","BCDEFG","ACDEFG","CDEFG"
,"ABDEFG","BDEFG","ADEFG","DEFG","ABCEFG","BCEFG","ACEFG","CEFG","ABEFG","BEFG","AEFG","EFG","ABCDFG","BCDFG","ACDFG","CDFG","ABDFG","BDFG"
,"ADFG","DFG","ABCFG","BCFG","ACFG","CFG","ABFG","BFG","AFG","FG","ABCDEG","BCDEG","ACDEG","CDEG","ABDEG","BDEG","ADEG","DEG","ABCEG","BCEG
","ACEG","CEG","ABEG","BEG","AEG","EG","ABCDG","BCDG","ACDG","CDG","ABDG","BDG","ADG","DG","ABCG","BCG","ACG","CG","ABG","BG","AG","G","ABC
DEFGH","BCDEFGH","ACDEFGH","CDEFGH","ABDEFGH","BDEFGH","ADEFGH","DEFGH","ABCEFGH","BCEFGH","ACEFGH","CEFGH","ABEFGH","BEFGH","AEFGH","EFGH"
,"ABCDFGH","BCDFGH","ACDFGH","CDFGH","ABDFGH","BDFGH","ADFGH","DFGH","ABCFGH","BCFGH","ACFGH","CFGH","ABFGH","BFGH","AFGH","FGH","ABCDEGH",
"BCDEGH","ACDEGH","CDEGH","ABDEGH","BDEGH","ADEGH","DEGH","ABCEGH","BCEGH","ACEGH","CEGH","ABEGH","BEGH","AEGH","EGH","ABCDGH","BCDGH","ACD
GH","CDGH","ABDGH","BDGH","ADGH","DGH","ABCGH","BCGH","ACGH","CGH","ABGH","BGH","AGH","GH","ABCDEFH","BCDEFH","ACDEFH","CDEFH","ABDEFH","BD
EFH","ADEFH","DEFH","ABCEFH","BCEFH","ACEFH","CEFH","ABEFH","BEFH","AEFH","EFH","ABCDFH","BCDFH","ACDFH","CDFH","ABDFH","BDFH","ADFH","DFH"
,"ABCFH","BCFH","ACFH","CFH","ABFH","BFH","AFH","FH","ABCDEH","BCDEH","ACDEH","CDEH","ABDEH","BDEH","ADEH","DEH","ABCEH","BCEH","ACEH","CEH
","ABEH","BEH","AEH","EH","ABCDH","BCDH","ACDH","CDH","ABDH","BDH","ADH","DH","ABCH","BCH","ACH","CH","ABH","BH","AH","H","ABCDEFGHI","BCDE
FGHI","ACDEFGHI","CDEFGHI","ABDEFGHI","BDEFGHI","ADEFGHI","DEFGHI","ABCEFGHI","BCEFGHI","ACEFGHI","CEFGHI","ABEFGHI","BEFGHI","AEFGHI","EFG
HI","ABCDFGHI","BCDFGHI","ACDFGHI","CDFGHI","ABDFGHI","BDFGHI","ADFGHI","DFGHI","ABCFGHI","BCFGHI","ACFGHI","CFGHI","ABFGHI","BFGHI","AFGHI
","FGHI","ABCDEGHI","BCDEGHI","ACDEGHI","CDEGHI","ABDEGHI","BDEGHI","ADEGHI","DEGHI","ABCEGHI","BCEGHI","ACEGHI","CEGHI","ABEGHI","BEGHI","
AEGHI","EGHI","ABCDGHI","BCDGHI","ACDGHI","CDGHI","ABDGHI","BDGHI","ADGHI","DGHI","ABCGHI","BCGHI","ACGHI","CGHI","ABGHI","BGHI","AGHI","GH
I","ABCDEFHI","BCDEFHI","ACDEFHI","CDEFHI","ABDEFHI","BDEFHI","ADEFHI","DEFHI","ABCEFHI","BCEFHI","ACEFHI","CEFHI","ABEFHI","BEFHI","AEFHI"
,"EFHI","ABCDFHI","BCDFHI","ACDFHI","CDFHI","ABDFHI","BDFHI","ADFHI","DFHI","ABCFHI","BCFHI","ACFHI","CFHI","ABFHI","BFHI","AFHI","FHI","AB
CDEHI","BCDEHI","ACDEHI","CDEHI","ABDEHI","BDEHI","ADEHI","DEHI","ABCEHI","BCEHI","ACEHI","CEHI","ABEHI","BEHI","AEHI","EHI","ABCDHI","BCDH
I","ACDHI","CDHI","ABDHI","BDHI","ADHI","DHI","ABCHI","BCHI","ACHI","CHI","ABHI","BHI","AHI","HI","ABCDEFGI","BCDEFGI","ACDEFGI","CDEFGI","
ABDEFGI","BDEFGI","ADEFGI","DEFGI","ABCEFGI","BCEFGI","ACEFGI","CEFGI","ABEFGI","BEFGI","AEFGI","EFGI","ABCDFGI","BCDFGI","ACDFGI","CDFGI",
"ABDFGI","BDFGI","ADFGI","DFGI","ABCFGI","BCFGI","ACFGI","CFGI","ABFGI","BFGI","AFGI","FGI","ABCDEGI","BCDEGI","ACDEGI","CDEGI","ABDEGI","B
DEGI","ADEGI","DEGI","ABCEGI","BCEGI","ACEGI","CEGI","ABEGI","BEGI","AEGI","EGI","ABCDGI","BCDGI","ACDGI","CDGI","ABDGI","BDGI","ADGI","DGI
","ABCGI","BCGI","ACGI","CGI","ABGI","BGI","AGI","GI","ABCDEFI","BCDEFI","ACDEFI","CDEFI","ABDEFI","BDEFI","ADEFI","DEFI","ABCEFI","BCEFI",
"ACEFI","CEFI","ABEFI","BEFI","AEFI","EFI","ABCDFI","BCDFI","ACDFI","CDFI","ABDFI","BDFI","ADFI","DFI","ABCFI","BCFI","ACFI","CFI","ABFI","
BFI","AFI","FI","ABCDEI","BCDEI","ACDEI","CDEI","ABDEI","BDEI","ADEI","DEI","ABCEI","BCEI","ACEI","CEI","ABEI","BEI","AEI","EI","ABCDI","BC
DI","ACDI","CDI","ABDI","BDI","ADI","DI","ABCI","BCI","ACI","CI","ABI","BI","AI","I","ABCDEFGHIJ","BCDEFGHIJ","ACDEFGHIJ","CDEFGHIJ","ABDEF
GHIJ","BDEFGHIJ","ADEFGHIJ","DEFGHIJ","ABCEFGHIJ","BCEFGHIJ","ACEFGHIJ","CEFGHIJ","ABEFGHIJ","BEFGHIJ","AEFGHIJ","EFGHIJ","ABCDFGHIJ","BCDF
GHIJ","ACDFGHIJ","CDFGHIJ","ABDFGHIJ","BDFGHIJ","ADFGHIJ","DFGHIJ","ABCFGHIJ","BCFGHIJ","ACFGHIJ","CFGHIJ","ABFGHIJ","BFGHIJ","AFGHIJ","FGH
IJ","ABCDEGHIJ","BCDEGHIJ","ACDEGHIJ","CDEGHIJ","ABDEGHIJ","BDEGHIJ","ADEGHIJ","DEGHIJ","ABCEGHIJ","BCEGHIJ","ACEGHIJ","CEGHIJ","ABEGHIJ","
BEGHIJ","AEGHIJ","EGHIJ","ABCDGHIJ","BCDGHIJ","ACDGHIJ","CDGHIJ","ABDGHIJ","BDGHIJ","ADGHIJ","DGHIJ","ABCGHIJ","BCGHIJ","ACGHIJ","CGHIJ","A
BGHIJ","BGHIJ","AGHIJ","GHIJ","ABCDEFHIJ","BCDEFHIJ","ACDEFHIJ","CDEFHIJ","ABDEFHIJ","BDEFHIJ","ADEFHIJ","DEFHIJ","ABCEFHIJ","BCEFHIJ","ACE
FHIJ","CEFHIJ","ABEFHIJ","BEFHIJ","AEFHIJ","EFHIJ","ABCDFHIJ","BCDFHIJ","ACDFHIJ","CDFHIJ","ABDFHIJ","BDFHIJ","ADFHIJ","DFHIJ","ABCFHIJ","B
CFHIJ","ACFHIJ","CFHIJ","ABFHIJ","BFHIJ","AFHIJ","FHIJ","ABCDEHIJ","BCDEHIJ","ACDEHIJ","CDEHIJ","ABDEHIJ","BDEHIJ","ADEHIJ","DEHIJ","ABCEHI
J","BCEHIJ","ACEHIJ","CEHIJ","ABEHIJ","BEHIJ","AEHIJ","EHIJ","ABCDHIJ","BCDHIJ","ACDHIJ","CDHIJ","ABDHIJ","BDHIJ","ADHIJ","DHIJ","ABCHIJ","
BCHIJ","ACHIJ","CHIJ","ABHIJ","BHIJ","AHIJ","HIJ","ABCDEFGIJ","BCDEFGIJ","ACDEFGIJ","CDEFGIJ","ABDEFGIJ","BDEFGIJ","ADEFGIJ","DEFGIJ","ABCE
FGIJ","BCEFGIJ","ACEFGIJ","CEFGIJ","ABEFGIJ","BEFGIJ","AEFGIJ","EFGIJ","ABCDFGIJ","BCDFGIJ","ACDFGIJ","CDFGIJ","ABDFGIJ","BDFGIJ","ADFGIJ",
"DFGIJ","ABCFGIJ","BCFGInterrupted.

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

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

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

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


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

И какие же конечные ненулевые подпоследовательности пропускает

sub (x:xs) = [[x]] ++ concatMap (\a -> [x:a,a]) (sub xs)
sub [] = []
-- (c) Булат

которая конструктивно нумерует искомое множество?

Prelude> take 100 $ sub [1..]
[[1],[1,2],[2],[1,2,3],[2,3],[1,3],[3],[1,2,3,4],[2,3,4],[1,3,4],[3,4],[1,2,4],[
2,4],[1,4],[4],[1,2,3,4,5],[2,3,4,5],[1,3,4,5],[3,4,5],[1,2,4,5],[2,4,5],[1,4,5]
,[4,5],[1,2,3,5],[2,3,5],[1,3,5],[3,5],[1,2,5],[2,5],[1,5],[5],[1,2,3,4,5,6],[2,
3,4,5,6],[1,3,4,5,6],[3,4,5,6],[1,2,4,5,6],[2,4,5,6],[1,4,5,6],[4,5,6],[1,2,3,5,
6],[2,3,5,6],[1,3,5,6],[3,5,6],[1,2,5,6],[2,5,6],[1,5,6],[5,6],[1,2,3,4,6],[2,3,
4,6],[1,3,4,6],[3,4,6],[1,2,4,6],[2,4,6],[1,4,6],[4,6],[1,2,3,6],[2,3,6],[1,3,6]
,[3,6],[1,2,6],[2,6],[1,6],[6],[1,2,3,4,5,6,7],[2,3,4,5,6,7],[1,3,4,5,6,7],[3,4,
5,6,7],[1,2,4,5,6,7],[2,4,5,6,7],[1,4,5,6,7],[4,5,6,7],[1,2,3,5,6,7],[2,3,5,6,7]
,[1,3,5,6,7],[3,5,6,7],[1,2,5,6,7],[2,5,6,7],[1,5,6,7],[5,6,7],[1,2,3,4,6,7],[2,
3,4,6,7],[1,3,4,6,7],[3,4,6,7],[1,2,4,6,7],[2,4,6,7],[1,4,6,7],[4,6,7],[1,2,3,6,
7],[2,3,6,7],[1,3,6,7],[3,6,7],[1,2,6,7],[2,6,7],[1,6,7],[6,7],[1,2,3,4,5,7],[2,
3,4,5,7],[1,3,4,5,7],[3,4,5,7],[1,2,4,5,7]]

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

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


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

D>И какие же конечные ненулевые подпоследовательности пропускает

Подмножества бесконечного множества — это набор бесконечных последовательностей из 0 и 1, т.е.
вещественные числа. Это несчетное множество и хоть я не могу сказать, что именно пропускает эта прога,
она обязательно что-то пропускает, поскольку программа может перенумеровать только счетное множество.
Она неверна в принципе при такой постановке задачи. Надо явно оговаривать, что она должна работать
именно так, а то я, например, считаю, что сначала должны возвращаться все одноэлементные подмножества
и это тоже будет верное решение.

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

Q>Подмножества бесконечного множества — это набор бесконечных последовательностей из 0 и 1, т.е.
Q>вещественные числа.

Не, там в условии "список всех его конечных подпоследовательностей".

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

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

Q>>Подмножества бесконечного множества — это набор бесконечных последовательностей из 0 и 1, т.е.
Q>>вещественные числа.

D>Не, там в условии "список всех его конечных подпоследовательностей".

Хмм, да. Но все равно смысла в такой постановке задачи мало — как я уже сказал, я могу возвращать
сначала все одноэлементные подмножества. Это значительно проще, а условию не противоречит.

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

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

Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.
А возвращать множества, удовлетворяющие условию задачи, моя программа может сколь угодно долго.

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

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

Q>Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.

В условии есть слово "всех". Очевидно, что предложенный тобой алгоритм никогда не вернет некоторые из конечных последовательностей.

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

Q>>Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.

N>В условии есть слово "всех". Очевидно, что предложенный тобой алгоритм никогда не вернет некоторые из конечных последовательностей.

Это очевидно, если признавать операции с бесконечностью. А теперь представим, что я выдал этот
алгоритм тебе в черном ящике. Сможешь ли ты доказать, что он чего-то не вернет, пусть даже
за бесконечное время? Нет. Значит, это правильный алгоритм.

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

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

Q>>>Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.

N>>В условии есть слово "всех". Очевидно, что предложенный тобой алгоритм никогда не вернет некоторые из конечных последовательностей.

Q>Это очевидно, если признавать операции с бесконечностью. А теперь представим, что я выдал этот
Q>алгоритм тебе в черном ящике. Сможешь ли ты доказать, что он чего-то не вернет, пусть даже
Q>за бесконечное время? Нет. Значит, это правильный алгоритм.


Но и ты не сможешь опровергнуть утверждение, что этот алгоритм выдает только одноэлементные последовательности (не решая, тем самым, задачу). Утверждения о черных ящиках они такие

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

Q>А теперь представим, что я выдал этот
Q>алгоритм тебе в черном ящике. Сможешь ли ты доказать, что он чего-то не вернет, пусть даже
Q>за бесконечное время? Нет.

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

subs = subs

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

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

D>Но и ты не сможешь опровергнуть утверждение, что этот алгоритм выдает только одноэлементные последовательности (не решая, тем самым, задачу). Утверждения о черных ящиках они такие

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

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

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

D>>Но и ты не сможешь опровергнуть утверждение, что этот алгоритм выдает только одноэлементные последовательности (не решая, тем самым, задачу). Утверждения о черных ящиках они такие

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

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

Здравствуйте, 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:)]

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

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 ]