实现单词函数是否可以在折叠后不需要后处理步骤？

Question

Real World Haskell, chapter 4, page 98 of the printed version问能否使用折叠实现words函数，这也是我的问题：

是否可能？如果不能，为什么？如果可以，如何实现？

我想到了以下实现方法，其基本思路是将每个非空格字符前置到输出列表中的最后一个单词上（在otherwise语句块中完成），如果没有空单词则使用空格触发将空单词添加到输出列表中（在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（或另一个折叠函数）不是直接提供最终输出的函数；总是有其他东西必须以某种方式调整输出。

因此，我回到最初的问题，并问是否实际上可以使用折叠来实现words（以正确处理尾随/前导/重复空格的方式）。通过使用折叠，我的意思是折叠函数必须是最外层的函数：

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

- Enlico

Answer 1

如果我理解正确，您的要求包括：

(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

对于任何步骤和基础。确实，如果我们有这个，那么

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

---

甚至["xa"] == words "xa" == step 'x' (words "a") == step 'x' (words " a") == words "x a" == ["x", "a"]，这样做的好处是可以作为fold函数的任何方向的有效参数。 - Cireo

Answer 2

@chi提出了一个很精彩的观点，即你无法使用"a" fold实现words，但你确实说过“使用folds”。

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

最外层和最内层的函数都是 folds。;-)

- luqui

---

我想你知道我的意思，但因为挑剔而+1 :P - Enlico

Answer 3

是的。虽然略微棘手，但您仍可以通过使用单个foldr并且仅此而已，如果您深入研究CPS（Continuation Passing Style），就可以正确地完成此工作。我之前展示了一种特殊类型的chunksOf函数。

在这种折叠中，我们的累加器（因此折叠的结果）是一个函数，并且我们必须将其应用于某种身份输入，以便获得最终结果。因此，这可能算作最终处理阶段或不算，因为我们在此处使用单个fold，它的类型包含函数。开放讨论 :)

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。在上面提到的将 [Int] 划分为 [[Int]] 时，当元素的升序序列被中断时，它非常有用。

- Redu