Ma première monade

À la recherche d’avis sur ce qui pourrait être amélioré

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut les zesteux !

TL;DR: Je demande l’avis des zesteux sur ce code https://gist.github.com/Ikyushii/52f797c5647ae94515aa

Il y a quelques temps, je me suis mis à Haskell. Le langage m’intéressait et j’avais envie de creuser. J’ai écrit quelques début de code source avec, en m’attaquant parfois à des gros morceaux (je pense notamment à Netwire et son interface basée sur les Arrows.

Ma prochaine ambition est d’utiliser Yesod pour écrire une application web que j’ai en tête depuis plusieurs année déjà. Et plutôt que m’attaquer au framework directement, j’ai pris le parti de commencer par un autre morceau. Une partie non négligeable de l’application consiste à montrer certaines données et leurs évolution au cours du temps. Et bien pour modéliser ça, j’ai décidé d’écrire une monade ! La première de ma vie o_o. Et maintenant je viens humblement demander l’avis de ceux qui s’y connaissent.

Sans plus attendre… La monade Gradiente.

1
2
3
4
5
6
7
newtype Gradiente a v = Gradiente { runGradiente :: a -> v }

instance Monad (Gradiente a) where
    return x = Gradiente $ \_ -> x
    Gradiente ti >>= f = Gradiente $ \ t -> let y = ti t
                                                Gradiente ti' = f y
                                            in ti' t

Le but est donc de représenter une donnée quelconque comme une fonction à un paramètre (dans mon cas, c’est soit une date, soit une distance).

Son implémentation monadique est comme suit. Pour être honnête, je me suis pas mal inspiré de la monade State. J’ai aussi fait une implémentation de la classe Monoid.

1
2
3
instance Monoid v => Monoid (Gradiente a v) where
    mempty = return mempty
    mappend (Gradiente f1) (Gradiente f2) = Gradiente $ \t -> mappend (f1 t) (f2 t)

Maintenant il faut pouvoir exprimer ces fonctions à un argument. Pour pouvoir utiliser la notation do, on a besoin de :

1
2
range :: Gradiente a a
range = Gradiente id

Et du coup on peut écrire des choses cools. Par exemple…

1
2
3
4
loading_text :: Gradiente Int String
loading_text = do
    t <- range
    return $ take t "************"

C’est cool ! Mais de manière amusante c’est un dommage collatérale. Je voulais personnellement exprimer des transformations successives. Pour ça, j’ai d’abord rajouté la notion d’interval.

1
2
3
4
5
6
7
8
9
data Interval a =
      After a
    | Before a
    | Between a a

interval_hit :: Ord a => Interval a -> a -> Bool
interval_hit (After t') t = t >= t'
interval_hit (Before t') t = t <= t'
interval_hit (Between t' t'') t = interval_hit (After t') t && interval_hit (Before t'') t

Quelques constructeurs (ils paraissent bête en l’état, mais je préfère) :

1
2
3
4
5
6
7
8
after :: a -> Interval a
after = After

before :: a -> Interval a
before = Before

between :: a -> a -> Interval a
between = Between

Et ensuite, j’exprime l’idée d’application « temporelle partielle »

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
apply :: Ord a => Interval a -> (v -> v) -> v -> Gradiente a v
apply i f x = do
    t <- range

    let
        res = if interval_hit i t
                then f x
                else x

    return res

fix :: Ord a => Interval a -> v -> v -> Gradiente a v
fix i x = apply i (pure x)

Et avec tout ça je peux m’amuser à écrire des choses comme suit :

1
2
i :: Gradiente Int Int
i = return 0 >>= fix (between 3 8) 5 >>= apply (after 5) (6+)

Et c’est tout ! Merci d’avoir jeté un coup d’œil. Vos remarques sont les bienvenues :).

Édité par lethom

Auteur du sujet

Partons sur le but final. J'ai par exemple un lieu, qui est globalement décrit par un nom et une description. Ce lieu peut subir des événements qui modifient son nom où sa description. Je veux qu'il soit facile, en décrivant à la fois l'état initial et les transformations, de retrouver l'état d'un lieu à un moment donné.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
data Location = Location {
    name :: String,
    description :: String
} deriving (Show)

updateName :: String -> Location -> Location
updateName n l = l { name = n }

updateDesc :: String -> Location -> Location
updateDesc n l = l { description = n }

paris :: Gradiente Int Location -- le Int correspond au temps par exemple en année
paris = return (Location "Paris" "Capitale de France. Un vrai bordel.")
        >>= apply (after 1853) (updateDesc "Capitale de France. Depuis Haussmann, c'est mieux rangé")
        >>= apply (after 1940) (updateDesc "Capitale de France. Occupée par les Allemands")
        >>= apply (after 1944) (updateDesc "Capitale de France. À nouveau libre")
1
2
3
4
5
6
7
8
*Main> runGradiente paris 1000 -- Paris en l'an 1000
Location { name = "Paris", description = "Capitale de France, un vrai bordel" }
*Main> runGradiente paris 1900 -- Paris en l'an 1900
Location { name = "Paris", description = "Capitale de France, depuis Haussmann c'est mieux rangé." }
*Main> runGradiente paris 1942 -- Paris en l'an 1942
Location { name = "Paris", description = "Capitale de France. Occupée par les Allemands." }
*Main> runGradiente paris 2000 -- Paris en l'an 2000
Location { name = "Paris", description = "Capitale de France. À nouveau libre" }

Cette réponse a aidé l'auteur du sujet

Salut,

J'ai peut-être lu trop vite mais il me semble que le type (->) x est déjà instance de la classe monade par défaut.

edit : sinon, ce que tu fais me fait penser à la programmation réactive fonctionnelle.

Édité par Couard anonyme

+1 -0
Auteur du sujet

Oh… Maintenant que tu le dis… J’ai peut-être juste réimplémenté ça en effet x).

Je vais me pendre /o/

Edit : En effet, il suffisait d'écrire

1
2
newtype Gradiente a v = Gradiente { runGradiente :: a -> v }
    deriving (Monad)

Du coup x). Je suis un peu déçu de moi-même. Ceci dit, au moins, j'ai bien compris comment fonctionne cette monade en particulier, on va dire. Merci pour me l'avoir fait remarquer, Couard.

Pour ce qui est de la FRP, c'est vrai. Ça y ressemble, c'en est même, sauf que la FRP va beaucoup plus loin et que j'avais besoin que d'un petit subset, d'où une petite implémentation maison.

Édité par lethom

Auteur du sujet

Pour des raisons d'abstraction. Dans l'idée, ça me permet de n'exporter que ces trois fonctions plutôt que les constructeurs de Interval. De cette façon, je peux changer l'implémentation de Interval sans casser les codes qui l'utilisent. En règle générale, je préfère utiliser des fonctions que directement les constructeurs de mes structures quand je peux. Je sais cependant pas si c'est une bonne pratique encouragée ou non.

Une autre raison, c'est aussi que je peux mettre des contraintes sur between avec un cas d'erreur si les valeurs sont pas cohérentes. Merci de me l'avoir rappelé x)

Édité par lethom

Perso, j'aurais plus vu le truc comme suit :

Pour appliquer une fonction ou non en fonction du temps, on prend une fonction p : t -> Bool, ce que l'on veut modifier x : t -> v, on couple les deux en un truc de type t -> (Bool,v). On compose avec un truc suivant si le Booléen est vrai ou faux pour obtenir t -> (v->v, v), puis on compose avec $.

Édité par Couard anonyme

+0 -0
Auteur du sujet

Pour appliquer une fonction ou non en fonction du temps, on prend une fonction p : t -> Bool, ce que l'on veut modifier x : t -> v, on couple les deux en un truc de type t -> (Bool,v). On compose avec un truc suivant si le Booléen est vrai ou faux pour obtenir t -> (v->v, v), puis on compose avec $.

Couard anonyme

Je vois pas l'avantage par rapport à ce que j'ai écrit ;o. En fait, ce que j'ai implémenté marché déjà comme ça avec la fonction interval_hit. C'est juste « caché ».

@Polio : Certes 8).

Édité par lethom

Pardon, j'ai pas été clair dans mon dernier message.

On a une fonction app : (a->b, a) -> b. Si on a une fonction qui dépend du temps, ainsi qu'une valeur qui dépend du temps, on a quelque chose de type t -> (a->b, a). On peut alors simplement composer avec app pour avoir quelque chose de la forme t -> b. On peut voir la chose comme suit également : fmap app : (t -> (a->b, a)) -> (t -> b) : on se place « dans » t ->.

Ensuite, si on note pair : a -> b -> (a,b) l'unique fonction de son type, on a liftM2 pair : (t -> a) -> (t -> b) -> (t -> (a,b)). Si on a un « prédicat » (pas le bon nom mais tant pis) de type t -> Bool, on peut le transformer en t -> (a -> b) en choisissant la fonction id ou une certaine fonction f suivant si le temps respecte ou non le prédicat. On compose le tout et voilà.

Enfin bon, c'est juste comment je verrais le truc pour le rendre plus « modulaire ». Après, effectivement, on peut manipuler des intervalles et les transformer en leur fonction caractéristique (la fonction qui dit si on est dedans ou pas). C'est juste que là, c'est tout ce que tu faisais avec tes intervalles, de prendre leur fonction caractéristique, c'est pour ça que ça m'a perturbé.

