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

Здравствуйте, 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"
------ -- могли бы и дальше перебирать, но здесь суффикс внезапно иссяк

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

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

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

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

BZ>

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

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

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

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

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

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

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

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

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

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

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

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