A implementação desta função de palavras é possível sem uma etapa de pós-processamento após a dobra?

O Mundo Real Haskell, capítulo 4, página 98 da impressão pergunta se wordspode ser implementado usando dobras, e esta é minha pergunta também:

É possível? Se não, por que? Se for, como?

Eu vim com o seguinte, que é baseado na ideia de que cada não-espaço deve ser anexado à última palavra na lista de saída (isso acontece no otherwiseguarda) e que um espaço deve acionar o acréscimo de uma palavra vazia ao a lista de saída, se ainda não houver uma (isso é tratado no 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

Claramente, esta solução está errada, uma vez que os espaços iniciais na cadeia de entrada resultam em uma cadeia vazia principal na lista de cadeias de saída.

No link acima, examinei várias das soluções propostas para outros leitores, e muitas delas funcionam de forma semelhante à minha solução, mas geralmente "pós-processam" a saída da dobra, por exemplo tail, se houver é uma string inicial vazia.

Outras abordagens usam tuplas (na verdade, apenas pares), para que a dobra lide com o par e possa lidar com os espaços iniciais / finais.

Em todas essas abordagens, foldr(ou outra dobra, fwiw) não é a função que fornece a saída final pronta para uso; sempre há algo mais para ajustar a saída de alguma forma.

Portanto, volto à pergunta inicial e pergunto se é realmente possível implementar words(de uma maneira que ele lide corretamente com espaços à direita / à esquerda / repetidos) usando dobras. Por usando pregas que significa que a função de dobragem tem de ser o mais exterior função:

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

Se bem entendi, seus requisitos incluem

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

Isso implica que não podemos ter

words = foldr step base

para qualquer stepe base.

De fato, se tivéssemos isso, então

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"

e isso contradiz (2).

Você definitivamente precisa de algum pós-processamento após o foldr.

O @chi possui um argumento maravilhoso que você não pode implementar wordsusando a dobra "a", mas você disse usando a dobra 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

Tanto a função mais externa quanto a mais interna são dobras. ;-)

Sim. Mesmo que seja um pouco complicado, você ainda pode fazer esse trabalho corretamente usando um único foldre mais nada se usar o CPS ( Continuation Passing Style ). Eu já havia mostrado um tipo especial de chunksOffunção anteriormente.

Nesse tipo de dobra, nosso acumulador, portanto, o resultado da dobra é uma função e precisamos aplicá-lo a um tipo de entrada de identidade, para que tenhamos o resultado final. Portanto, isso pode contar como um estágio final de processamento ou não, pois estamos usando uma dobra única aqui e o tipo inclui a função. Aberto ao debate :)

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 : O valor inicial da função para começar.

go : A função do iterador

Na verdade, não estamos utilizando totalmente o poder do CPS aqui, já que temos o personagem anterior pce o personagem atual cem cada turno. Foi muito útil na chunksOffunção mencionada acima, enquanto Arrancamento um [Int]em [[Int]]cada vez que uma sequência ascendente de elementos foram quebrados.