edit : en fait, pour la fonction liftM2 pair, on peut voir les foncteurs applicatifs comme les foncteurs ayant une telle fonction, où on peut « coupler » les objets : (f a) -> (f b) -> (f (a,b)). Haskell considère que l'on doit avoir un truc de type (f (a->b)) -> (f -> a) -> (f -> b), mais personnellement je préfère l'autre vision.

Édité par Couard anonyme

+0 -0

Désolé, c'était encore vraiment pas clair.

J'avais pris le point de vue « foncteur applicatif » : on considère que l'on a quelque chose de type m (a->b) (avec ici m la monade « temporelle »), ainsi que quelque chose de type m a, et on le transforme en quelque chose de type m b. De plus, j'avais voulu présenter en même temps le point de vue « (f a, f b) -> f (a,b) » (une autre manière de voir les foncteurs applicatifs). Une fonction de type m (a->b) » peut se transformer en a -> m b (on passe du point de vue foncteur applicatif au point de vue monade), et dans le cas des fonctions on peut utiliser flip : (t->(a->b)) -> (a->(t->b)).

Voici le code :

1
2
3
4
5
choose : a -> a -> Bool -> a
choose x y b = if b then x else y

apply : (t->Bool) -> (a->a) -> a -> (t->a)
apply pred f = flip $ fmap (choose f id) pred

Je ne sais pas si c'est plus clair ?

+0 -0

Désolé du triple post.

Je vois pas l'avantage par rapport à ce que j'ai écrit ;o.

Ah, pardon… j'ai lu trop vite et j'ai lu « Je ne vois pas le rapport avec ce que j'ai écrit. ».

L'avantage d'avoir une fonction générique t -> Bool au lieu de juste des intervalles, c'est juste que c'est plus modulaire… Par exemple, imaginons que l'on veuille appliquer une fonction ou une autre suivant la parité.

Je préfère la version « foncteur applicatif » que je trouve plus simple (la première que j'ai donnée sans le flip, sauf pour la notation pour les applications successives : je préfère noter x |> f |> g que g $ f x).

Après, on peut aussi gérer les intervalles comme suit. On se sert de (<=x) pour before, (>=x) pour after et between x y = (&&) <$> (>=x) <*> (<=y). C'est peut-être la même chose que between x y t = (t>=x) && (t<=y), mais personnellement je préfère… on prend « (after x) ∩ (before y) ». Après, si on veut pouvoir manipuler les intervalles, on peut créer un type de donnée pour ça, mais il est mieux d'avoir quelque chose qui transforme ce type de données en « prédicat » et s'en occuper séparément (i.e. pas d'apparition de cette fonction à l'intérieur des fonctions comme apply — si on veut, on peut créer une fonction apply_on_interval, des trucs comme ça).

En fait, il faudrait remplacer le type Bool par un type « 2 = 1 + 1 » (au sens « soit on est dans le premier 1, soit dans le deuxième »), avec une manière de transformer tout couple de fonctions de 1 vers a en une fonction de 2 vers a (c'est la fonction « choose » vu de la « bonne manière »).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
x |> f = f <*> x

choose :: (a,a) -> (Bool -> a)
choose (x,y) b = if b then x else y

branch : (v,v) -> (t->Bool) -> (t->v)
branch (f,g) pred = choose (f,g) <$> pred
-- branch est la version « à l'intérieur de t-> » de choose (mais la syntaxe
-- n'est pas bien).

syracuse_step = id |> branch (\n -> n `div` 2, \n -> 3*n + 1) even

apply_cond : (v->v) -> (t->Bool) -> (t->(v->v))
apply_cond f = branch (f,id)

fix_cond :: v -> (t->Bool) -> (t->(v->v))
fix_cond = apply . pure

toto = id |> fix_cond 0 even
+0 -0

Le petit bouton éditer en haut à gauche de ton message sur ordinateur est là pour éviter ça. ;)

Ah oui, merci. Je l'utilise souvent en plus. :(

Je cache tout parce que j'ai l'impression de ne pas être vraiment vraiment dans le sujet.

Concernant les performances, j'imagine que l'on peut faire mieux que de passer à travers autant de fonctions que l'on a fait de modifications.

Comme exercice, on peut faire un mini-DSL pour résoudre les trucs comme « placer les nombres de 1 à 9 sur cette grille pour respecter telles contraintes ». Attention, il ne faut pas de duplication, donc cela nécessite plus que simplement la monade liste (et on pourra essayer de généraliser la construction, bien que les monades ne se « composent » pas aussi bien que les foncteurs applicatifs). On peut passer par de l'algèbre linéaire si toutes les contraintes sont linéaires, mais c'est pas le but ici. Là, les foncteurs applicatifs ne suffisent pas.


On voit que tout ce qui peut être optenu en version « monadique » avec t-> peut l'être en version « applicative » (à cause du fait que l'on puisse passer de a -> m b à m (a -> b)). Intuitivement, on peut toujours considérer que les calculs se passent en parallèle pour toutes les valeurs du type t (une constante accessible dans chacune des branches, séparément).

