Получение всех подстрок длиной 4 из бесконечного списка

Question

Я довольно новичок в Haskell и пытаюсь решить следующую проблему:

У меня есть функция, которая создает бесконечный список строк разной длины. Но количество строк определенной длины ограничено.

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

Я знаю, что filter() не будет работать, так как он проверяет каждую часть списков и приводит к бесконечному количествуloop.

Это моя функция, которая генерирует бесконечный список:

allStrings =  [ c : s | s <- "" : allStrings, c <- ['R', 'T', 'P']]

Я уже пробовал это:

allStrings = [x | x <- [ c : s | s <- "" : allStrings, 
                  c <- ['R', 'T', 'P']], length x == 4] 

, который не завершился.

Спасибо за помощь!

Answer 1

Это

allStrings4 = takeWhile ((== 4) . length) . 
                dropWhile ((< 4) . length) $ allStrings

делает свое дело.

Это работает, потому что ваше (первое) определение allStrings ловко генерирует все строки, содержащие 'R', 'T' и 'P' буквы продуктивно в порядке неубывающая длина порядок.

Вместо того, чтобы пытаться втиснуть все в одно определение, разделите ваши проблемы! Сначала создайте решение более общей проблемы (это ваше allStrings определение), затем используйте , чтобы решить более ограниченную проблему. Это часто будет намного проще, особенно с ленивой оценкой Haskell.

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

Answer 2

Проблема в том, что ваш фильтр делает невозможным создание каких-либо решений. Чтобы сгенерировать строку длиной 4, сначала необходимо сгенерировать строку длиной 3, поскольку каждый раз перед ней добавляется один символ. Чтобы сгенерировать список длиной 3, он должен будет генерировать строки длиной 2 и т. Д. До базового случая: пустой строки.

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

Мы можем исправить это, используя другой список, который будет создавать строки, и фильтровать этот список следующим образом:

allStrings = filter ((==) 4 . length) vals
    where vals = [x | x <- [ c : s | s <- "" : vals, c <- "RTP"]]

Это создаст все списки длиной 4, а затем застрянет в бесконечном цикле, поскольку filter будет продолжать поиск других строк и не сможет их найти.

Однако мы можем добиться большего успеха, например, используя replicateM :: Monad m => Int -> m a -> m [a] здесь:

Prelude Control.Monad> replicateM 4 "RTP"
["RRRR","RRRT","RRRP","RRTR","RRTT","RRTP","RRPR","RRPT","RRPP","RTRR","RTRT","RTRP","RTTR","RTTT","RTTP","RTPR","RTPT","RTPP","RPRR","RPRT","RPRP","RPTR","RPTT","RPTP","RPPR","RPPT","RPPP","TRRR","TRRT","TRRP","TRTR","TRTT","TRTP","TRPR","TRPT","TRPP","TTRR","TTRT","TTRP","TTTR","TTTT","TTTP","TTPR","TTPT","TTPP","TPRR","TPRT","TPRP","TPTR","TPTT","TPTP","TPPR","TPPT","TPPP","PRRR","PRRT","PRRP","PRTR","PRTT","PRTP","PRPR","PRPT","PRPP","PTRR","PTRT","PTRP","PTTR","PTTT","PTTP","PTPR","PTPT","PTPP","PPRR","PPRT","PPRP","PPTR","PPTT","PPTP","PPPR","PPPT","PPPP"]

Обратите внимание, что здесь сначала используется символ last меняется, когда мы генерируем следующую строку. Я оставляю это как упражнение для получения обратного результата.