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

Real World Haskell, глава 4, стр. 98 печати спрашивает, wordsможно ли реализовать с помощью сгибов, и это тоже мой вопрос:

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

Я придумал следующее, которое основано на идее, что каждый непробел должен быть добавлен перед последним словом в списке вывода (это происходит в otherwiseохране), и что пробел должен инициировать добавление слова 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) не есть функция, которая обеспечивает окончательный вывод из коробки; всегда есть что-то, с чем нужно как-то настроить выход.

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

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

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

(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.

У @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

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

Да. Даже если это немного сложно, вы все равно можете делать эту работу правильно, используя один 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]]каждый раз, когда восходящая последовательность элементов была нарушена.