Убедитесь, что все символы в строке совпадают

Было интересно, можете ли вы мне помочь, я пишу программу haskell, и я использую метод транспонирования, и он работает так, как я хочу. Но затем я хочу проверить, что каждая [строка], возвращаемая при транспонировании, имеет один и тот же символ, например

transpose["hello","help","hell","helm"]

вернет что-то вроде

["hhhh","eeee","llll","plml","o"]

Интересно, можно ли в таком случае пройти все вышеперечисленное и остановиться, когда строка не состоит из всех одинаковых символов, например, остановившись на "plml"


debugging algorithm haskell
person K.Madden    schedule 10.12.2019    source источник
comment
Похоже, вам следует использовать takeWhile. Я оставлю вас, чтобы придумать подходящую функцию предиката (которую вы могли бы, например, написать с помощью довольно простой прямой рекурсии).   -  person Robin Zigmond    schedule 10.12.2019
comment
Может ли это быть использовано для получения самого длинного общего префикса?   -  person K.Madden    schedule 10.12.2019
comment
Что-то вроде автодополнения: вы начинаете входить в мир, и у вас есть список слов, начинающийся с одинаковых букв?   -  person Andrelec1    schedule 10.12.2019
comment
Это самая длинная распространенная проблема с префиксом, которую я пытаюсь решить   -  person K.Madden    schedule 10.12.2019
comment
Попробуйте takeWhile ((==1) . length . nub). Извините за краткий комментарий, я на лекции;)   -  person MikaelF    schedule 10.12.2019
comment
@MikaelF nub излишне дорого стоит, если все, что вам нужно знать, это то, что есть ровно один элемент. Вместо этого вы можете использовать all, чтобы проверить, равен ли каждый элемент списка первому элементу списка.   -  person amalloy    schedule 10.12.2019
comment
@amalloy, так как ты хочешь это сделать? Все еще пользуетесь дублем   -  person K.Madden    schedule 10.12.2019
comment
По теме: Проверьте, все ли элементы складного объекта одинаковы   -  person Joseph Sible-Reinstate Monica    schedule 10.12.2019

Ответы (1)


arrow_upward
4
arrow_downward

Один из способов сделать это - применить group к каждой строке:

> group "hhhh"
["hhhh"]
> group "plml"
["p","l","m","l"]

Затем, если вы takeWhile число групп равно 1, вы получите все однородные строки:

> test = ["hello","help","hell","helm"]
> import Data.List
> takeWhile ((==1) . length) . map group . transpose $ test
[["hhhh"],["eeee"],["llll"]]

Вы можете избавиться от лишнего слоя списка с помощью map head.

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

single :: [a] -> Bool
single [a] = True
single _ = False

и используйте:

> map head . takeWhile single . map group . transpose $ test
["hhhh","eeee","llll"]]

Основное отличие состоит в том, что (==1) . length необходимо оценить и подсчитать длину всего набора групп, но single может остановиться раньше. Например, на бесконечной строке:

> ((==1) . length) $ group $ "aaa" ++ repeat 'b'  -- hangs forever
> single $ group $ "aaa" ++ repeat 'b'  -- returns `False` at first 'b'

Альтернативой, предложенной в комментариях, была бы более прямая проверка того, что первый символ равен всем остальным символам:

allSame :: (Eq a) => [a] -> Bool
allSame (x:rest) = all (==x) rest

и:

> takeWhile allSame . transpose $ test
["hhhh","eeee","llll"]

СПОЙЛЕРЫ: Согласно вашим комментариям, вы пытаетесь найти самый длинный префикс, поэтому в завершение обратите внимание, что вы хотите map head по:

["hhhh","eeee","llll"]

получить:

['h','e','l']

что то же самое, что:

"hel"

Поскольку map head, за которым следует map head, можно записать map head . map head или даже короче map (head . head), окончательное определение с использованием group может быть записано:

prefix :: (Eq a) => [[a]] -> [a]
prefix = map (head . head) . takeWhile single . map group . transpose
   where single [a] = True
         single _ = False

и окончательное определение с использованием allSame можно записать:

prefix :: (Eq a) => [[a]] -> [a]
prefix = map head . takeWhile allSame . transpose
   where allSame (x:rest) = all (==x) rest
person K. A. Buhr    schedule 10.12.2019
comment
Удивительный! Спасибо огромное. Если вы не возражаете, не могли бы вы дать краткую разбивку строки prefix = map (head. Head). takeWhile холост. группа карт. транспонировать 'как в том, как это работает со строкой - person K.Madden; 15.12.2019