Najlepszym sposobem, aby to zrozumieć, jest zrobienie tego. Poniżej znajduje się implementacja foldlM
użycia foldl
zamiast foldr
. To dobre ćwiczenie, spróbuj i przyjdź później do rozwiązania, które zasugeruję. Przykład wyjaśnia wszystkie powody, które podjąłem, aby to osiągnąć, które mogą być inne niż twoje i mogą być stronnicze, ponieważ już wiedziałem o używaniu akumulatora funkcji.
Krok 1 : Spróbujmy pisać foldlM
pod względemfoldl
-- this doesn't compile because f returning type is (m b) and not just (b)
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f z0 xs
-- So let substitute f by some undefined f'
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' z0 xs
where f' = undefined
-- cool, but f' should use f somehow in order to get the monadic behaviour
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' z0 xs
where f' b a = f somethingIDontkNow
Tutaj zdajesz sobie sprawę, że f'
to jest czyste i musisz wyodrębnić wynik f
wpisywania dopasowania. Jedynym sposobem na „wyodrębnienie” wartości monadycznej >>=
jest użycie operatora, ale taki operator musi zostać zawinięty zaraz po użyciu.
Podsumowując: za każdym razem, gdy skończysz z tym, chciałbym w pełni rozwinąć tę monadę , po prostu poddaj się. To nie jest właściwa droga
Krok 2 : Spróbujmy pisać foldlM
w kategoriach, foldl
ale najpierw używaj []
jako składanego, ponieważ łatwo jest dopasować wzór (tzn. Nie musimy tak naprawdę używać fold
)
-- This is not very hard. It is pretty standard recursion schema. :)
foldlM' :: (Monad m) => (b -> a -> m b) -> b -> [a] -> m b
foldlM' f z0 [] = return z0
foldlM' f z0 (x:xs) = f z0 x >>= \c -> foldlM' f c xs
Ok, to było łatwe. Porównajmy definicję ze zwykłą foldl
definicją list
foldlM' :: (Monad m) => (b -> a -> m b) -> b -> [a] -> m b
foldlM' f z0 [] = return z0
foldlM' f z0 (x:xs) = f z0 x >>= \c -> foldlM' f c xs
myfoldl :: (b -> a -> b) -> b -> [a] -> b
myfoldl f z0 [] = z0
myfoldl f z0 (x:xs) = foldl f (f z0 x) xs
Fajne!! są prawie takie same. Trywialna sprawa dotyczy dokładnie tego samego. Rekurencyjne sprawa jest trochę inna, chcesz napisać coś więcej takich jak: foldlM' f (f z0 x) xs
. Ale nie można go skompilować, jak w kroku 1, więc możesz pomyśleć , że nie chcę aplikować f
, tylko po to, aby przeprowadzić takie obliczenie i skomponować je >>=
. Chciałbym napisać coś więcej, foldlM' f (f z0 x >>=) xs
gdyby miał sens ...
Krok 3 Zdaj sobie sprawę, że to, co chcesz kumulować, to kompozycja funkcji, a nie wynik. ( tutaj prawdopodobnie jestem stronniczy przez to, że już to wiedziałem, ponieważ to opublikowałeś ).
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' initFunc xs
where initFunc = undefined :: b -> m b
f' = undefined :: (b -> m b) -> a -> (b -> m b) -- This type signature can be deduce because f' should be applied to initFunc and a's from t a.
Poprzez rodzaj initFunc
i wykorzystanie naszej wiedzy z kroku 2 (definicja rekurencyjna) możemy to wywnioskować initFunc = return
. Definicję f'
można uzupełnić wiedząc, że f'
należy użyć f
i >>=
.
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' return xs z0
-- ^^^^^^
-- |- Initial value
where f' b a = \bvalue -> b bvalue >>= \bresult -> f bresult a -- this is equivalent to (b >=> \result -> f result a) which captures the sequence behaviour of the implementation
-- ^ ^^^^^^ ^^^^^^^
-- | | |- This is the result of previous computation
-- | |- f' should return a function b -> m b. Any time you have to return a function, start writing a lambda
-- |- This b is the accumulated value and has type b -> m b
-- Following the types you can write this with enough practise
Jak widać, nie jest to takie trudne. Potrzebuje praktyki, ale nie jestem profesjonalnym programistą haskell i mógłbym to zrobić sam, to kwestia praktyki