Понимание подробного списка в Haskell

Я использую Haskell, чтобы найти список целых чисел от 1 до 10000, которые имеют особое свойство. я делаю следующее

[ number | number <- [1..10000], (isSpecial number)]

Однако время от времени я придумывал некоторые специальные свойства, которые

  1. трудно быть удовлетворенным

  2. нужно долго проверять

В результате он зависает там после нескольких первых нескольких примеров.

Интересно, как я могу сделать понимание списка в Haskell подробным, поэтому у меня есть хорошее обновление о том, насколько продвинулся Haskell.


person Student    schedule 25.11.2019    source источник
comment
вы не можете сделать понимание списка подробным так, как вы предлагаете. Однако вы можете получить эту информацию совершенно по-другому, выполнив действие IO, которое перебирает все числа от 1 до 10000, сверяет каждое с isSpecial и распечатывает свой прогресс на терминале. Это то, о чем вы говорите?   -  person Robin Zigmond    schedule 26.11.2019
comment
Хм.. вы имеете в виду, что мне придется писать isSpecial_Verbose, который что-то говорит каждый раз, когда он вызывается?   -  person Student    schedule 26.11.2019
comment
isSpecial — это функция от Int до Bool. Как мне сделать так, чтобы его вывод был как Bool, так и IO()? @РобинЗигмонд   -  person Student    schedule 26.11.2019
comment
Интересно, выполняете ли вы задачи Project Euler. Там у вас обычно есть два варианта: во-первых, сгенерировать и отфильтровать — именно то, что вы показываете в сообщении; во-вторых, генерировать только числа, удовлетворяющие этому свойству. Второй подход сложнее, но работает намного лучше, чем первый.   -  person Artem Pelenitsyn    schedule 26.11.2019
comment
Нет, я имею в виду написать совершенно новое значение типа IO (), которое использует isSpecial (и прокручивать соответствующие числа)   -  person Robin Zigmond    schedule 26.11.2019
comment
@ArtemPelenitsyn некоторые задачи по математике настолько сложны, что никто не знает, как точно сгенерировать набор желаемых чисел.   -  person Student    schedule 26.11.2019
comment
@RobinZigmond Я до сих пор не совсем понимаю .. вы имеете в виду написать функцию verbosified :: (a->b) -> IO() и применить ее к isSpecial? Мой вопрос все еще там: мне нужна функция isSpecial, чтобы сообщить свои логические результаты. Как я могу сохранить это, делая его подробным?   -  person Student    schedule 26.11.2019
comment
хорошо, я могу показать вам, если хотите, просто не хотел писать ответ, не зная, было ли это то, что вы искали. Но я имею в виду, что вы можете сделать, например, tellMeResult :: Int -> IO (); tellMeResult n = putStrLn $ "Testing " ++ show n ++ " - it's " ++ (if isSpecial n then "special" else "not special"). Затем выполните это для всех чисел от 1 до 1000 (например, с mapM).   -  person Robin Zigmond    schedule 26.11.2019
comment
То, что я предлагаю, не особенно сложно, но оно даст вам приблизительное представление о том, сколько времени занимает расчет для каждого числа, и где вы находитесь.   -  person Robin Zigmond    schedule 26.11.2019
comment
Да, тогда я понял! Однако я спросил об этом, потому что мне все еще нужен список понимания. Обычно список понимания отличный.. но иногда система зависает, потому что есть один список, который занимает так много времени. Если бы я мог сделать весь список подробным, я мог бы определить, что больше всего съедает время, и исправить это более эффективно!   -  person Student    schedule 26.11.2019
comment
Вы можете использовать трассировку вывести текущее состояние на консоль во время его оценки   -  person Ed'ka    schedule 26.11.2019


Ответы (4)


Примерно это имел в виду Робин Зигмонд:

checkNumbers :: IO [Int]
checkNumbers = filterM check [1..10000]
    where
        check number = do
            print $ "Checking number" <> show number
            pure $ isSpecial number

Это напечатает «Проверка числа x» перед проверкой каждого числа. Не стесняйтесь экспериментировать с любыми другими эффектами (или, по-вашему, «многословием») внутри функции check.

person Fyodor Soikin    schedule 25.11.2019
comment
Я все еще понимаю этот код. Я не видел IO [Int] и не знаком с pure. Я вернусь к этому после изучения их .. - person Student; 26.11.2019
comment
@Student Я полагаю, вы видели return; если у вас есть, pure то же самое (это применимо к большему количеству типов, но пока не беспокойтесь об этом). Что касается IO [Int], IO — это конструктор типа, а IO a в основном означает, что это действие, которое выполняет некоторый ввод/вывод и возвращает значение типа a. a может быть любым, включая список, как здесь. - person Robin Zigmond; 26.11.2019

