Questions sur les typeclass

Bonjour à tous,

Récemment je me suis remis à apprendre la langage Haskell. En guise d'exercice j'ai essayé d'implémenter des vecteurs à 2 et 3 dimensions dans le but d'écrire un raytracer vraiment basique (les exemples pullulent sur le net). Bien que ce soit un cas assez basique, il y a à mon sens plusieurs manières de représenter un type Vecteur à 2 ou 3 dimensions, j'ai choisi d'utiliser une typeclass étant donné que beaucoup d'opérations sur les vecteurs à 2 et 3 dimensions se ressemblent.

J'ai donc plusieurs questions à poser à des Haskelleux plus expérimentés sur la pertinence d'une telle implémentations. J'écris mes questions un peu en vrac, vous trouverez le code à la fin du post.

1) J'utilise ici des tuples plutôt que des listes (contrairement à ce qu'on peut trouver ici). Est-ce que c'est plus idiomatique de faire de cette façon ? L'implémentation avec des listes est certes plus sexy parce qu'on peut facilement itérer dessus à coup de map ou zipWith, mais est-ce que cela ne pose pas des problèmes de "sécurité" par la suite ? Avec des tuples je suis sûr de la dimension des données que je manipule alors que ce n'est pas le cas avec des listes.

2) Je préfère utiliser un type paramétrique pour définir les vecteurs, ainsi j'ai plus de liberté par la suite si je veux manipuler autre chose que des instances de Num. Qu'en pensez-vous ?

3) Qu'en est-il des foncteurs ? Il y aurait t-il des avantages à représenter des vecteurs sous forme de liste et d'utiliser un foncteur pour les manipuler ?

Je suis désolé si les questions sembles confuses, n'hésitez pas à donner votre commentaire sur le code, tout est bon à prendre !

Merci d'avance

Le code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

module Vectors where


import Prelude hiding ((*>), (<*>))


data Vector2D a = Vect2D (a, a) deriving (Show, Eq)
data Vector3D a = Vect3D (a, a, a) deriving (Show, Eq)


class Vector v where

     -- Basic operations
    (<+>) :: Num a => v a -> v a -> v a -- u+v

    (<->) :: Num a => v a -> v a -> v a -- u-v
    u <-> v = u <+> neg v

    (*>)  :: Num a => a -> v a -> v a   -- k*v
    k *> v = appEach (*k) v

    neg :: Num a => v a -> v a          -- -v
    neg v = (-1) *> v

    (<.>) :: Num a => v a -> v a -> a   -- u.v

    -- Norms and distances
    normalize :: (Floating a, Eq a) => v a -> v a
    normalize v =
        case norm v of
            0 -> 0 *> v
            n -> (1/n) *> v

    mag :: Num a => v a -> a
    mag v = v <.> v

    norm :: Floating a => v a -> a
    norm = sqrt . mag

    mkNormedVect :: (Floating a, Eq a) => v a -> v a -> v a
    mkNormedVect a b = normalize $ b <-> a

    dist :: Floating a => v a -> v a -> a
    dist u v = norm $ v <-> u

    -- Apply f to each component
    appEach :: (a -> b) -> v a -> v b


instance Vector Vector3D where

    Vect3D (a, b, c) <+> Vect3D (x, y, z) = Vect3D (a+x, b+y, c+z)

    Vect3D (a, b, c) <.> Vect3D (x, y, z) = a*x + b*y + c*z

    appEach f (Vect3D (x, y, z)) = Vect3D (f x, f y, f z)


instance Vector Vector2D where

    Vect2D (a, b) <+> Vect2D (x, y) = Vect2D (a+x, b+y)

    Vect2D (a, b) <.> Vect2D (x, y) = a*x + b*y

    appEach f (Vect2D (x, y)) = Vect2D (f x, f y)

-- u*v
(<*>) :: Num a => Vector3D a -> Vector3D a -> Vector3D a
Vect3D (a, b, c) <*> Vect3D (x, y, z) = Vect3D (b*z - c*y, c*x - a*z, a*y - b*x)

Ce qui me gêne le plus avec ta solution c'est que tu te répète. Globalement tes implémentation pour les vecteurs 2d et 3d font la même chose au nombre d'éléments prêt. Tu devrais n'écrire qu'un seul code pour additionner deux vecteurs de la même taille car quelques soit sa dimension, c'est toujours l'addition des éléments termes à termes. En soit l'implémentation avec les listes me semble ainsi plus logique, à condition que les opérations soient cohérente et que tu n'autorise pas, par exemple, à additionner deux vecteurs de taille différentes.

En soit l'implémentation avec les listes me semble ainsi plus logique, à condition que les opérations soient cohérente et que tu n'autorise pas, par exemple, à additionner deux vecteurs de taille différentes.

