2010-06-08 11 views
6

¿Por qué Haskell no puede resolver el tipo de [[]] (Una lista de listas)?
¿Por qué no es simplemente * -> *, ya que puedo darle un tipo como Int, y obtener [[Int]], que es de tipo *.¿Por qué GHCi no puede resolver el tipo de [[]]?

+4

es como preguntar por qué GHC no puede determinar el tipo del valor 'sqr t sqrt' aunque 'sqrt' en sí mismo es' Doble -> Doble' – newacct

+1

: t sqrt sqrt funciona bien en GHCI aunque – Squidly

+8

Es porque 'sqrt' es polimórfico. Una mejor analogía es: t no no. – sdcvvc

Respuesta

8

creo que es el mismo que con Maybe Maybe, aunque en este último caso la razón es quizás más clara: el "exterior" de tipo constructor espera ser aprobado un tipo de clase *, pero ve un constructor de tipo de tipo * -> * (la "interno" Maybe/[]) y se queja. Si estoy en lo correcto, esto no es realmente un problema con la funcionalidad :kind de GHCi, sino más bien con la búsqueda de la sintaxis correcta para expresar la composición de constructores de tipo de mayor nivel.

Como solución, algo así como

:kind forall a. [[a]] 
:kind forall a. Maybe (Maybe a) 

se puede utilizar (con la extensión lenguaje apropiado encendido - ExistentialQuantification, creo - para permitir la sintaxis forall).

+1

Este hilo de Haskell Café podría ser relevante: http://www.mail-archive.com/[email protected]/msg08530.html - Composición de Type Constructors. –

+0

No creo que el tipo existencial fuera intencionado (que es '*'). Una manera fácil, pero fuera de GHCi, es 'tipo a = [[a]]' (que es '* -> *'). – sdcvvc

+1

@sdcvvc que es un tipo polimórfico universalmente cuantificado (no es existencial). –

4

Si desugar [[]] como [] [], entonces es obvio que es poco compatible porque [] :: * -> *.

Si realmente deseaba una "lista de listas", debe componer dos tipos de constructores del tipo * -> *. No se puede hacer eso sin una pequeña repetición porque Haskell no tiene una lambda de nivel de tipo. Puede hacer esto sin embargo:

newtype Comp f g a = Comp { unComp :: f (g a) } 

Ahora se puede escribir:

type ListList = Comp [] [] 

Y escribir funciones de usarlo:

f :: ListList Int -> ListList Int 
f = Comp . map (map (+1)) . unComp 

composición Functor como esto tiene aplicaciones en diversas áreas, en particular Swierstra de "Data types a la carte"

Cuestiones relacionadas