Вот способ, который не требует ввода-вывода, вместо этого полагаясь на лень, и ваш программист угадывает, какая «сторона» условия встречается чаще. Просто чтобы было с чем поиграть, вот немного медленная функция, которая проверяет, является ли число кратным 10. Детали этой функции не важны, не стесняйтесь пропустить ее, если что-то не имеет смысла. Я также собираюсь включить отчеты о времени; вы увидите, почему позже.

> isSpecial :: Int -> Bool; isSpecial n = last [1..10000000] `seq` (n `mod` 10 == 0)
> :set +s

(Добавляйте один 0 каждые пять лет.)

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

> :m + Data.List
> (matches, nonMatches) = partition isSpecial [1..20]
(0.00 secs, 0 bytes)
> nonMatches
[1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19]
(12.40 secs, 14,400,099,848 bytes)

Очевидно, я не могу отобразить это через StackOverflow, но когда я сделал вышеописанное, числа в списке nonMatches медленно появлялись на моем терминале одно за другим, давая довольно хороший индикатор того, где в списке он в данный момент думал. И теперь, когда вы печатаете matches, полный список доступен более или менее мгновенно, как вы можете видеть по отчету о времени (т.е. не через очередное 12-секундное ожидание):

> matches
[10,20]
(0.01 secs, 64,112 bytes)

Но будьте осторожны!

  1. Важно, чтобы matches и nonMatches имели типы, которые не являются полиморфными классами типов (т. е. не имеют типов, начинающихся с Num a => ... или какого-либо другого ограничения). В приведенном выше примере я добился этого, сделав isSpecial мономорфным, что вынуждает matches и nonMatches быть такими же, но если ваш isSpecial полиморфен, вы должны указать сигнатуру типа для matches или nonMatches, чтобы предотвратить эту проблему.

  2. Таким образом, все списки nonMatches и matches будут реализованы в памяти. Это может быть дорого, если первоначальный разделяемый список очень длинный. (Но до, скажем, пары сотен тысяч Ints для современных компьютеров не так уж и много.)

person Daniel Wagner    schedule 25.11.2019

Debug.Trace

Вы можете посмотреть на Debug.Trace. Он позволяет выводить сообщения на консоль. Но поскольку Haskell ленив, контролировать, когда происходит печать, не так просто. И это тоже не рекомендуется для производства:

Prelude Debug.Trace> import Debug.Trace
Prelude Debug.Trace> [x | x <- [1..10], traceShow (x, odd x) $ odd x]
(1,True)
[1(2,False)
(3,True)
,3(4,False)
(5,True)
,5(6,False)
(7,True)
,7(8,False)
(9,True)
,9(10,False)
]
person ziggystar    schedule 27.11.2019

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

Что я обычно делаю, так это разбиваю входной список на фрагменты из n элементов, фильтрую каждый фрагмент так же, как и весь список, и преобразовываю каждый фрагмент в пару его головного элемента и отфильтрованного фрагмента:

chunked_result = [ (h, [n | n <- chunk, isSpecial n])
                   | chunk@(h:_) <- chunksOf n input]

Помещение такого списка результатов через concatMap snd дает исходную не "подробную" опцию.

Настройка значения n повлияет на частоту, с которой будет "сообщаться" о прогрессе, когда список результатов будет просто распечатываться, показывая как проверенные, так и обнаруженные числа, с некоторым несущественным "шумом" вокруг них.

Использование second concat . unzip в списке результатов фрагментов чем-то похоже на идею разбиения Даниэля Вагнера (с оговорками),(*), но с вашим установленным значением n, а не просто 1.

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


(*), чтобы сделать его совместимым, нам нужно вставить где-нибудь seq посередине, например

chunked_result = [ (last s `seq` last chunk, s)
                   | chunk <- chunksOf n input
                     let s = [n | n <- chunk, isSpecial n] ]

или что-то.

person Will Ness    schedule 26.11.2019
comment
Это хорошо, но second concat . unzip не совсем вернет то, что делает мой ответ: ни один из вызовов isSpecial не будет принудительно напечатан fst частью результата, поэтому fst часть на самом деле не дает хорошего индикатора того, насколько был достигнут прогресс. Ничего страшного — это просто другая вещь, и нет необходимости точно воспроизводить то, что я с ней сделал. Но я бы рекомендовал просто отказаться от этой части ответа, чтобы не запутаться. - person Daniel Wagner; 27.11.2019
comment
Я отредактировал эту часть. конечно, повторение вашей идеи не было целью того, что я написал, этот трюк с фрагментацией - это то, что я часто делаю сам, возможно, с некоторой последовательностью посередине (как вы указываете - скоро это отредактируется). В основном я просто печатаю результаты как есть, так что все принудительно. Я даже изначально написал, что я часто делаю в таких ситуациях... но потом отредактировал для нейтральности. мне просто пришло в голову, что это одно и то же, поэтому я упомянул об этом. - person Will Ness; 27.11.2019