Et si tu veux t'amuser un peu, tu peux même encoder ça statiquement tant que tes opérations restent simples (pour l'addition ou des produits de matrices, par exemple, ça marche très bien). N'hésite pas à chercher un peu et à revenir si tu ne trouves pas.

Edit : d'ailleurs, il existe sûrement quelque part une extension de haskell qui permet plus ou moins d'écrire un encodage de la taille plus flexible que celui auquel je pense. Mais bon, c'est pour plus tard.

Super merci pour vos réponses !

Je vais donc implémenter les vecteurs avec les listes, le code sera plus court et plus élégant. J'ai pas bien compris la réponse de Zéphyr par contre. Qu'est-ce que tu entends pas encoder ça statiquement ? Est-ce que tu parles de la taille des vecteurs, c'est-à-dire qu'il faudrait se la trimballer en même temps que les vecteurs pour être sûr de ne pas faire d'erreurs ?

Je pense qu'il veut dire que les opérations devraient générer des erreurs a la compilation si tu essai d'additionner deux éléments qui ne sont pas de la même taille et non à l'exécution. Il n'y pas forcément besoin que la taille soit encodé en dur pour cela.

Quand tu essayes de créer un type, il faut toujours réfléchir au typeclass qui correspondent à ton type : ça peut toujours aider à faire ce que tu veux, en plus de t'éviter de réinventer la roue.

Typiquement, appEach :: (a -> b) -> v a -> v b correspond exactement au type de fmap. Il serait donc logique qu'un vecteur soit instance de Functor. Et ça se fait de manière triviale :

1
2

instance Functor Vector2D where
    fmap f (Vect2D (a, b)) = Vect2D (f a, f b)

Au passage, quel intérêt de mettre un tuple dans ton type plutôt que de mettre directement tes données : data Vector2D a = Vect2D a a semble plus naturel.

Autre point intéressant, tu défini plusieurs opérateurs qui n'ont pour but que d'appliquer une fonction élément par élément à tes vecteurs. Ça ressemble fortement à ce qu'on peut faire avec Applicative :

1
2
3

instance Applicative Vector2D where
    pure a = Vect2D a a
    (Vect2D fa fb) <*> (Vect2D a b) = Vect2D (fa a) (fb b)

À partir de là, tu obtiens une méthode générique pour appliquer une fonction sur des vecteurs membre à membre.

Typiquement :

1
2
3

neg a = (\x -> -x) <$> a
a <+> b = (+) <$> a <*> b
mult l a = (*l) <$> a

