Какие знания или обучение необходимы для того, чтобы кто-то записал определение сгиба, как это? [закрыто]

В последнее время я пытаюсь использовать Haskell в некоторых моих реальных производственных системах. Система типов Haskell действительно предлагает мне большую помощь. Например, когда я понял, что мне нужна какая-то функция типа

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

Есть на самом деле такие функции , как foldM, foldlMи foldrM.

Однако, что действительно шокировало меня, так это определение этих функций, таких как:

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

поэтому функция f'должна иметь тип:

f' :: a -> b -> b

как того требует foldr, то bдолжно быть добрым *-> m *, чтобы все определение foldlMмогло иметь смысл.

Другой пример включает в себя определения liftA2и<*>

(<*>) :: 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)

Я попробовал некоторые из моих собственных решений, прежде чем заглянуть в исходный код. Но разрыв настолько велик, что я не думаю, что смогу когда-нибудь придумать это решение, независимо от того, сколько строк кода я напишу в будущем.

Поэтому мой вопрос в том, какие знания или какая конкретная математическая отрасль необходима кому-либо для рассуждений на столь отвлеченном уровне.

Я знаю, что теория категорий может предложить некоторую помощь, и я давно слежу за этой замечательной лекцией и все еще работаю над ней.

В общем, логика и т. Д. Я бы вообразил. Но вы также можете научиться этому, делая это. :) Со временем вы замечаете некоторые закономерности, подбираете некоторые хитрости.

Вот так foldrс дополнительным аргументом. Некоторые видят, что это складывается в функции, чтобы их можно было объединить с помощью .и id(что иногда действительно <=<и 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)
-}

Некоторым легче понять это в более простых, синтаксических терминах, так как

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

поэтому, когда не gявляется строгим во втором аргументе, sможет служить состоянием, передаваемым слева, даже если мы сворачиваем справа, как один пример.

Так что лучший способ понять это - это сделать. Ниже приведена реализация foldlMиспользования foldlвместо foldr. Это хорошее упражнение, попробуйте его и попробуйте позже найти решение, которое я бы предложил. В этом примере объясняются все причины, по которым я это сделал, которые могут отличаться от ваших и могут быть предвзятыми, поскольку я уже знал об использовании аккумулятора функций.

Шаг 1 : Давайте попробуем написать foldlMс точки зренияfoldl

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

Здесь вы понимаете, что f'это чисто, и вам нужно извлечь результат fдля соответствия типа. Единственный способ «извлечь» монадическое значение - использовать >>=оператор, но такой оператор должен быть перенесен сразу после его использования.

Итак, в заключение: каждый раз, когда вы в конечном итоге, я хотел бы полностью развернуть эту монаду , просто сдаваться. Это не правильный путь

Шаг 2 : Давайте попробуем писать foldlMв терминах, foldlно сначала используем []как складываемые, так как сопоставление с образцом легко (т.е. нам на самом деле не нужно использовать 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

Хорошо, это было легко. Давайте сравним определение с обычным foldlопределением списков

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

Круто!! они почти одинаковые. Тривиальный случай примерно такой же. Рекурсивный случай немного по- другому, вы хотели бы написать что - то подобное: foldlM' f (f z0 x) xs. Но это не компилируется, как в шаге 1, так что вы можете подумать, ОК, я не хочу применять f, просто чтобы провести такое вычисление и составить его >>=. Я хотел бы написать что-то более похожее, foldlM' f (f z0 x >>=) xs если бы это имело смысл ...

Шаг 3 Поймите, что то, что вы хотите накапливать, является композицией функций, а не результатом. ( здесь я, вероятно, предвзятый факт, что я уже знал это, потому что Вы отправили это ).

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. 

По типу initFuncи использованию наших знаний из шага 2 (рекурсивное определение) мы можем вывести это initFunc = return. Определение f'может быть завершено, зная, что f'следует использовать fи >>=.

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

Как видите, это не так уж сложно сделать. Это требует практики, но я не профессиональный разработчик Haskell, и я мог бы сделать это сам, это вопрос практики

Вам не нужно никаких специальных знаний по математике, чтобы написать такую ​​функцию, как foldM. Я использую Haskell в производстве уже 4 года, и я также пытаюсь понять это определение foldM. Но это в основном потому, что оно плохо написано. Пожалуйста, не воспринимайте это как личную ошибку, если вы не можете понять какой-то непонятный код. Вот более читаемая версияfoldlM

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

Эта функция все еще не самая простая. Главным образом потому, что он имеет нетипичное использование, foldrгде промежуточный аккумулятор является функцией. Но вы можете увидеть несколько парней, которые делают такое определение более читабельным:

1. Комментарии о аргументах функции.
2. Лучшие имена аргументов (все еще короткие и идиоматические, но они, по крайней мере, более читабельны).
3. Явная сигнатура типа функции внутри where(чтобы вы знали форму аргументов).

Увидев такую ​​функцию, вы можете выполнить технику эквационального рассуждения, чтобы пошагово расширить определение и посмотреть, как оно работает. Умение придумывать такие функции приходит с опытом. У меня нет сильных математических навыков, и эта функция не является типичной функцией Хаскеля. Но чем больше у вас практики, тем лучше становится :)