11
votes

HASK est-il localement petit?

La catégorie HASK de HASKELL est-elle un exemple de la catégorie locale?

http://ncatlab.org/nlab/show/locally+Small+Category < / a>

Peut-être pas .. hask comme cpo http://www.cs.gunma-u.ac. JP / ~ HAMANA / PAPERS / CPO.PDF

The Haskellwiki, http://www.hakell.org/hakellwiki/hask a très Bonne information, montrant que HASK n'est pas fermé cartésien.

haskell

4 commentaires

Haskell a cette chose inconfortable "polymorphisme" qui ruine la plupart des propriétés de taille. Donc, ma supposition est "non" - mais je ne suis pas assez d'un expert pour faire cela dans un véritable contre-exemple!

La raison pour laquelle je demande est due à une conversation sur REDDIT traitant de l'interprétation correcte dans HASKELLL DES FUNCTEURS N-ARY. lien

Mathoverflow.net/Questtions/24540/... Cette question peut être liée.

Le jeu de catégories n'est pas petit.

3 Réponses :

1
votes

Les objets HASK sont des types de haskell qui sont de manière importante. Les flèches HASK sont des fonctions de haskell qui sont également de manière importante. Donc, HASK n'est pas seulement petit localement, HASK est faible.

Carte (OB (HASK)) = Carte (HOM (HASK)) = Carte (N)

Plus de détails sur HASK ici:

http://yannesposito.com/scratch/fr/blog/category -Le théorique-présentation /

2 commentaires

Euh ... ce n'est pas comme ça que ça marche. Le fait que tous les programmes soient finis ne rend pas l'univers des programmes dénombrables. Paradoxe de Skolem ici.

@Philipjf, j'ai construit un modèle obéissant cela comme une réponse. Je voudrais vos commentaires sur l'endroit où j'ai mal tourné.

2
votes

Qu'est-ce que HASK? Si cela inclut toutes les "fonctions" de HASKELLL "Fonctions" comme morphisme, il n'est donc définitivement pas xxx

le "hom-set" de gros -> gros contient tout le calcul de la Lambda non typée! Je doute qu'il soit localement petit, même si vous n'autorisez que des fonctions de terminaison - je pense qu'il n'y a pas de modèles théoriques définis de système-f.

EDIT: Sept ans plus tard, je ne peux pas faire de la tête ou de la queue de ce que J'essayais de dire ici. HASK n'a pas de modèles théoriques définis, dans le sens des modèles qui interprètent les types de fonctions comme des ensembles complètes de fonctions. C'est vrai, mais je ne sais pas de quoi cela a à voir avec la question. Il n'est pas vraiment clair ce que "HASK" est, mais une réponse raisonnable me semble avoir de petits homsets (c'est-à-dire qu'il est localement petit).

