¿Es posible implementar esta función de palabras sin un paso de procesamiento posterior después del plegado?

Real World Haskell, capítulo 4, página 98 de la impresión pregunta si wordsse puede implementar usando pliegues, y esta es mi pregunta también:

¿Es posible? Si no, ¿por qué? Si es así, ¿cómo?

Se me ocurrió lo siguiente, que se basa en la idea de que cada espacio que no sea espacio debe anteponerse a la última palabra en la lista de salida (esto sucede en la otherwiseguardia), y que un espacio debe activar la adición de una palabra vacía a la lista de salida si aún no hay una (esto se maneja en el 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 solución es incorrecta, ya que los espacios iniciales en la cadena de entrada dan como resultado una cadena vacía inicial en la lista de cadenas de salida.

En el enlace de arriba, he examinado varias de las soluciones propuestas para otros lectores, y muchas de ellas funcionan de manera similar a mi solución, pero generalmente "procesan posteriormente" la salida del pliegue, por ejemplo tail, si la hay es una cadena inicial vacía.

Otros enfoques usan tuplas (en realidad solo pares), de modo que el pliegue trata con el par y puede manejar bien los espacios iniciales / finales.

En todos estos enfoques, foldr(u otro pliegue, fwiw) no es la función que proporciona la salida final de la caja; siempre hay algo más que tiene que ajustar la salida de alguna manera.

Por lo tanto, vuelvo a la pregunta inicial y pregunto si es realmente posible implementar words(de una manera que maneje correctamente los espacios finales / iniciales / repetidos) usando pliegues. Al usar pliegues quiero decir que la función de plegado tiene que ser la función más externa:

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

Si entiendo correctamente, sus requisitos incluyen

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

Esto implica que no podemos tener

words = foldr step base

para cualquiera stepy base.

De hecho, si tuviéramos eso, entonces

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"

y esto contradice (2).

Definitivamente necesita algo de procesamiento posterior después de foldr.

@chi tiene un argumento maravilloso que no puedes implementar wordsusando "a" fold, pero dijiste usando fold 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 la función más externa como la más interna son pliegues. ;-)

Si. A pesar de que es un poco complicado, aún puede hacer este trabajo correctamente utilizando un solo foldry nada más si se detiene en CPS ( Estilo de paso de continuación ). Había mostrado un tipo especial de chunksOffunción anteriormente.

En este tipo de pliegues nuestro acumulador, por lo tanto, el resultado del pliegue es una función y tenemos que aplicarlo a un tipo de entrada de identidad para que tengamos el resultado final. Por lo tanto, esto puede contar como una etapa de procesamiento final o no, ya que estamos usando un solo pliegue aquí y el tipo incluye la función. Abierto a 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 : El valor de la función inicial para comenzar.

go : La función iteradora

En realidad, no estamos utilizando completamente el poder del CPS aquí ya que tenemos tanto el carácter anterior pccomo el carácter correcto ca la mano en cada turno. Fue muy útil en la chunksOffunción mencionada anteriormente, mientras fragmentación una [Int]en [[Int]]cada vez que una secuencia ascendente de elementos estaban rotas.