Здравствуйте, thesz, Вы писали:
К>>Тривиальная? Вон Булат с разбега дал красивое и неправильное решение. А nikov-у пришлось прибегнуть к арифметике.
T>Это получение 2^n, по-моему. Вся сложность в трудности проверок.
Здравствуйте, Кодт, Вы писали:
К>Странно... видать, где-то я очепятнулся.
Блин. Колдунство какое-то
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)=..... в интерпретаторе руками — то без дырок.
Ниччего не понимаю.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[8]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, 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],...
Вот это, как раз, и есть нюанс.
Что лучше — бесконечный поток одноэлементных списков, или бесконечный поток каких-либо других списков?
Начало 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 позволяет выбирать элементы "по диагонали", перебирая пары "в ширину".
Для переборных алгоритмов самое то.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[3]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, hexamino, Вы писали:
H>Надо написать функцию, которая, получив на вход список (конечный или бесконечный), вернет список всех его конечных подпоследовательностей. Для бесконечного исходного списка подпоследовательностей должно быть, естественно, бесконечно много. Помогите, пожалуйста.
Для бесконечного списка — это несчетное множество, что делает задачу несколько бессмысленной. Для конечного
списка задача кажется мегатривиальной.
Re[2]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, deniok, Вы писали:
D>Здравствуйте, Quintanar, Вы писали:
Q>>Для бесконечного списка — это несчетное множество, что делает задачу несколько бессмысленной.
D>И какие же конечные ненулевые подпоследовательности пропускает
Подмножества бесконечного множества — это набор бесконечных последовательностей из 0 и 1, т.е.
вещественные числа. Это несчетное множество и хоть я не могу сказать, что именно пропускает эта прога,
она обязательно что-то пропускает, поскольку программа может перенумеровать только счетное множество.
Она неверна в принципе при такой постановке задачи. Надо явно оговаривать, что она должна работать
именно так, а то я, например, считаю, что сначала должны возвращаться все одноэлементные подмножества
и это тоже будет верное решение.
Re[2]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Quintanar, Вы писали:
H>>Надо написать функцию, которая, получив на вход список (конечный или бесконечный), вернет список всех его конечных подпоследовательностей. Для бесконечного исходного списка подпоследовательностей должно быть, естественно, бесконечно много. Помогите, пожалуйста.
Q>Для бесконечного списка — это несчетное множество, что делает задачу несколько бессмысленной.
Множество всех подмножеств счетного множества — несчетно. А множество конечных подмножеств счетного множества — счетно.
Re[4]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Quintanar, Вы писали:
Q>Подмножества бесконечного множества — это набор бесконечных последовательностей из 0 и 1, т.е. Q>вещественные числа.
Не, там в условии "список всех его конечных подпоследовательностей".
Re[5]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, deniok, Вы писали:
D>Здравствуйте, Quintanar, Вы писали:
Q>>Подмножества бесконечного множества — это набор бесконечных последовательностей из 0 и 1, т.е. Q>>вещественные числа.
D>Не, там в условии "список всех его конечных подпоследовательностей".
Хмм, да. Но все равно смысла в такой постановке задачи мало — как я уже сказал, я могу возвращать
сначала все одноэлементные подмножества. Это значительно проще, а условию не противоречит.
Re[6]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Quintanar, Вы писали:
Q>Хмм, да. Но все равно смысла в такой постановке задачи мало — как я уже сказал, я могу возвращать Q>сначала все одноэлементные подмножества. Это значительно проще, а условию не противоречит.
Противоречит
Приведенное Булатом решение за конечное время добирается до любой наперед заданной подпоследовательности, то есть решает поставленную задачу нахождения всех конечных подпоследовательностей. Твое решение этого не делает.
Re[7]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, deniok, Вы писали:
D>Противоречит D>Приведенное Булатом решение за конечное время добирается до любой наперед заданной подпоследовательности, то есть решает поставленную задачу нахождения всех конечных подпоследовательностей. Твое решение этого не делает.
Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.
А возвращать множества, удовлетворяющие условию задачи, моя программа может сколь угодно долго.
Re[8]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Quintanar, Вы писали:
D>>Противоречит D>>Приведенное Булатом решение за конечное время добирается до любой наперед заданной подпоследовательности, то есть решает поставленную задачу нахождения всех конечных подпоследовательностей. Твое решение этого не делает.
Q>Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.
В условии есть слово "всех". Очевидно, что предложенный тобой алгоритм никогда не вернет некоторые из конечных последовательностей.
Re[9]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, nikov, Вы писали:
Q>>Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.
N>В условии есть слово "всех". Очевидно, что предложенный тобой алгоритм никогда не вернет некоторые из конечных последовательностей.
Это очевидно, если признавать операции с бесконечностью. А теперь представим, что я выдал этот
алгоритм тебе в черном ящике. Сможешь ли ты доказать, что он чего-то не вернет, пусть даже
за бесконечное время? Нет. Значит, это правильный алгоритм.
Re[10]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, nikov, Вы писали:
Q>>>Не очень существенное замечание, поскольку требования вернуть любую наперед заданную последовательность в задаче нет.
N>>В условии есть слово "всех". Очевидно, что предложенный тобой алгоритм никогда не вернет некоторые из конечных последовательностей.
Q>Это очевидно, если признавать операции с бесконечностью. А теперь представим, что я выдал этот Q>алгоритм тебе в черном ящике. Сможешь ли ты доказать, что он чего-то не вернет, пусть даже Q>за бесконечное время? Нет. Значит, это правильный алгоритм.
Но и ты не сможешь опровергнуть утверждение, что этот алгоритм выдает только одноэлементные последовательности (не решая, тем самым, задачу). Утверждения о черных ящиках они такие
Re[10]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Quintanar, Вы писали:
Q>А теперь представим, что я выдал этот Q>алгоритм тебе в черном ящике. Сможешь ли ты доказать, что он чего-то не вернет, пусть даже Q>за бесконечное время? Нет.
Если у меня нет возможности анализировать код алгоритма, а только его поведение, то про очень многие алгоритмы нельзя доказать, что они неправильные. Например
subs = subs
А если еще запретить смотреть на результаты, так и вообще...
Re[11]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, deniok, Вы писали:
D>Но и ты не сможешь опровергнуть утверждение, что этот алгоритм выдает только одноэлементные последовательности (не решая, тем самым, задачу). Утверждения о черных ящиках они такие
Я не должен ничего опровергать. Я утверждаю, что мой алгоритм решает поставленную задачу. Конструктивного
способа доказать обратное нет (или пока не привели такое). А доказательства оперирующие бесконечностью я
не принимаю, ведь мы находимся в мире алгоритмов
Я бы даже сказал, что моя программа намного лучше, поскольку она потребляет меньше ресурсов
и более короткая и понятная.
Re[12]: [Haskell] Найти все конечные подпоследовательности
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, deniok, Вы писали:
D>>Но и ты не сможешь опровергнуть утверждение, что этот алгоритм выдает только одноэлементные последовательности (не решая, тем самым, задачу). Утверждения о черных ящиках они такие
Q>Я не должен ничего опровергать. Я утверждаю, что мой алгоритм решает поставленную задачу.
А я утверждаю, что он решает другую, несовместимую задачу (выдача одноэлементных последовательностей).
Для проверки мы запускаем его и видим, что мое утверждение столь же обосновано, сколь твое
Вон Булат с разбега дал красивое и неправильное решение. А nikov-у пришлось прибегнуть к арифметике.
Перекуём баги на фичи!
