Jaka wiedza lub szkolenie jest potrzebne, aby ktoś mógł zapisać taką definicję foldlM? [Zamknięte]

Ostatnio próbuję użyć Haskell w moim prawdziwym systemie produkcji skrzynek. System typów Haskell naprawdę oferuje mi ogromną pomoc. Na przykład, kiedy zdałem sobie sprawę, że potrzebuję jakiejś funkcji typu

f :: (Foldable t, Monad m) => ( a-> b -> m b) -> b -> t a -> m b

Istnieje rzeczywiście działa jak foldM, foldlMi foldrM.

Jednak najbardziej zaskoczyła mnie definicja tych funkcji, takich jak:

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

więc funkcja f'musi być typu:

f' :: a -> b -> b

zgodnie z wymaganiami foldr, bmusi być zatem uprzejmy *-> m *, aby cała definicja foldlMmogła mieć sens.

Kolejny przykład obejmuje definicje liftA2i<*>

(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 id

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)

Wypróbowałem kilka własnych rozwiązań, zanim zajrzałem do kodu źródłowego. Ale różnica jest tak duża, że ​​nie sądzę, żebym kiedykolwiek wymyślił takie rozwiązanie, bez względu na to, ile wierszy kodu napiszę w przyszłości.

Moje pytanie brzmi: jaki rodzaj wiedzy lub która konkretna gałąź matematyki jest niezbędna, aby ktoś mógł rozumować na tak wysoce abstrakcyjnym poziomie.

Wiem, że teoria kategorii może zaoferować pomoc i śledzę ten wspaniały wykład od dłuższego czasu i wciąż nad nim pracuję.

Ogólnie wyobrażam sobie logikę. Ale możesz się tego także nauczyć, robiąc to. :) Z czasem zauważysz pewne wzory, podnieś sztuczki.

Tak foldrz dodatkową argumentacją. Niektórzy postrzegają to jako składanie na funkcje, dzięki czemu można je łączyć .i id(które czasami są naprawdę <=<i return),

foldr g z xs  =  foldr ($) z . map g $ xs
              =  foldr (.) id (map g xs) z
         ~/=  foldr (<=<) return (map g xs) z
{-
  (\f -> f . f) :: (a -> a) -> (a -> a)

  (\f -> f <=< f) :: Monad m => (a -> m a) -> (a -> m a)
                            (still just a type, not a kind)
-}

Niektórzy uważają, że łatwiej to zrozumieć w prostszych, syntaktycznych terminach, jak

foldr g z [a,b,c,...,n] s =
     g a (foldr g z [b,c,...,n]) s

więc kiedy gnie jest ścisły w swoim drugim argumencie, smoże służyć jako stan przekazywany od lewej, mimo że składamy po prawej, jako jeden przykład.

Najlepszym sposobem, aby to zrozumieć, jest zrobienie tego. Poniżej znajduje się implementacja foldlMużycia foldlzamiast 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ć foldlMpod 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 fwpisywania 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ć foldlMw kategoriach, foldlale 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łą foldldefinicją 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 initFunci 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ć fi >>=.

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

Nie potrzebujesz żadnej konkretnej wiedzy z matematyki, aby napisać taką funkcję foldM. Używam Haskell w produkcji już od 4 lat, a także mam problemy ze zrozumieniem tej definicji foldM. Ale to głównie dlatego, że jest źle napisane. Nie traktuj tego jako osobistej winy, jeśli nie rozumiesz jakiegoś niejasnego kodu. Oto bardziej czytelna wersjafoldlM

foldlM
    :: forall t m a b .
       (Foldable t, Monad m)
    => (b -> a -> m b)  -- ^ Monadic action
    -> b                -- ^ Starting accumulator
    -> t a              -- ^ List of values
    -> m b              -- ^ Computation result inside a monad
foldlM f z xs = (foldr step pure xs) z
  where
    step :: a -> (b -> m b) -> b -> m b
    step cur next acc = do
        result <- f acc cur
        next result

Ta funkcja wciąż nie jest najłatwiejsza. Głównie dlatego, że ma nietypowe zastosowanie w foldrprzypadku, gdy akumulator pośredni jest funkcją. Ale widać kilka majów, które czynią taką definicję bardziej czytelną:

1. Komentarze na temat argumentów funkcji.
2. Lepsze nazwy argumentów (wciąż krótkie i idiomatyczne, ale są przynajmniej bardziej czytelne).
3. Wyraźny podpis typu funkcji wewnątrz where(dzięki czemu znasz kształt argumentów).

Po obejrzeniu takiej funkcji możesz teraz wykonać technikę wnioskowania równania, aby krok po kroku rozwinąć definicję i zobaczyć, jak ona działa. Możliwość wymyślenia takich funkcji wiąże się z doświadczeniem. Nie mam silnych umiejętności matematycznych, a ta funkcja nie jest typową funkcją Haskella. Ale im więcej ćwiczysz, tym lepiej będzie :)