Возможно ли реализовать эту функцию слова без шага постобработки после свертывания? - PullRequest
Новая
       63

Возможно ли реализовать эту функцию слова без шага постобработки после свертывания?

14 голосов
/ 29 апреля 2020

Реальный мир Haskell, глава 4, стр. 98 печати спрашивает, можно ли реализовать words, используя сгибы, и это тоже мой вопрос:

Является ли это возможным? Если нет, то почему? Если да, то как?

Я придумал следующее, основанное на идее, что каждый непробел должен быть добавлен перед последним словом в списке вывода (это происходит в otherwise guard), и пробел должен инициировать добавление слова emtpy в список вывода, если его еще нет (это обрабатывается в if - then - else). 

myWords :: String -> [String]
myWords = foldr step [[]]
  where
    step x yss@(y:ys)
      | x == ' ' = if y == "" then yss else "":yss
      | otherwise = (x:y):ys

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

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

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

Во всех этих подходах foldr (или другой фолд, fwiw) не является функцией, которая обеспечивает окончательный вывод из коробки; всегда есть что-то, с чем нужно как-то настроить вывод.

Поэтому я go возвращаюсь к первоначальному вопросу и спрашиваю, возможно ли на самом деле реализовать words (таким образом, чтобы он правильно обрабатывал трейлинг / ведущие / повторные пробелы) с использованием складок. Под с использованием сгибов я имею в виду, что функция сгибания должна быть самой внешней функцией: 

myWords :: String -> [String]
myWords input = foldr step seed input

Ответы [ 3 ]

13 голосов
/ 29 апреля 2020

Если я правильно понимаю, ваши требования включают 

(1) words "a b c" == words " a b c" == ["a", "b", "c"]
(2) words "xa b c" == ["xa", "b", "c"] /= ["x", "a", "b", "c"] == words "x a b c"

Это означает, что у нас не может быть 

words = foldr step base

для любых step и base.

Действительно, если бы у нас было это, тогда 

words "xa b c"
= def words and foldr
step 'x' (words "a b c")
= (1)
step 'x' (words " a b c")
= def words and foldr
words "x a b c"

, и это противоречит (2).

Вам определенно понадобится некоторая пост-обработка после foldr.

5 голосов
/ 29 апреля 2020
У

@ chi есть замечательный аргумент, что вы не можете реализовать words, используя сгиб «а», но вы сказали , используя сгиб s . 

words = filterNull . words1
    where
    filterNull = foldr (\xs -> if null xs then id else (xs:)) []
    words1 = foldr (\c -> if c == ' ' then ([]:) else consHead c) []
    consHead c []       = [[c]]
    consHead c (xs:xss) = (c:xs):xss

И самая внешняя и самая внутренняя функция - сгибы. ; -)

1 голос
/ 30 апреля 2020

Да. Даже если это немного сложно, вы все равно можете правильно выполнять эту работу, используя один foldr и ничего больше, если вы погружаетесь в CPS ( Continuation Passing Style ). Ранее я показывал специальный вид функции chunksOf.

В таких типах сгибов наш аккумулятор, следовательно, результат сгиба является функцией, и мы должны применить ее к тождественный вид ввода, так что у нас есть конечный результат. Так что это может считаться конечной стадией обработки или нет, так как мы используем здесь единственную складку, и тип ее включает функцию. Открыто для обсуждения:) 

ws :: String -> [String]
ws str = foldr go sf str $ ""
         where
         sf :: String -> [String]
         sf s = if s == " " then [""] else [s]
         go :: Char -> (String -> [String]) -> (String -> [String])
         go c f = \pc -> let (s:ss) = f [c]
                         in case pc of
                            ""        -> dropWhile (== "") (s:ss)
                            otherwise -> case (pc == " ", s == "") of
                                         (True, False)  -> "":s:ss
                                         (True, True)   -> s:ss
                                         otherwise      -> (pc++s):ss

λ> ws "   a  b    c   "
["a","b","c"]

sf: начальное значение функции для начала.

go: функция итератора

На самом деле мы не полностью используя силу CPS здесь, так как у нас есть и предыдущий символ pc и правильный символ c под рукой на каждом ходу. Это было очень полезно в функции chunksOf, упомянутой выше, при разбиении [Int] на [[Int]] каждый раз, когда была нарушена восходящая последовательность элементов.

...