Haskell - исключить списки на основе теста в понимании вложенного списка

Question

Я хочу создать серию возможных уравнений на основе общей спецификации:

test = ["12", "34=", "56=", "78"]

Каждая строка (например, «12») представляет возможный символ в этом месте, в данном случае «1» или «2».) Таким образом, возможные уравнения из теста будут «13 = 7» или «1 = 68». Я знаю, что примеры, которые я привожу, не сбалансированы, но это потому, что я специально даю упрощенную короткую строку (Я также знаю, что могу использовать «последовательность» для поиска всех возможностей, но я хочу быть более умным, поэтому мне нужен другой подход, описанный ниже.)

То, что я хочу, это попытаться исправить каждое из равных по очереди, а затем удалить все остальные равные в уравнении. Итак, я хочу:

[["12","=","56","78"],["12","34","=","78”]]

Я написал это понимание вложенного списка: (для этого необходимо: {- # ЯЗЫК ParallelListComp # -})

fixEquals :: [String] -> [[String]]
fixEquals re
  = [
      [
        if index == outerIndex then equals else remain 
        | equals <- map (filter (== '=')) re
        | remain <- map (filter (/= '=')) re
        | index <- [1..]
      ]

      | outerIndex <- [1..length re]
    ]

Это производит:

[["","34","56","78"],["12","=","56","78"],["12","34","=","78"],["12","34","56","”]]

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

Я могу сделать:

countOfEmpty :: (Eq a) => [[a]] -> Int 
countOfEmpty = length . filter (== [])

fixEqualsFiltered :: [String] -> [[String]]
fixEqualsFiltered re = filter (\x -> countOfEmpty x == 0) (fixEquals re)

так что «fixEqualsFiltered test» дает:

[["12","=","56","78"],["12","34","=","78”]]

это то, что я хочу, но это не выглядит элегантно. Я не могу не думать, что есть другой способ отфильтровать их. В конце концов, всякий раз, когда в операторе if используется выражение «равно» и оно пустое, мы хотим отбросить «равно», поэтому составление списка кажется пустой тратой (например, [«», «34», «56», «78»). ] и затем бросьте его.)

Любые мысли приветствуются.

Answer 1

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

fixEquals = init . f
f :: [String] -> [[String]]
f [] = [[]]
f (x:xs) | '=' `elem` x = ("=":removeEq xs) : map (removeEq [x] ++) (f xs)
         | otherwise    = map (x:) (f xs)

removeEq :: [String] -> [String]
removeEq = map (filter (/= '='))

То, как это работает, заключается в том, что еслив текущей строке есть '=', затем она разбивает возвращаемый результат на два, если не просто вызывает рекурсивно.init необходим, так как в последнем возвращенном элементе нет равных ни в одной строке.

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

Answer 2

Let

xs = [["","34","56","78"],["12","=","56","78"],["12","34","=","78"],["12","34","56",""]]

in

filter (not . any null) xs

даст

[["12","=","56","78"],["12","34","=","78"]]

Если вы хотите понять список, выполните

[x | x <- xs, and [not $ null y | y <- x]]

Answer 3

Думаю, я бы так и сделал. Во-первых, предварительный текст, который я написал так много раз, уже практически сгорел в моих пальцах:

zippers :: [a] -> [([a], a, [a])]
zippers = go [] where
    go _ [] = []
    go b (h:e) = (b,h,e):go (h:b) e

Вероятно, запуск его один или два раза в ghci будет более четким объяснением того, что это делает, чем любое английское письмо, которое я мог бы сделать:

> zippers "abcd"
[("",'a',"bcd"),("a",'b',"cd"),("ba",'c',"d"),("cba",'d',"")]

Другими словами, он дает возможность выбирать каждый элемент списка по очереди, давая «остатки» того, что было до и после точки выбора. Учитывая этот инструмент, вот наш план: мы недетерминированно выберем String, который будет служить нашим знаком равенства, перепроверим, что мы получили знак равенства в первую очередь, а затем уберем равенство от других. Итак:

fixEquals ss = do
    (prefix, s, suffix) <- zippers ss
    guard ('=' `elem` s)
    return (reverse (deleteEquals prefix) ++ ["="] ++ deleteEquals suffix)

deleteEquals = map (filter ('='/=))

Давайте попробуем это:

> fixEquals ["12", "34=", "56=", "78"]
[["12","=","56","78"],["12","34","=","78"]]

Отлично! Но это всего лишь трамплин для фактического создания уравнений, верно? Оказывается, не так сложно пройти весь путь за один шаг, пропустив этот промежуточный пункт. Давайте сделаем это:

equations ss = do
    (prefixes, s, suffixes) <- zippers ss
    guard ('=' `elem` s)
    prefix <- mapM (filter ('='/=)) (reverse prefixes)
    suffix <- mapM (filter ('='/=)) suffixes
    return (prefix ++ "=" ++ suffix)

И мы можем попробовать это в ghci:

> equations ["12", "34=", "56=", "78"]
["1=57","1=58","1=67","1=68","2=57","2=58","2=67","2=68","13=7","13=8","14=7","14=8","23=7","23=8","24=7","24=8"]

Answer 4

Самый простой способ добиться желаемого - создать все комбинации и отфильтровать те, которые имеют значение:

Prelude> test = ["12", "34=", "56=", "78"]
Prelude> sequence test
["1357","1358","1367","1368","13=7","13=8","1457","1458","1467","1468","14=7","14=8","1=57","1=58","1=67","1=68","1==7","1==8","2357","2358","2367","2368","23=7","23=8","2457","2458","2467","2468","24=7","24=8"
Prelude> filter ((1==).length.filter('='==)) $ sequence test
["13=7","13=8","14=7","14=8","1=57","1=58","1=67","1=68","23=7","23=8","24=7","24=8","2=57","2=58","2=67","2=68"]

Вы указали на недостаток: представьте, у нас есть следующий список строк: ["=", "=", "0123456789", "0123456789"]. Мы создадим 100 комбинаций и отбросим их все.

Вы можете смотреть на комбинации в виде дерева. Для ["12", "34"] у вас есть:

  /  \
 1    2
/ \  / \
3 4  3 4

Вы можете обрезать дерево: просто игнорируйте поддеревья, когда у вас есть два = на пути. Давайте попробуем это сделать. Во-первых, простая combinations функция:

Prelude> :set +m
Prelude> let combinations :: [String] -> [String]
Prelude|     combinations [] = [""]
Prelude|     combinations (cs:ts) = [c:t | c<-cs, t<-combinations ts]
Prelude|
Prelude> combinations test
["1357","1358","1367","1368","13=7","13=8","1457","1458","1467","1468","14=7","14=8","1=57","1=58","1=67","1=68","1==7","1==8","2357","2358","2367","2368","23=7","23=8","2457","2458","2467","2468","24=7","24=8", ...]

Во-вторых, нам нужна переменная для хранения текущего числа = встреченных знаков:

• если мы найдем второй знак =, просто отбросим поддерево
• если мы достигнем конца комбинации без =, отбросим комбинацию

То есть:

Prelude> let combinations' :: [String] -> Int -> [String]
Prelude|     combinations' [] n= if n==1 then [""] else []
Prelude|     combinations' (cs:ts) n = [c:t | c<-cs, let p = n+(fromEnum $ c=='='), p <= 1, t<-combinations' ts p]
Prelude|
Prelude> combinations' test 0
["13=7","13=8","14=7","14=8","1=57","1=58","1=67","1=68","23=7","23=8","24=7","24=8","2=57","2=58","2=67","2=68"]

• Мы используем p в качестве нового номера знака = на пути: если p>1, отбросить поддерево.
• Если n равен нулю, у нас нет знака = на пути, отбросьте комбинацию.

Вы можете использовать переменную n для хранения дополнительной информации, например, типа последнего символа (чтобы избежать +* последовательностей).