Une autre chose importante par rapport à ta question 2 : quel intérêt de pouvoir avoir autre chose que du Num dans tes vecteurs? Mathématiquement, les espaces vectoriels ne se définissent que sur des corps, ce qui correspond très grossièrement au typeclass Fractionnal. Ce qui veux dire qu'il n'y a aucun intérêt d'avoir un vecteur qui contient autre chose que des éléments de Fractionnal. Vu que ton espace vectoriel forme un groupe, il serait logique qu'il soit instance de Num (encore une fois, c'est pas une correspondance parfaite).

Quand à la question du choix entre liste et définition directe, l'utilisation de Functor et Applicative rends l'intérêt des liste assez faible à mon sens, d'autant que ce n'est pas le rôle d'une liste. La seule chose qu'il te manque avec Functor et Applicative, c'est le fait de pouvoir faire un produit scalaire, ce qui peut être généralisé avec une instance de Foldable :

1
2
3
4

instance Foldable Vector2D where
    foldr f e (Vect2D a b) = f a (f b e)

dot a b = foldr (+) 0 $ (*) <$> a <*> b

En fait, la seule chose qui pose problème ici est le fait qu'il y a du code "dupliqué" entre Vector2D et Vector3D. La seule solution que je vois pour résoudre ce problème est d'introduire une récursivité dans le type et d'utiliser cette généricité dans les instances à déclarer (et d'ajouter un nombre non négligeable d'extensions du langage). Ça me semble bien complexe et peu intéressant si tu comptes utiliser uniquement des vecteurs en 2 et 3 dimensions. Par contre, si tu veux un large panel de vecteurs, c'est possible et c'est ce qui est fait dans le package Vec.

J'ai pas bien compris la réponse de Zéphyr par contre. Qu'est-ce que tu entends pas encoder ça statiquement ? Est-ce que tu parles de la taille des vecteurs, c'est-à-dire qu'il faudrait se la trimballer en même temps que les vecteurs pour être sûr de ne pas faire d'erreurs ?

Je parle bien de faire une vérification sur la taille des vecteurs, mais d'une vérification statique. Si tu te « trimballes la taille en même temps que les vecteurs », tu vas pouvoir vérifier dynamiquement, c'est-à-dire à l'exécution, que deux vecteurs que tu additionnes ont bien la même taille. Ce qui serait super, c'est de ne même pas avoir besoin de faire cette vérification à l'exécution et de n'autoriser le code à compiler que si les additions sont forcément faites sur des vecteurs de la même taille.

Du coup, il va bien falloir écrire cette taille quelque part, mais pas dans la valeur de tes vecteurs, puisqu'elle n'est pas disponible à la compilation. La solution, c'est de faire apparaître cette taille dans leur type. Je te laisse réfléchir un peu à ça. Ne te prends pas non plus trop la tête dessus : c'est une astuce assez technique, et si tu débutes, il ne faut pas te laisser noyer. Mais si ça t'amuse, n'hésite pas.

Salut à tous !

Merci beaucoup pour tous vos retours, cela m'a bien aidé à mieux comprendre les typeclass, Functor et Applicative. J'ai donc repris (honteusement) les explications de Berdes pour arriver à ça :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

module Vectors where

    
data Vector a = Vect2d a a
              | Vect3d a a a
                  deriving (Eq, Show)

                           
instance Functor Vector where

    fmap f (Vect2d x y) = Vect2d (f x) (f y)
    fmap f (Vect3d x y z) = Vect3d (f x) (f y) (f z)


instance Applicative Vector where

    pure x = Vect3d x x x

    (Vect2d fx fy) <*> (Vect2d x y) = Vect2d (fx x) (fy y)
    (Vect3d fx fy fz) <*> (Vect3d x y z) = Vect3d (fx x) (fy y) (fz z)


instance Foldable Vector where

    foldr f e (Vect2d x y) = f x (f y e)
    foldr f e (Vect3d x y z) = f x $ f y (f z e)


-- Basic vector manipulation
(<+>) :: Num a => Vector a -> Vector a -> Vector a
u <+> v = (+) <$> u <*> v

(<->) :: Num a => Vector a -> Vector a -> Vector a
u <-> v = (-) <$> u <*> v

cross :: Num a => Vector a -> Vector a -> Vector a
cross (Vect3d a b c) (Vect3d x y z) = Vect3d (b*z - c*y) (c*x - a*z) (a*y - b*x)

dot :: Num a => Vector a -> Vector a -> a
dot u v = foldr (+) 0 $ (*) <$> u <*> v

neg :: Num a => Vector a -> Vector a
neg u = (\x -> -x) <$> u

mul :: Num a => a -> Vector a -> Vector a
mul k u = (*k) <$> u 

-- Norm and distance
mag :: Num a => Vector a -> a
mag u = dot u u

norm :: Floating a => Vector a -> a
norm = sqrt . mag

normalize :: (Floating a, Eq a) => Vector a -> Vector a
normalize v =
    case norm v of
        0 -> pure 0
        n -> mul (1/n) v

mkNormedVect :: (Floating a, Eq a) => Vector a -> Vector a -> Vector a
mkNormedVect u v = normalize $ v <-> u

dist :: Floating a => Vector a -> Vector a -> a
dist u v = norm $ u <-> v

Le code est en effet bien plus sympa à lire et bien plus idiomatique. Je n'ai plus de questions particulières à ce sujet donc je marque le thread comme résolu. Est-ce que vous avez néanmoins des commentaires à faire sur ce code ?

Utiliser des tuples et triplets était à mon sens plus sûr, cela évite de s’emmêler les pinceaux en développant. J'ai cependant essayer de réfléchir quelques minutes sur la proposition de Zephyr mais sans succès. Voilà le genre de choses que j'ai tentées :

1
2
3
4
5
6
7
8

data Vector a = Vector [a] Int
                    deriving (Eq, Show)

(<+>) :: Num a => Vector a -> Vector a -> Vector a
(Vector u size1) <+> (Vector v size2)
    | size1 == size2 = Vector (zipWith (+) u v) size1

test = (Vector [1, 2] 2) <+> (Vector [1, 2, 3] 3)

Cependant le code ne plante que à l'exécution, pas à la compilation. A quelles techniques est-ce que tu pensais ? Je suis curieux même si comme tu l'as dit c'est pas vraiment primordial lorsque l'on débute. Ca pourrait surement me servir plus tard.

Merci à tous en tout cas, c'est bien plus clair maintenant

Attention ! Actuellement, les vecteurs 2D et les vecteurs 3D ont le même type, ce qui fait que Vect2D 1 2 <+> Vect3D 1 2 3 est valide d'un point de vue du type et ne posera problème qu'à l'exécution.

Pour continuer à grouper un maximum de code, il faut que tu fasses une typeclass Vector comme tu avais fait au début. Par contre, Functor, Applicative et Foldable devront être dupliqués entre Vector2D et Vector3D.

Tu pourrais du coup faire :

1
2
3
4
5
6
7

class (Applicative v, Foldable v) => Vector v where
    (<+>) :: Num a => v a -> v a -> v a
    u <+> v = (+) <$> u <*> v
    -- tout ce que tu veux sauf cross qui est spécifique à Vector3D

instance Vector Vector2D
instance Vector Vector3D

Salut Berdes et merci pour ta réponse.

J'avais en effet pensé à faire comme tu me l'avais indiqué, c'est-à-dire créer une classe Vector dérivant de Applicative et Foldable afin d'englober les opérations sur les vecteurs, mais je n'avais pas Haskell sous à la main à ce moment là puis j'ai oublié…

Voici mon code final (du moins je l'espère ) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

module Vectors where


data Vector2d a = Vect2d a a deriving (Eq, Show)
data Vector3d a = Vect3d a a a deriving (Eq, Show)


instance Vector Vector2d
instance Vector Vector3d

class (Applicative v, Foldable v) => Vector v where

    (<+>) :: Num a => v a -> v a -> v a
    u <+> v = (+) <$> u <*> v

    (<->) :: Num a => v a -> v a -> v a
    u <-> v = u <+> neg v

    dot :: Num a => v a -> v a -> a
    dot u v = foldr (+) 0 $ (*) <$> u <*> v

    neg :: Num a => v a -> v a
    neg u = mul (-1) u

    mul :: Num a => a -> v a -> v a
    mul k u = (*k) <$> u 

    mag :: Num a => v a -> a
    mag u = dot u u

    norm :: Floating a => v a -> a
    norm = sqrt . mag

    normalize :: (Floating a, Eq a) => v a -> v a
    normalize v =
        case norm v of
            0 -> pure 0
            n -> mul (1/n) v

    mkNormedVect :: (Floating a, Eq a) => v a -> v a -> v a
    mkNormedVect u v = normalize $ v <-> u

    dist :: Floating a => v a -> v a -> a
    dist u v = norm $ u <-> v


instance Functor Vector2d where
    fmap f (Vect2d x y) = Vect2d (f x) (f y)

instance Functor Vector3d where
    fmap f (Vect3d x y z) = Vect3d (f x) (f y) (f z)

instance Applicative Vector2d where
    pure x = Vect2d x x
    (Vect2d fx fy) <*> (Vect2d x y) = Vect2d (fx x) (fy y)

instance Applicative Vector3d where
    pure x = Vect3d x x x
    (Vect3d fx fy fz) <*> (Vect3d x y z) = Vect3d (fx x) (fy y) (fz z)

instance Foldable Vector2d where
    foldr f e (Vect2d x y) = f x (f y e)

instance Foldable Vector3d where
    foldr f e (Vect3d x y z) = f x $ f y (f z e)


cross :: Num a => Vector3d a -> Vector3d a -> Vector3d a
cross (Vect3d a b c) (Vect3d x y z) = Vect3d (b*z - c*y) (c*x - a*z) (a*y - b*x)

Encore un grand merci pour avoir pris le temps de me répondre. Je pense que cette implémentations des vecteurs est un bon moyen de se familiariser avec les typeclass que propose Haskell, du moins c'est bien plus clair pour moi maintenant

Autrement, si tu veux réduire la taille de ton code, il faut savoir que GHC peut ajouter des fonctionnalités qui ne sont pas dans les specs Haskell mais qui peuvent être bien pratiques.

Le premier exemple est l'instance de Functor. Il a été prouvé qu'il ne peut y avoir qu'une "bonne" instance de Functor pour un type donnée (par "bonne", on entend une instance qui n'utilise pas undefined où d'autres trucs dans le genre). Il est donc tout à fait possible d'automatiser la création de cette instance.

GHC propose aussi de créer l'instance de Foldable automatiquement.

Pour utiliser ces ajouts, il faut soit spécifier à la compilation les options -XDeriveFunctor -XDeriveFoldable, soit ajouter une indication au début de ton fichier :

1

{-# Language  DeriveFunctor, DeriveFoldable #-}

Ensuite, il te suffit d'écrire :

1
2

data Vector2d a = Vect2d a a deriving (Eq, Show, Functor, Foldable)
data Vector3d a = Vect3d a a a deriving (Eq, Show, Functor, Foldable)

Je ne connaissais pas du tout ces fonctionnalités, je viens d'essayer et ça marche bien, c'est bien pratique. Je vais me renseigner davantage là-dessus ce soir lorsque j'aurai un peu plus de temps.

Merci beaucoup pour ton aide !