Real World Haskell, capítulo 4, página 98 de la impresión pregunta si {{X0 }} se 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 no espacio debe anteponerse a la última palabra en la lista de salida (esto sucede en la protección otherwise), 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 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 anterior, 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" la salida del pliegue, por ejemplo, {{X0} } si hay 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 realmente es posible implementar words (de 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
21
Enrico Maria De Angelis 29 abr. 2020 a las 10:22

3 respuestas

La mejor respuesta

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 cualquier step y 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.

12
chi 29 abr. 2020 a las 07:36

@chi tiene un argumento maravilloso de que no puedes implementar words usando "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. ;-)

4
luqui 29 abr. 2020 a las 08:26

Si. A pesar de que es un poco complicado, aún puede hacer este trabajo correctamente utilizando un solo foldr y nada más si se detiene en CPS (Estilo de paso de continuación). Había mostrado un tipo especial de chunksOf 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
                                         (False, False) -> (pc++s):ss
                                         (False, True)  -> (pc++s):ss
                                         (True, False)  -> "":s:ss
                                         (True, True)   -> 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 pc como el carácter correcto c a la mano en cada turno. Fue muy útil en la función chunksOf mencionada anteriormente mientras fragmentaba un [Int] en [[Int]] cada vez que se rompía una secuencia ascendente de elementos.

1
Redu 1 may. 2020 a las 20:33