在折叠后不进行后处理步骤，是否可以实现这个单词功能？

Question

现实世界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

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

对于任何 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.

Answer 2

@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

最外侧和最内侧的功能都是褶皱。 ;-)

Answer 3

是的。尽管这有点棘手，但你仍然可以通过使用单一的 foldr 如果你纠结于CPS(延续传球方式). 我曾表现出一种特殊的 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]] 每当一个元素的升序被打破时。