L'implémentation de cette fonction de mots est-elle possible sans étape de post-traitement après le pliage?

Real World Haskell, chapitre 4, page 98 de l'impression demande si wordspeut être implémenté en utilisant des plis, et c'est aussi ma question:

C'est possible? Sinon, pourquoi? Si c'est le cas, comment?

J'ai trouvé ce qui suit, qui est basé sur l'idée que chaque non-espace doit être ajouté au dernier mot de la liste de sortie (cela se produit dans la otherwisegarde), et qu'un espace doit déclencher l'ajout d'un mot vide à la liste de sortie s'il n'y en a pas déjà une (elle est gérée dans le 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

Clairement, cette solution est fausse, car les espaces de tête dans la chaîne d'entrée entraînent une chaîne vide de tête dans la liste de sortie des chaînes.

Au lien ci-dessus, j'ai examiné plusieurs des solutions proposées pour d'autres lecteurs, et beaucoup d'entre elles fonctionnent de manière similaire à ma solution, mais elles "post-traitent" généralement la sortie du pli, par exemple en l' tailintégrant s'il y a est une chaîne de début vide.

D'autres approches utilisent des tuples (en fait juste des paires), de sorte que le pli traite de la paire et peut bien gérer les espaces de début / fin.

Dans toutes ces approches, foldr(ou un autre pli, fwiw) n'est pas la fonction qui fournit la sortie finale hors de la boîte; il y a toujours quelque chose d'autre à régler d'une manière ou d'une autre sur la sortie.

Par conséquent, je reviens à la question initiale et demande s'il est réellement possible d'implémenter words(de manière à ce qu'il gère correctement les espaces de fin / de début / répétés) à l'aide de plis. En utilisant des plis, je veux dire que la fonction de pliage doit être la fonction la plus externe:

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

Si je comprends bien, vos exigences incluent

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

Cela implique que nous ne pouvons pas avoir

words = foldr step base

pour tout stepet base.

En effet, si nous avions cela, alors

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"

et cela contredit (2).

Vous avez certainement besoin d'un post-traitement après le foldr.

@chi a un merveilleux argument selon lequel vous ne pouvez pas implémenter en wordsutilisant "un" pli, mais vous avez dit utiliser pli 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

La fonction la plus externe et la plus interne sont des plis. ;-)

Oui. Même si c'est un peu délicat, vous pouvez toujours faire ce travail correctement en utilisant un seul foldret rien d'autre si vous vous attardez sur le CPS ( Continuation Passing Style ). J'avais montré un type spécial de chunksOffonction auparavant.

Dans ce type de plis, notre accumulateur, d'où le résultat du pli est une fonction et nous devons l'appliquer à une sorte d'identité d'entrée afin que nous ayons le résultat final. Cela peut donc compter comme une étape de traitement final ou non, car nous utilisons ici un seul pli et le type de celui-ci inclut la fonction. Ouvert au débat :)

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 : La valeur de fonction initiale pour commencer.

go : La fonction itérateur

En fait, nous n'utilisons pas pleinement la puissance du CPS ici, car nous avons à la fois le personnage précédent pcet le personnage actuel cà chaque tour. Il était très utile dans la chunksOffonction mentionnée ci-dessus tout en découpant un [Int]en [[Int]]chaque fois qu'une séquence ascendante d'éléments était rompue.