Quel type de connaissances ou de formation est nécessaire pour que quelqu'un écrive la définition de foldlM comme ceci? [fermé]

9

Récemment, j'essaie d'utiliser Haskell dans certains de mes systèmes de production de cas réels. Le système de type Haskell m'a vraiment aidé. Par exemple, quand j'ai réalisé que j'avais besoin d'une fonction de type

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

Il existe en fait des fonctions comme foldM, foldlMet foldrM.

Cependant, ce qui m'a vraiment choqué, c'est la définition de ces fonctions, telles que:

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

donc la fonction f'doit être de type:

f' :: a -> b -> b

tel que requis par foldr, alors bdoit être de nature *-> m *, de sorte que toute la définition de foldlMpourrait avoir un sens.

Un autre exemple comprend les définitions de liftA2et<*>

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

J'ai essayé certaines de mes propres solutions avant de jeter un œil au code source. Mais l'écart est si énorme que je ne pense pas que je pourrais jamais trouver cette solution, quel que soit le nombre de lignes de code que j'écrirai à l'avenir.

Ma question est donc de savoir quel type de connaissances ou quelle branche mathématique spécifique est nécessaire pour que quelqu'un raisonne à un niveau aussi abstrait.

Je sais que la théorie des catégories pourrait offrir de l'aide et j'ai suivi cette excellente conférence pendant longtemps et j'y travaille toujours.

Theodora
la source
13
Haskell est une langue. Il contient de nombreux mots et la plupart de ces mots peuvent être utilisés de différentes manières. Lorsque vous apprenez une nouvelle langue, pendant des années, de nombreuses phrases et expressions idiomatiques n'ont aucun sens. Mais plus vous l'utilisez, plus vous voyez de schémas familiers, et les choses que vous pensiez intimidantes et avancées venaient tout naturellement. Se détendre.
luqui

Réponses:

3

En général, la logique etc., j'imagine. Mais vous pouvez aussi l'apprendre en le faisant. :) Avec le temps, vous remarquez certains modèles, prenez quelques astuces.

Comme ça foldravec une chose d'argument supplémentaire. Certains le voient comme se repliant en fonctions afin de pouvoir les combiner à travers .et id(qui sont parfois vraiment <=<et 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)
-}

Certains trouvent plus facile à comprendre en termes syntaxiques plus simples, comme

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

donc quand gest non strict dans son deuxième argument, speut servir d'état passant par la gauche, même si nous nous replions à droite, par exemple.

Will Ness
la source
1
Merci beaucoup, j'essayais de comprendre si cette définition est unique et je ne m'attendais pas à l'utilisation de la composition Kleisli ici. Cette réponse résout vraiment mon doute.
Theodora
vous êtes les bienvenus. :)
Will Ness
4

La meilleure façon de le comprendre est donc de le faire. Ci-dessous, il y a une implémentation de l' foldlMutilisation foldlau lieu de foldr. C'est un bon exercice, essayez-le et revenez plus tard à la solution que je suggérerais. L'exemple explique tout le raisonnement que j'ai fait pour y parvenir, qui peut être différent du vôtre et peut être biaisé parce que je savais déjà comment utiliser un accumulateur de fonctions.

Étape 1 : Essayons d'écrire foldlMen termes defoldl

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

Ici, vous réalisez que f'c'est pur et vous devez extraire le résultat de fpour taper match. La seule façon d'extraire une valeur monadique est avec l' >>=opérateur, mais un tel opérateur doit être bouclé juste après son utilisation.

Donc, en conclusion: chaque fois que vous vous retrouvez avec, j'aimerais déballer complètement cette monade , abandonnez. N'est-ce pas la bonne façon

Étape 2 : Essayons d'écrire foldlMen termes de foldlmais en utilisant d'abord []comme pliable, car il est facile de faire correspondre les motifs (c'est-à-dire que nous n'avons pas vraiment besoin d'utiliser 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, c'était facile. Comparons la définition avec la foldldéfinition habituelle des listes

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

Cool!! ils sont à peu près les mêmes. Le cas trivial concerne exactement la même chose. Le cas récursif est un autre petit peu, vous voulez écrire quelque chose comme: foldlM' f (f z0 x) xs. Mais ce n'est pas compiler comme à l'étape 1, donc vous pourriez penser OK, je ne veux pas appliquer f, juste pour tenir un tel calcul et le composer avec >>=. J'aimerais écrire quelque chose de plus comme foldlM' f (f z0 x >>=) xs si ça avait du sens ...

Étape 3 Réalisez que ce que vous voulez accumuler est une composition de fonction et non un résultat. ( ici, je suis probablement biaisé par le fait que je le savais déjà parce que vous l'avez posté ).

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. 

Par le type initFuncet l'utilisation de nos connaissances de l'étape 2 (la définition récursive), nous pouvons en déduire initFunc = return. La définition de f'peut être complétée en sachant que f'devrait utiliser fet >>=.

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

Comme vous pouvez le voir, ce n'est pas si difficile à faire. Il a besoin de pratique, mais je ne suis pas un développeur de haskell professionnel et je pourrais le faire moi-même, c'est une question de pratique

lsmor
la source
1
Je ne vois pas vraiment ce qui rend un pli gauche plus facile à comprendre qu'un pli droit ici. Le pli droit est beaucoup plus susceptible de produire un résultat utile pour des structures infinies et d'être efficace pour des Monadinstances typiques .
dfeuer
@dfeuer Il ne s'agit pas de montrer un exemple plus simple, mais de proposer un exercice approprié pour l'OP et d'exposer une argumentation raisonnée de la solution, en essayant de prouver qu'il n'est pas nécessaire d'être un haskeller super-maître pour obtenir une telle solution. Les digressions sur l'efficacité ne sont pas prises en compte
lsmor
3

Vous n'avez pas besoin de connaissances spécifiques en mathématiques pour écrire une fonction comme foldM. J'utilise Haskell en production depuis 4 ans déjà, et j'ai aussi du mal à comprendre cette définition de foldM. Mais c'est surtout parce que c'est mal écrit. S'il vous plaît, ne le prenez pas comme une faute personnelle si vous ne comprenez pas un code obscur. Voici une version plus lisible defoldlM

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

Cette fonction n'est pas encore la plus simple. Principalement parce qu'il a une utilisation non typique de l' foldrendroit où l'accumulateur intermédiaire est une fonction. Mais vous pouvez voir quelques méthodes qui rendent cette définition plus lisible:

  1. Commentaires sur les arguments de fonction.
  2. De meilleurs noms d'arguments (toujours courts et idiomatiques, mais ils sont au moins plus lisibles).
  3. La signature de type explicite de la fonction à l'intérieur where(pour que vous connaissiez la forme des arguments).

Après avoir vu une telle fonction, vous pouvez maintenant effectuer une technique de raisonnement équationnel pour développer la définition étape par étape et voir comment cela fonctionne. La capacité de proposer de telles fonctions vient avec l'expérience. Je n'ai pas de solides compétences en mathématicien, et cette fonction n'est pas une fonction typique de Haskell. Mais plus vous vous entraînez, mieux c'est :)

Shersh
la source