Построение экспоненциального размера списка в haskell

Question

У меня есть две функции, которые делают что-то, только если C - это определенный шаблон.Каждая функция выводит список из C.

Моя цель состоит в том, чтобы, учитывая [C], я хотел получить все возможности вызова f1 и f2 в списке, оставляя остальные без изменений.Например:

предположим, что список C:

    c1
    c2 --matches the pattern
    c3

, тогда я хочу получить список из двух списков

[[c1] ++ (f1 c2) ++ [c3],[c1] ++ (f2 c2) ++ [c3]]

Однако, если у меня есть

c1
c2 --matches the pattern
c3 --matches the pattern

Тогда у нас должно быть 4 списка, потому что мы хотим, чтобы все комбинации вызывали f1 и f2.Таким образом, это будет:

[(f1 c1) ++ (f1 c2) ++ [c3], (f2 c1) ++ (f2 c2) ++ [c3], 
(f1 c1) ++ (f2 c2) ++ [c3], (f2 c1) ++ (f1 c2) ++ [c3]]

В настоящее время мой код структурирован примерно следующим образом:

f1 :: C -> [C]

f2 :: C ->  [C]

combine ::  [C] -> [[C]]
combine  my_pattern:xs =  ?
combine (x:xs) =  ?
combine [] = []

  where first_set = (f1 my_pattern)
        second_set = (f2 my_pattern)

Может ли кто-нибудь дать интуитивное представление о том, как я мог бы заполнить оставшуюся часть?Есть ли какие-либо функции из Data.List, которые могут быть полезны?Я посмотрел на документацию, но не смог сразу заметить, какой из них может быть полезным.

Answer 1

Другие ответы кажутся мне очень сложными.В этом ответе я расширю свой комментарий: это просто foldMap, сочетающий монаду недетерминизма (списки!) С моноидом последовательности (списки!).

Сначала напишите вещь, которая работает на одном элементеиз списка:

singleElement x
    | matchesThePattern x = [f1 x, f2 x]
    | otherwise = [[x]]

Затем примените его к каждому элементу:

import Data.Monoid
combine = foldMap (Ap . singleElement)

Вот и все.Вот и весь код.

Например, предположим, что мы хотим повторить каждую букву 2 или 3 раза, то есть x -> xx или xxx, а все остальные символы останутся прежними.

singleElement x
    | 'a' <= x && x <= 'z' = [[x, x], [x, x, x]]
    | otherwise = [[x]]

Тогда мы можем попробовать это в ghci:

> combine "123def"
Ap {getAp = ["123ddeeff","123ddeefff","123ddeeeff","123ddeeefff","123dddeeff","123dddeefff","123dddeeeff","123dddeeefff"]}

Выберите имя, отличное от singleElement в вашем собственном коде, конечно.

Answer 2

Вы должны как-то определить

applicable_f1 :: C -> Bool
applicable_f2 :: C -> Bool

.Тогда

combinations :: [C] -> [[C]]
combinations cs = map concat . sequence $
    [ concat $ [ [ [c]   | not (applicable_f1 c || applicable_f2 c)]
               , [ f1 c  | applicable_f1 c]
               , [ f2 c  | applicable_f2 c] ]
      | c <- cs]

Answer 3

Мой подход заключается в

1. Решить проблему для элемента в списке, на который вы в данный момент смотрите (x или my_pattern).Это означает создание одного или нескольких новых списков.
2. Решите проблему для остальной части списка (xs).Это вернет вам список списков ([[C]]).
3. Объедините два решения.Если у вас есть несколько списков, созданных на шаге 1, каждый из этих списков ([C]) объединится с каждым списком (также [C]) в списке списков ([[C]]) с шага 2.

У меня есть два возможных подхода.

Мне не ясно, какую помощь вы ищете, поэтому я оставил свои ответы несколько «свободными от спойлеров».Если вам это нужно, попросите разъяснений или дополнительных подробностей.

Понимание списка

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

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

[ x ++ y | x <- _, y <- _] :: [[C]]
-- this means
-- x :: [C]
-- y :: [C]
-- _ :: [[C]]

Это понимание списка создает список списков.x - это то, что предваряется, поэтому было бы целесообразно, чтобы оно исходило от применения функций f1 и f2.y - это конец каждого результирующего списка.Я оставлю вас, чтобы выяснить, что это может быть.

Несоответствующий случай проще, чем этот, и может быть записан как

[ x : y | y <- _] :: [[C]]
-- note that x is not local to the list comprehension
-- y :: [C]
-- _ :: [[C]]

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

Аппликативный

Еще один способ решения этой проблемы - использование Applicative экземпляра [a].

Давайте рассмотрим функцию (<*>) в списке Applicative instance.

-- this is the type when specialized to lists
(<*>) :: [a -> b] -> [a] -> [b]

Эта функция имеет своего рода странную сигнатуру типа.Он принимает список функций и список, а затем возвращает вам другой список.Он имеет эффект применения каждой функции a -> b к каждому элементу [a] по порядку.

>>> [(+1), (+2)] <*> [1,2,3]
-- [2,3,4] comes from (+1)
-- [3,4,5] comes from (+2)
[2,3,4,3,4,5]

Мы хотим получить [[C]], а не [C], поэтому, если мы хотим использовать(<*>) мы можем специализировать его тип больше на

(<*>) :: [a -> [C]] -> [a] -> [[C]]

Чтобы избежать путаницы, я рекомендую выбрать a = [C], что дает

(<*>) :: [[C] -> [C]] -> [[C]] -> [[C]]

Ваш список функций должен предшествовать правильномуэлементы на списки, которые вы генерируете.Вторым аргументом должны быть списки, возвращаемые рекурсивным вызовом.