Pourquoi (a,b,c,d) n'est-il pas un sucre pour (a,(b,(c,(d,()))))) ?

Question

Il est clair que tout n-uplet peut être représenté par un ensemble de 2-tuples imbriqués. Alors pourquoi n'est-ce pas la même chose en Haskell ? Cela casserait-il quelque chose ?

Rendre ces types équivalents rendrait l'écriture de fonctions sur les tuples beaucoup plus facile. Par exemple, au lieu de définir zip,zip2,zip3,etc., vous pourriez définir une seule fonction zip qui fonctionnerait pour tous les tuples.

Bien sûr, vous peut fonctionne avec des 2-tuples imbriqués, mais c'est laid et il n'y a pas de manière canonique d'effectuer l'imbrication (i.e. devons-nous imbriquer à gauche ou à droite ?).

Answer 1

Le type (a,b,c,d) a un profil de performance différent de celui de (a,(b,(c,(d,())))) . En général, l'indexation dans un n-tuple prend O(1) alors que l'indexation d'une "hlist" de n nuples imbriqués nécessite O(n) .

Ceci étant dit, vous devriez consulter le travail classique d'Oleg sur HLists . L'utilisation de HLists nécessite une utilisation extensive, et quelque peu sommaire, de la programmation au niveau des types. Beaucoup de gens trouvent cela inacceptable, et ce n'était pas disponible dans les premiers temps de Haskell. La meilleure façon de représenter une HList aujourd'hui est probablement d'utiliser des GADTs et des DataKinds.

data HList ls where
  Nil  :: HList '[]
  Cons :: x -> HList xs -> HList (x ': xs)

Cela donne une imbrication canonique, et vous permet d'écrire des fonctions qui fonctionnent pour toutes les instances de ce type. Vous pourriez implémenter votre méthode multi zipWith en utilisant les mêmes techniques que celles utilisées dans printf . Un casse-tête plus intéressant consiste à générer les lentilles appropriées pour ce type (conseil : utilisez les naturelles de niveau type et les familles de types pour l'indexation).

J'ai envisagé d'écrire une bibliothèque de type HList utilisant des tableaux et des unsafeCoerce sous le capot pour obtenir des performances similaires à celles des tuple tout en restant dans une interface générique. Je ne l'ai pas fait, mais cela ne devrait pas être trop difficile.

EDIT : plus j'y pense, plus je suis enclin à bricoler quelque chose quand j'aurai le temps. Le problème de copie répétée mentionné par Andreas Rossberg peut probablement être éliminé en utilisant la fusion de flux ou des techniques similaires.

Answer 2

Le principal problème que cela pose en Haskell serait qu'un tuple imbriqué permet des valeurs supplémentaires, par paresse. Par exemple, le type (a,(b,()) est habité par tous (x,_|_) o (x,(y,_|_)) ce qui n'est pas le cas pour les tuples plats. L'existence de ces valeurs n'est pas seulement gênante sur le plan sémantique, elle rendrait également les tuples beaucoup plus difficiles à optimiser.

Dans un langage strict, cependant, votre suggestion est effectivement une possibilité. Mais elle introduit toujours un problème de performance : les implémentations voudront toujours aplatir les tuples. Par conséquent, dans les cas où vous les construisez ou les déconstruisez réellement de manière inductive, elles devront effectuer de nombreuses copies répétées. Lorsque vous utilisez des tuples de très grande taille, cela peut poser un problème.