L'étrangeté de Ma réponse de nombreuses années passée est légèrement embarrassante pour moi. Je suis sûr que je voulais dire quelque chose de très perspicace - je n'ai aucune idée de ce que c'était, et comme formulé cela semble plutôt faux .



                                                                    
                                    
                                    
                                        6 commentaires
                                        
                                                                                            
                                                    Trouvé un commentaire ici, [link] ( Golem.ph.utexas .edu / Catégorie / 2011/01 / ... ) sur la construction d'un modèle théorique de System-F                                                
                                                
                                                                                            
                                                    @edase qui est intéressant. Je pense que je me souvenais de ce  Hal.inria. FR / DOCS / 00 / 07/62/61 / PDF / RR-0296.PDF  papier                                                
                                                
                                                                                            
                                                    Votre source peut être plus autorisée que la mienne. Dan Doel fait quelques problèmes dans l'effort de modélisation. "Parce que, à quoi diable est une famille uniforme de fonctions théoriques définies?"                                                
                                                
                                                                                            
                                                    Est-il en fait le cas que s'il n'y a pas de modèle théorique de série, la collection de tous termes ne peut pas être un ensemble? Ce n'est pas évident pour moi; La propriété d'être un  modèle  impose une plus grande structure que la propriété de simplement avoir tous les termes.                                                

                                                
                                                                                            
                                                    @Danielwagner J'ai répondu à cette question il y a 7 ans, et honnêtement, je ne suis pas sûr de ce que je voulais dire ici. Les catégories de COP sont évidemment petites localement. Comme c'est le modèle de terme. Ce que vous ne pouvez pas avoir est un modèle (non trivial) qui interprète les types de fonctions en tant qu'ensemble complet de fonctions, car il n'y a pas de solutions non triviales à t = t ^ t dans le jeu.                                                
                                                
                                                                                            
                                                    Je suis à mi-chemin enclin à supprimer cette réponse juste parce que, si je ne comprends pas ce que je disais, je ne vois pas comment il est plausible que quelqu'un d'autre puisse


                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Surtout @Phillipjf, voici un essai. Je n'essaie pas de faire le modèle de hask le plus précis ou élégant, j'essaie simplement de faire  un modèle . Critique, s'il vous plaît. 

 Si A est un type HASKELLL, définissez une valeur  de type A  dans HASK pour être une classe d'équivalence de HASKELL TYPEE bien typé de type A (Strings x pour lequel  x :: Un  serait accepté par le vérificateur de type), l'égalité de l'extension Modulo. C'est-à-dire que deux termes sont considérés comme égaux si elles s'étendent à la même forme normale (éventuellement infinie) et deux termes qui n'ont pas de HNF sont également égaux. Le fait que ce ne soit pas décidable n'est pas pertinent, nous n'avons besoin que d'indiquer ces conditions, théoriquement, que j'ai peu de doute que nous pouvons faire. 

 laisser les objets de  hask  be types de haskell (types primitifs et types définis par l'utilisateur; nous supposerons que tous les types définissables par l'utilisateur existent et ont des noms distincts. Les définitions de type défini par l'utilisateur sont le code source. , alors ils sont comptables. Nommez-les  d0 ,  d1 , ... selon ce comptage.). 

 Laissez les morphismes  a -> b  valeurs de type  a -> b  

 Laissez l'identité sur  a  la classe d'équivalence de  ID :: A -> A  et la composition de  g  et < Code> f  Soyez la classe d'équivalence de  g. f . 

 L'ensemble de toutes les valeurs est un ensemble dénombrable, car les termes ne sont que des chaînes sur un alphabet fini. Donc, ce modèle de  hask  est petit. 

 est-ce faux?                                 


                                                                    
                                    
                                    
                                        6 commentaires
                                        
                                                                                            
                                                    C'est cette chose qui arrive toujours. Étant donné que la syntaxe est finie (pour chaque logique), des choses comme celles-ci devraient simplement fonctionner. Le problème est que vous rencontrez du paradoxe. Comme, considérez l'ensemble de l'ensemble de l'ensemble  NAT -> bool . Supposons que vous ayez une fonction  F :: NAT -> NAT -> BOOL  qui a généré chaque programme HASKELL correspondant à un membre de cet ensemble hom-homologué (permettant la répétition). Ensuite, nous pourrions définir  g n = pas (f n n)  qui n'est clairement pas quelque chose que cela génère. C'est pourquoi le paradoxe de Skolem est un paradoxe! Voir  existentielletype.wordpress.com/2013/01/ 28 / ...  pour des idées similaires                                                

                                                
                                                                                            
                                                    @Philipjf, il n'est pas calculable pour  F  pour générer toutes les fonctions totales et uniquement les fonctions totales, il doit donc générer des programmes partiels, c'est-à-dire certains N telles que  fnn = _ | _  . La chose est,  _ | _  est un point fixe de  non , donc  non (fnn)  "n'est clairement pas quelque chose que cela génère" est faux . Je conviens que c'est un territoire semblant subtil et paradoxal s'il n'est pas approché de rigueur (et cela fait toujours exploser mon cerveau de temps en temps). J'ai écrit un koan à ce sujet: cf.  Lukepalmer.wordpress.com/2012/01/26/communauté-comptabilité - a>                                                

                                                
                                                                                            
                                                     Link  Une interprétation de Luke Palmer en résultat de Haskell Cafe , par Ryan Ingram                                                
                                                
                                                                                            
                                                    Je pense que cela se résume si la loi de l'église est le modèle de hask = PCF de Luqui. Wheras La loi de l'église étant fausse peut impliquer quelque chose d'autre entièrement. "FFR;" Fondations pratiques de Langues pratiques pour les langages de programmation "Robert Harper 9, 10. Et les poteaux de blogs pertinents                                                
                                                
                                                                                            
                                                    Êtes-vous simplement riffs maintenant, ou cela a-t-il des portes sur la question initiale?                                                
                                                
                                                                                            
                                                    Ya viens de me riffler, travaillant à travers des choses, supprimera les commentaires plus tard.

Articles qui pourrait vous intéresser : Qu'est-ce que l'homomorphisme monoïde exactement? Haskell max à partir de l'arbre de recherche binaire paramétré Comment puis-je additionner tous les 2 éléments d'une liste? Aucun support trouvé pour filename.hs. Procéder avec un berceau implicite