Строковый токенизатор

Цель:

  • Создайте функцию с именем wordsAndSpaces который разбивает строку на группы пробелов, сохраняя каждую группу пробелов как один токен.
    Пример: wordsAndSpaces "extra spaces" дает ["extra", " ", "spaces"]

Правила:

  • Входные строки будут содержать только буквенно-цифровые символы и пробелы (специальные символы обрабатывать не нужно).
  • Разрешены только функции Prelude (без импорта, например Data.List.Split)

Примечания:

  • Я специально ищу отзывы о том, как я могу сломать шаблоны мышления, которые я выработал при работе с императивными языками. В моем коде наверняка есть явные признаки выздоравливающего Java-программиста 🙂
wordsAndSpaces :: String -> [String]
wordsAndSpaces = wordsAndSpaces' []

wordsAndSpaces' :: [String] -> String -> [String]
wordsAndSpaces' tokens [] = tokens
wordsAndSpaces' tokens (char : xs)
  | shouldAddToLastToken char tokens = wordsAndSpaces' (addToLastToken char tokens) xs
  | otherwise = wordsAndSpaces' (tokens ++ [[char]]) xs

shouldAddToLastToken :: Char -> [String] -> Bool
shouldAddToLastToken c tokens
  | null tokens = False
  | otherwise =
    (isSpace c && (isSpace . last . last) tokens)
      || ((not . isSpace) c && (not . isSpace . last . last) tokens)

addToLastToken :: Char -> [String] -> [String]
addToLastToken char tokens = init tokens ++ [last tokens ++ [char]]

isSpace :: Char -> Bool
isSpace = (== ' ')

1 ответ
1

Меня поразило, как вы относитесь к спискам Haskell, как к Java … Массивам? (Я не использовал Java с … 2006 г.?) Если вы постоянно возитесь с элементами в конце списков, вероятно, вы делаете что-то не так. Я не уверен, в чем сложность всего этого, но я думаю, что это может быть что-то вроде $ mathcal {O} (м ^ 2n ^ 2) $ куда $ m $ — длина исходной строки и $ n $ количество жетонов. Списки Haskell — это связанные списки, в которых можно найти произвольные элементы (из которых last один) является $ mathcal {O} (n) $ операция, как добавление любого элемента в конец списка (++).

Я думаю, что по мере того, как вы познакомитесь с Prelude, вы начнете интуитивно понимать форму эффективных алгоритмов Haskell. Это не значит, что в Haskell также нет массивов, но мы склонны использовать их по-другому. (Как именно это выходит за рамки этого вопроса.)

В этом случае концепция, которую вы ищете, — это span. То есть первая часть списка, соответствующая предикату, а затем остальная часть. В этом случае мы заботимся о предикатах isSpace и not . isSpace.

-- REPL session, if you're not familiar with REPLs yet coming from Java, check out GHCi
> span isSpace "   word word"
("   ","word word")
> span (not . isSpace) "wordword    word word"
("wordword","    word word")

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


Вот решение с использованием span. Spoiler’d, так что вы можете сначала разобраться.

wordsAndSpaces :: String -> [String]
wordsAndSpaces [] = []
wordsAndSpaces cs@(c:_) = case isSpace c of
    True  -> let (w, rest) = span isSpace cs  in w : wordsAndSpaces rest
    False -> let (w, rest) = break isSpace cs in w : wordsAndSpaces rest
                          -- break p = span (not . p), just a convenient name

В этом решении вы могли заметить, что оба зубца вилки (как бы) очень и очень похожи. Как правило, это намек на то, что существует удобная библиотечная функция или есть какой-то распространенный трюк, который имеет глубоко неинтуитивное теоретическое название категории и / или требует вспышки абстрактно аргументированного понимания для распознавания. К счастью, в этом случае вам просто нужно знать о Data.List.groupBy :: (a -> a -> Bool) -> [a] -> [[a]].

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


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

> groupBy (==) [1,1,2,2,2,3,4,5,5,5,5]
[[1,1],[2,2,2],[3],[4],[5,5,5,5]]

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
isSpace :: (a      -> Bool)

Итак, вопрос в том, как превратить унарный предикат isSpace в бинарный предикат для перехода к groupBy? Первый шаг к осознанию того, что Bool возвращаемые значения означают разные вещи. isSpace говорит, является ли персонаж пробелом, groupByпредикат спрашивает, являются ли две вещи одинаковый. Таким образом, мы можем проверить результат isSpace на двух элементах на равенство.

predicate :: Char -> Char -> Bool
predicate c d = isSpace c == isSpace d

Но оказывается, что мы даже делаем который так часто, что для него тоже есть название, Data.Function.on :: (b -> b -> c) -> (a -> b) -> a -> a -> c. Используется как —

predicate = (==) `on` isSpace

on выполняет бинарную операцию (b -> b -> c) и унарная операция (a -> b) и лифты биноп для работы as, какими бы они ни были. groupBy — хороший пример, сортировки — еще один, где вы можете сделать что-то вроде compare `on` color, если color имел тип как Shape -> Color. Мы хотели бы отсортировать Shapes пользователем Color, поэтому вы используете функцию более высокого порядка (on), чтобы создать для этого функцию! Попробуй реализовать on.


Итак, вот как напишет Хаскеллер wordsAndSpaces.

wordsAndSpaces = groupBy ((==) `on` isSpace)

Имея этот (вероятно, шокирующий) пример мотивации, попробуйте написать groupBy. Вернитесь к решению, используя span, рассмотрите его симметрию и попытайтесь подняться на один уровень вверх по стеку абстракции. В конечном итоге кодирование на Haskell — это решение самой маленькой части проблемы, которую вы можете, распознавание того, какая функция более высокого порядка может направить ее на решение чуть более крупной проблемы, а затем повторение этого процесса снова и снова, пока не дойдете до конца.

В этом случае (хотя я как бы извилистый) сначала нам нужно было выяснить, как определить, является ли что-то пробелом. Затем вы выясняете, как определить один отрезок пробелов или непробелов. Тогда трюк состоит в категоризации все пробелов «может быть или нет». Каждый шаг на пути — это что-то маленькое и выполнимое само по себе, и мы стараемся рассмотреть наиболее общее возможное решение, чтобы мы не обязательно подумайте сразу обо всей проблеме.

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *