折叠后无需后处理步骤，是否可以实现文字功能? [英] Is implementing the words function possible without a postprocessing step after folding?

问题描述

《真实世界》 Haskell，印刷品第98页第4章询问是否 words 可以使用折叠来实现，这也是我的问题:

Real World Haskell, chapter 4, page 98 of the print asks if words can be implemented using folds, and this is my question too:

有可能吗?如果没有，为什么?如果是，怎么办?

我提出了以下内容，其依据是每个非空格都应该放在输出列表的最后一个单词的前面(这发生在否则防护中)，并且如果还没有空格，则空格应触发将空词附加到输出列表(这在 if - then - else 中进行处理).

I came up with the following, which is based on the idea that each non-space should be prepended to the last word in the output list (this happens in the otherwise guard), and that a space should trigger the appending of an emtpy word to the output list if there is not one already (this is handled in the 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

显然，此解决方案是错误的，因为输入字符串中的前导空格会导致输出字符串列表中的一个前导空字符串.

Clearly this solution is wrong, since leading spaces in the input string result in one leading empty string in the output list of strings.

在上面的链接中，我研究了为其他读者准备的几种解决方案，其中许多解决方案与我的解决方案相似，但是它们通常对折页的输出进行后处理"，例如通过<如果前导字符串为空，则 tail .

At the link above, I've looked into several of the proposed solutions for other readers, and many of them work similarly to my solution, but they generally "post-process" the output of the fold, for instance by tailing it if there is an empty leading string.

其他方法使用元组(实际上只是成对的)，以便折叠处理成对的并能很好地处理前导/尾随空格.

Other approaches use tuples (actually just pairs), so that the fold deals with the pair and can well handle the leading/trailing spaces.

在所有这些方法中， folder (或另一种折叠方式，fwiw)都不是开箱即用地提供最终输出的功能.总是有其他东西必须以某种方式调整输出.

In all these approaches, foldr (or another fold, fwiw) is not the function that provides the final output out of the box; there's always something else with has to adjust the output somehow.

因此，我回到最初的问题，询问是否实际上可以使用折叠实现 words (以正确处理尾部/前导/重复空格的方式).使用折叠的意思是折叠功能必须是最外层的功能:

Therefore I go back to the initial question and ask if it is actually possible to implement words (in a way that it correctly handles trailing/leading/repeated spaces) using folds. By using folds I mean that the folding function has to be the outermost function:

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

推荐答案

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

If I understand correctly, your requirements include

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

的确，如果我们有，那么

Indeed, if we had that, then

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)相矛盾.

您肯定需要在 folder 之后进行一些后处理.

You definitely need some post-processing after the foldr.

这篇关于折叠后无需后处理步骤，是否可以实现文字功能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！