J'ai pas encore bien étudié le truc, mais par exemple pour a -> Maybe b, on peut avoir ou non une valeur pour chaque a, tandis que pour Maybe (a->b), on a soit une valeur partout, soit nulle part. On voit bien que l'on peut passer du deuxième au premier (toujours vrai, toute instance de Monad est aussi instance de Applicative (de manière cohérente)), mais pas l'inverse (du moins en respectant les autres opérations).

On peut voir intuitivement les constructions faisables avec Functor comme des chaines (tout ce qu'on fait est appliquer des fonctions à l'intérieur), et celles avec Applicative comme des arbres (on peut appliquer des fonctions à plusieurs paramètres (pure est pour les fonctions à 0 paramètre)). Lorsque l'on écrit une expression (un arbre) dans un contexte de foncteur applicatif, les valeurs et le « contexte » (par exemple, Just ou Nothing) sont indépendants. En effet, on peut remplacer tous les types utilisés par le type « unité » 1 (je crois () en Haskell), et on voit que « confondre tous les types » après avoir effectué le calcul est comme « confondre tous les types » à l'intérieur du calcul : la « forme » ne change pas suivant les valeurs. En revanche, avec les monades, la forme/contexte peut changer selon les valeurs (on ne peut pas confondre les types). Mais ici, il n'y a qu'une seule « forme » possible (il n'y a qu'une seule fonction de t vers 1) : une famille indexée par t, et donc les monades ne nous apportent rien.

Autrement dit, si m 1 est isomorphe à 1, alors on ne gagne rien à faire une monade. D'ailleurs, on peut considérer pour « axiomatiser » les foncteurs applicatifs que l'on a une « forme par défaut », un élément de m 1, à la place de pure (et on obtient pure en mappant sur cette forme par défaut). Mais la manière unifiée de voir ça est de se dire que l'on peut appliquer toute fonction « normale » f qui prend un n-uplet à n paramètres de type « F (le foncteur applicatif) de quelque chose » (en « zippant » les valeurs et en mappant la fonction, et ce « zippage » correspond lui-même à appliquer la fonction qui prend n paramètres et retourne le n-uplet correspondant (i.e. la fonction identité : on ne mappe rien)).

Je précise que je dis ça sans le tirer d'une source fiable, et je n'ai pas encore tout bien rendu précis (passionnant mais ça prend du temps de bien étudier et j'ai d'autres trucs à faire, j'y ai déjà passé assez de temps). N'hésitez donc pas à me rectifier.


Imaginons le code suivant, dans la monade t-> :

1
2
3
4
do
  x <- f
  y <- h x
  return (g x y)

Pour pouvoir le transformer en applicatif, il faut que la forme de h x (i.e. fmap (const ()) (h x)) ne dépende pas de x. Pour le faire effectivement, il faut que ce soit le premier paramètre de h qui soit de type t, et non son dernier (la forme ne dépend de rien), donc on fait simplement passer le dernier paramètre de h en premier. Cela correspond à l'arbre suivant (les feuilles sont des éléments quelconques et les nœuds internes sont toujours des fonctions simple que l'on « mappe » mais sur plusieurs paramètres).

1
2
3
4
5
6
7
    g
   _|_
  |   |
  $   f
 _|_
|   |
h   f

On se retrouve donc avec comme code g <$> (h <*> f) <*> f. On voit que f doit alors apparaitre plusieurs fois (on pouvait faire un DAG avec la monade).

Édité par Couard anonyme

+0 -0
Auteur du sujet

Tout ce que tu as écrit est très intéressant, je n’y ai pas encore répondu par simple manque de temps ! Je te fais un retour sur tout ça rapidement. Pour ce qui est des perfs, je ne saurai pas trop dire. Mon but de toute façon est plus de chercher à faire de l’Haskell idiomatique plutôt que performant…

Dans tous les cas, la monade des fonctions me permet de faire vraiment ce que je veux. Dans tous les cas, j’ai pris le parti d’utiliser presque abusivement le mot-clef newtype pour mettre à profit le typage d’haskell. Peut-être qu’à terme j’écrirais un article sur cette utilisation de cette monade.

Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte