W Real World Haskell, rozdział 4, strona 98 druku, pyta się, czy words
moż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 otherwise
wartowniku) 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 tail
go, 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
źródło
["xa"] == words "xa" == step 'x' (words "a") == step 'x' (words " a") == words "x a" == ["x", "a"]
, co ma tę zaletę, że jest ważnym argumentem dla obu kierunków@chi ma cudowny argument, że nie możesz zaimplementować
words
używając „a” fold, ale powiedziałeś, używając fold s .Zarówno funkcja najbardziej zewnętrzna, jak i wewnętrzna są fałdami. ;-)
źródło
Tak. Mimo że jest to trochę skomplikowane, możesz nadal wykonywać tę pracę poprawnie, używając jednego
foldr
i nic więcej, jeśli rozwiniesz się w CPS ( kontynuacja Passing Style ). Wcześniej pokazałem specjalny rodzajchunksOf
funkcji.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ę :)
sf
: Początkowa wartość funkcji na początek.go
: Funkcja iteratoraW rzeczywistości nie wykorzystujemy w pełni mocy CPS, ponieważ mamy zarówno poprzednią postać, jak
pc
i poprawną postaćc
pod każdym względem. Było to bardzo przydatne wchunksOf
funkcji wspomnianej powyżej, podczas dzielenia[Int]
na za[[Int]]
każdym razem, gdy rosnąca sekwencja elementów była łamana.źródło