Czy zaimplementowanie tej funkcji jest możliwe bez kroku przetwarzania końcowego po złożeniu?

W Real World Haskell, rozdział 4, strona 98 druku, pyta się, czy wordsmożna go wdrożyć za pomocą foldów, i to też jest moje pytanie:

Czy to możliwe? Jeśli nie to dlaczego? Jeśli tak, to w jaki sposób?

Wymyśliłem następujące, które są oparte na pomyśle, że każde spacje powinny być poprzedzone ostatnim słowem na liście wyników (dzieje się to w otherwisewartowniku) i że spacja powinna wyzwalać dołączanie pustego słowa do lista wyjściowa, jeśli jeszcze jej nie ma (jest to obsługiwane w 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

Oczywiście to rozwiązanie jest złe, ponieważ początkowe spacje w ciągu wejściowym powodują, że jeden wiodący pusty ciąg jest na wyjściowej liście ciągów.

Pod powyższym linkiem zapoznałem się z kilkoma proponowanymi rozwiązaniami dla innych czytelników, a wiele z nich działa podobnie do mojego rozwiązania, ale generalnie „przetwarzają” wyjście z owczarni, na przykład poprzez wprowadzenie tailgo, jeśli istnieje jest pustym ciągiem wiodącym.

Inne podejścia używają krotek (właściwie tylko par), dzięki czemu fold zajmuje się parą i może dobrze obsługiwać spacje wiodące / końcowe.

We wszystkich tych podejściach foldr(lub innym fold, fwiw) nie jest funkcją, która zapewnia ostateczne wyjście po wyjęciu z pudełka; zawsze jest coś innego z jakoś wyregulowaniem wydajności.

Dlatego wracam do początkowego pytania i pytam, czy rzeczywiście jest możliwe zaimplementowanie words(w sposób, który poprawnie obsługuje spacje końcowe / wiodące / powtarzane) za pomocą foldów. Przez użyciem fałdy To znaczy, że funkcja musi być składany funkcja najbardziej oddalonych:

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

Jeśli dobrze rozumiem, twoje wymagania obejmują

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

Oznacza to, że nie możemy mieć

words = foldr step base

dla każdego stepi base.

Rzeczywiście, gdybyśmy to mieli, to wtedy

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"

i to jest sprzeczne (2).

Na pewno potrzebujesz trochę późniejszego przetwarzania foldr.

@chi ma cudowny argument, że nie możesz zaimplementować wordsużywając „a” fold, ale powiedziałeś, używając 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

Zarówno funkcja najbardziej zewnętrzna, jak i wewnętrzna są fałdami. ;-)

Tak. Mimo że jest to trochę skomplikowane, możesz nadal wykonywać tę pracę poprawnie, używając jednego foldri nic więcej, jeśli rozwiniesz się w CPS ( kontynuacja Passing Style ). Wcześniej pokazałem specjalny rodzaj chunksOffunkcji.

W tego rodzaju fałdach nasz akumulator, stąd wynik fałdu jest funkcją i musimy zastosować go do danych wejściowych, aby uzyskać końcowy wynik. Może to więc być traktowane jako końcowy etap przetwarzania lub nie, ponieważ używamy tutaj pojedynczego zagięcia, a jego typ obejmuje funkcję. Otwarty na debatę :)

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 : Początkowa wartość funkcji na początek.

go : Funkcja iteratora

W rzeczywistości nie wykorzystujemy w pełni mocy CPS, ponieważ mamy zarówno poprzednią postać, jak pci poprawną postać cpod każdym względem. Było to bardzo przydatne w chunksOffunkcji wspomnianej powyżej, podczas dzielenia [Int]na za [[Int]]każdym razem, gdy rosnąca sekwencja elementów była łamana.