Połączyć listę i zsumować z podlistą?

Question

szukam rozwiązania dla mojej klasy Haskell.

Mam listę numerów i muszę zwrócić SUM dla każdej części listy. Części są podzielone przez 0. Potrzebuję użyć funkcji FOLDL.

przykład:
początkową listy: [1,2,3,0,3,4,0,5,2,1]
podlistę [[1,2,3], [3,4], [5,2,1]]
wynik [6,7,7]

mam funkcji znajdowania 0 w początkowej listy:

findPos list = [index+1 | (index, e) <- zip [0..] list, e == 0] 

([4,6] powraca do początkowej listy z przykładu)

oraz funkcja do tworzenia SUMA z FOLDLEM:

sumList list = foldl (+) 0 list 

Ale zupełnie nie udało się umieścić go razem:/

---- Moje rozwiązanie
W końcu znalazłem coś zupełnie innego, że chłopaki sugerowane.
Zajęło mi cały dzień, aby go:/

groups :: [Int] -> [Int] 
groups list = [sum x | x <- makelist list] 

makelist :: [Int] -> [[Int]] 
makelist xs = reverse (foldl (\acc x -> zero x acc) [[]] xs) 

zero :: Int -> [[Int]] -> [[Int]] 
zero x acc | x == 0 = addnewtolist acc 
      | otherwise = addtolist x acc 

addtolist :: Int -> [[Int]] -> [[Int]] 
addtolist i listlist = (i : (head listlist)) : (drop 1 listlist) 

addnewtolist :: [[Int]] -> [[Int]] 
addnewtolist listlist = [] : listlist 

Answer 1

Po rozwiązaniu problemu sam, pokażę ci nieco mniej szczegółową wersję. Foldr wydaje się, moim zdaniem, lepszy od tego problemu *, ale ponieważ poprosił o foldl pokażę moje rozwiązanie za pomocą obu funkcji.

Również Twój przykład jest nieprawidłowy, suma [5,2,1] jest 8, a nie 7.

Wersja foldr.

makelist' l = foldr (\x (n:ns) -> if x == 0 then 0:(n:ns) else (x + n):ns) [0] l 

W tej wersji, to przechodzenie do listy, gdy prąd elementu (x) jest 0, dodać nowy element do listy zasobniku (N: NS). W przeciwnym razie dodajemy wartość bieżącego elementu do wartości przedniego elementu akumulatora i zastępujemy przednią wartość akumulatora tą wartością.

krok po kroku

1. acc = [0], x = 1. Result is [0+1]
2. acc = [1], x = 2. Result is [1+2]
3. acc = [3], x = 5. Result is [3+5]
4. acc = [8], x = 0. Result is 0:[8]
5. acc = [0,8], x = 4. Result is [0+4,8]
6. acc = [4,8], x = 3. Result is [4+3,8]
7. acc = [7,8], x = 0. Result is 0:[7,8]
8. acc = [0,7,8], x = 3. Result is [0+3,7,8]
9. acc = [3,7,8], x = 2. Result is [3+2,7,8]
10. acc = [5,7,8], x = 1. Result is [5+1,7,8] = [6,7,8]

Nie masz go!

I wersja foldl. Działa podobnie jak powyżej, ale tworzy odwróconą listę, stąd użycie odwrócenia na początku tej funkcji, aby odwrócić listę.

makelist l = reverse $ foldl (\(n:ns) x -> if x == 0 then 0:(n:ns) else (x + n):ns) [0] l 

* Składanie listy z prawej strony pozwala minusy (:) funkcyjne do wykorzystania naturalnie, wykorzystując moją metodę z lewego fałdu produkuje odwróconą listę. (Nie jest prawdopodobne, prostszy sposób na lewą wersję krotny że nie myśleć, że eliminuje to trywialności.)

Answer 2

mam zamiar dać Ci kilka wskazówek, zamiast kompletnego rozwiązania, ponieważ brzmi to jak może to być zadanie domowe.

Podoba mi się podział proponowanych kroków. W pierwszym kroku (przechodząc od listy liczb ze znacznikami zerowymi do listy list) sugeruję wykonanie jawnej rekursji; spróbuj to dla szablonu:

splits []  = {- ... -} 
splits (0:xs) = {- ... -} 
splits (x:xs) = {- ... -} 

Można również nadużywać groupBy jeśli jesteś ostrożny.

Po drugie, wygląda na prawie na miejscu; Ostatnim krokiem, którego potrzebujesz, jest przejrzenie funkcji map :: (a -> b) -> ([a] -> [b]), która przyjmuje normalną funkcję i uruchamia ją na każdym elemencie listy.

Jako ćwiczenie dodatkowe warto zastanowić się, w jaki sposób można wykonać całą operację jednym kliknięciem jako pojedynczą zakładkę. Jest to możliwe - i nawet niezbyt trudne, jeśli przejrzysz, jakie musiałyby być typy różnych argumentów do foldr/foldl!

Zwiększenia ponieważ zmienił się pytanie:

Ponieważ wygląda na to, że wypracowane rozwiązanie, teraz czują się komfortowo dając jakieś spoilery. =)

Zaproponowałem dwie możliwe implementacje; taki, który idzie krok po kroku, jak sugerujesz, i drugi, który idzie wszystko naraz.Krok po kroku można wyglądać następująco:

splits []  = [] 
splits (0:xs) = [] : splits xs 
splits (x:xs) = case splits xs of 
    []  -> [[x]] 
    (ys:yss) -> ((x:ys):yss) 

groups' = map sum . splits 

Albo tak:

splits' = groupBy (\x y -> y /= 0) 
groups'' = map sum . splits' 

all-at-once wersja może wyglądać następująco:

accumulate 0 xs  = 0:xs 
accumulate n (x:xs) = (n+x):xs 

groups''' = foldr accumulate [0] 

Do sprawdź, czy je rozumiesz, oto kilka ćwiczeń, które możesz wypróbować:

• Co zrobić, aby splits i splits' zrobić z [1,2,3,0,4,5]? [1,2,0,3,4,0]? [0]? []? Sprawdź swoje prognozy w ghci.
• Przewidzieć, co każda z czterech wersji groups (włącznie z twoimi) wyprowadza dla wejść takich jak [] lub [1,2,0,3,4,0], a następnie przetestuj swoje przewidywania w ghci.
• Zmodyfikuj groups''', aby wyświetlić zachowanie jednej z pozostałych implementacji.
• Zmodyfikuj groups''', aby używać foldl zamiast foldr.

Answer 3

Jak już rozwiązany, inna wersja:

subListSums list = reverse $ foldl subSum [0] list where 
    subSum xs 0 = 0 : xs 
    subSum (x:xs) n = (x+n) : xs 

(przy założeniu, że mają tylko nieujemne liczby w liście)