Ma première monade

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 :).

C'est peut-être moi, mais je ne comprends absolument pas ce que tu cherches à faire…

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

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.

Bah, c'est pas inutile de réinventer la roue.

Après, pourquoi avoir créé les fonctions before, after, etc. alors que ce sont juste des synonymes de After, etc. ?

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)

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

NON, tu as un livre à terminer.

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

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.

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 ?

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

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

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.

1
2
3
4

do
  x <- f
  y <- h x
  return (g x y)

1
2
3
4
5
6
7

    g
   _|_
  |   |
  $   f
 _|_
|   |
h   f

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.