Haskell - anidado listas vacías - Excelente biblioteca

Hola Haskellers y Haskellettes,Haskell - anidado listas vacías

al leer http://learnyouahaskell.com/ un amigo mío se acercó con un problema:

¿Es posible en Haskell escribir una función recursiva que da verdadero si todos los sub -sub -_- sublistas están vacías. Mi primera suposición fue - debería ser - pero tengo un gran problema simplemente escribiendo la anotación tipo.

Intentó algo así como

nullRec l = if null l 
       then True 
       else if [] `elem` l 
        then nullRec (head [l]) && nullRec (tail l) 
        else False

que es - no funciona - :-)

me encontré con algo como

plegable con concat - para llegar aa sola lista larga
(me da problemas para implementar)
o hacer un tipo de datos arborescente infinito - y hacer esto desde la lista
(no se han aplicado todavía)

pero este último sonar un poco como una exageración para este problema. lo que es sus ideas - en un domingo soleado como este ;-)

Gracias de antemano

como una reacción a todos los comentarios - este mal estilo que me gustaría añadir esto se solo un experimento !
¡No intente esto en casa! ;-)

Fuente

2011-07-10 epsilonhalbe

Piense en el tipo de función que debería ser (si la implementa en listas normales). – yatima2975

ya lo pensé - debería ser algo infinito [[... [a] ...]] pero no es posible escribirlo en haskell - por eso surgió el segundo enfoque. Pero hay una forma más fácil de hacer esto. Además mi cerebro es un poco lento ya que estoy enfermo hoy. – epsilonhalbe

Enfermo o no, ¡estás en el camino correcto! Es bastante fácil escribir una familia de funciones 'nullRec2 :: [[a]] -> Bool',' nullRec3 :: [[[a]]] -> Bool' y así sucesivamente (¡prueba un par!), Pero tú no puede hacer que se ajusten fácilmente a una sola firma de tipo. O necesita un tipo de árbol como 'data Tree a = Branch [Tree a] | Nodo a' o tal vez hay algo posible con las clases de tipos (aún no he pensado mucho sobre este enfoque). – yatima2975

¿Qué tal una clase de tipo?

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-} 

class NullRec a where 
    nullRec :: a -> Bool 

instance NullRec a => NullRec [a] where 
    nullRec [] = True 
    nullRec ls = all nullRec ls 

instance NullRec a where 
    nullRec _ = False 

main = print . nullRec $ ([[[[()]]]] :: [[[[()]]]])

Fuente

2011-07-10 15:34:52 fuz

Más precisamente, está utilizando no solo una clase de tipo sino también la extensión GHC [OverlappingInstances] (http://www.haskell.org/ghc/docs/7.0.4/html/users_guide/type-class-extensions.html # instancia-superposición). Sin esta extensión, incluso el uso de una clase de tipo no puede lograr lo que se requiere en la pregunta. Esto sugiere fuertemente que si alguien tiene que implementar esto (que no sea como un experimento), el programa probablemente no está diseñado de la manera correcta. –

Esto no es posible usando el polimorfismo paramétrico solamente, debido a lo siguiente.

Considere estos valores:

x = [8] :: [Int] 
y = [3.0] :: [Double] 
z = [[]] :: [[Int]]

Obviamente, usted quiere que su función funcione tanto con x y y, de ahí su tipo debe ser null1 :: [a] -> Bool. (¿Puede alguien me ayude a hacer este argumento aspecto formal? ¿Cómo puedo demostrar que esta es la única sin contexto tipo más específico unificables con [Int] -> Bool y [Double] -> Bool? ¿Hay un nombre para esa relación entre los tipos?)

Ahora , si tiene este tipo, entonces null1 z será igual a null1 x porque difieren solo en los valores de los elementos de la lista, que se abstraen de. (Ni siquiera cerca de una prueba formal de nuevo :()

lo que quiere para z es null2 :: [[a]] -> Bool, que será diferente en el comportamiento, y dando así null1 y null2 el mismo nombre requerirá una sobrecarga.(vea la respuesta de FUZxxl)

Fuente

2011-07-10 16:03:25 Rotsor

Encuentro ese argumento bastante convincente. – luqui

Me siento como 'null1. (: []) :: a -> Bool' nos acerca a la prueba formal, pero todavía no sé cómo hacer el último paso (mostrando que 'a -> Bool' es lo mismo que' Bool'). – Rotsor

Es un tipo de teorema libre al revés, pero el límite inferior más grande de 'Int' y' Double' (en el enrejado de tipos libres de contexto de Haskell, con substición como la relación) es 'a', ya que no se puede sustituye las variables de tipo en las dos (¡no hay ninguna!) y termina con el mismo tipo. ¿O estoy confundiendo mis direcciones arriba y abajo? – yatima2975

Haskell - anidado listas vacías

Respuesta

Cuestiones relacionadas