2012-01-31 4 views
5

Como ejercicio, estoy implementando en Haskell una operación 'contra' que forma un par a partir de dos valores de cualquier tipo. Implementar el tipo de datos que se necesita es bastante fácil:A 'contras' en Haskell que se muestra como su contraparte Scheme

data Nil = Nil deriving (Eq) 
data Pair a b = Cons a b deriving (Eq) 

car (Cons x _) = x 
cdr (Cons _ y) = y 

caar = car . car 
cdar = cdr . car 
cadr = car . cdr 
cddr = cdr . cdr 

*Main> cddr (Cons 55 (Cons (1,2,3,4) "hello, world!")) 
"hello, world!" 
*Main> 

pero inspirado por this thread, quiero hacer los pares resultantes imprimen como listas régimen podrían - incluyendo la "lista impropia" infame (1 2 3 4.). Mi aplicación (véase más adelante) está trabajando para Char:

*Main> Cons 'a' (Cons 'b' (Cons 'c' Nil)) 
('a' 'b' 'c') 
*Main> Cons 'a' (Cons 'b' 'c') 
('a' 'b' . 'c') 
*Main> Cons (Cons 'a' 'b')(Cons 'c' (Cons 'd' Nil)) 
(('a' . 'b') 'c' 'd') 

No está funcionando tan bien para Int (o de cualquier otro tipo de datos). Entonces mi pregunta es: ¿cómo puedo hacer que esto funcione para otros tipos de datos? es decir, yo quiero que funcione de esta manera:

*Main> Cons 5 (Cons "hello" (Cons False Nil)) 
(5 "hello" False) 

Mi aplicación plena corriente sigue:

data Nil = Nil deriving (Eq) 
data Pair a b = Cons a b deriving (Eq) 

car (Cons x _) = x 
cdr (Cons _ y) = y 

caar = car . car 
cdar = cdr . car 
cadr = car . cdr 
cddr = cdr . cdr 

instance Show Nil where show _ = "()" 

class ShowPair a where 
    showRight::a->String 

instance (Show a, ShowPair a, ShowPair b)=>Show (Pair a b) where 
    show (Cons car cdr) = "(" ++ (show car) ++ (showRight cdr) ++ ")" 

instance (Show a, ShowPair a, ShowPair b)=>ShowPair (Pair a b) where 
    showRight (Cons car cdr) = " " ++ (show car) ++ (showRight cdr) 

instance ShowPair Char where 
    showRight x = " . " ++ show x 

instance ShowPair Int where 
    showRight x = " . " ++ show x 

instance ShowPair Nil where 
    showRight _ = "" 
+1

Haskell viene con una operación integrada que puede formar un par a partir de dos valores de cualquier tipo: '(a, b)'. Se puede deletrear '(,) a b' si quieres poder usarlo como lo harías con una función. '()' luego toma la parte de su 'Nil'. 'auto' se escribe' fst', y 'cdr' es' snd'. – Ben

+0

@Ben Entendido - Sabía que era probable que estuviera haciendo una reinvención de rueda aquí. ¿Hay alguna manera de obtener pares producidos con (,) para imprimir como listas de esquemas? – gcbenison

Respuesta

6

Aquí hay una opción. En primer lugar, habilitar estas extensiones al poner esta línea en la parte superior de su archivo:

{-# LANGUAGE FlexibleInstances, OverlappingInstances, UndecidableInstances#-} 

A continuación, eliminar los casos de ShowPairChar y Int.

Ahora añadir una instancia ShowPair para nada con Show:

instance Show a => ShowPair a where showRight = (" . " ++) . show 

Esto ahora se asegura de que cualquier tipo a que es una instancia de Show es también una instancia de ShowPair donde se demuestra anteponiendo un . a su forma de cuerda normal. Sin embargo, si un tipo tiene una instancia más específica de ShowPair (por ejemplo, Nil), Haskell lo usará en su lugar.

Esto no es parte de Haskell estándar, por lo que debe habilitar las tres extensiones de idioma. Consulte How to write an instance for all types in another type class? para obtener más información sobre por qué necesita las extensiones.

+0

Gracias por esta gran explicación y el enlace a la publicación relacionada. – gcbenison

2

Ben en los comentarios a la pregunta menciona el tipo de par nativo, que voy a utilizar en esta respuesta. También voy a sustituir su Nil con la unidad Haskell tipo ().

Esto está un poco fuera de lo que estás preguntando, pero creo que vale la pena decirlo. En Haskell es difícil capturar la noción de "lista" en Scheme a menos que "haga trampa" y use una extensión como Data.Dynamic. Esto se debe a que, desde el punto de vista de Haskell "puro" y no extendido, es difícil, si no imposible, asignar todas las listas de Esquemas del mismo tipo. Esto significa que, si bien Scheme le permite escribir funciones que toman cualquier lista, adecuada o inadecuada, tendrá dificultades para hacer lo mismo en Haskell (y por una buena razón, las "listas" incorrectas probablemente no deberían existir de todos modos).

Así que, por ejemplo, básicamente ha elegido usar (a, b) como el tipo de pares similares a Scheme.Ahora supongamos que tenemos estas listas Scheme:

(define zero '()) 
(define one '(1)) 
(define two '(1 2)) 
(define three '(1 2 3)) 
(define four '(1 2 3 4)) 

He aquí una traducción simple en términos de pares de Haskell, que corresponde a la forma en que lo está haciendo:

zero ::() 
zero =() 

one :: (Integer,()) 
one = (1,()) 

two :: (Integer, (Integer,())) 
two = (1, (2,())) 

three :: (Integer, (Integer, (Integer,()))) 
three = (1, (2, (3,()))) 

four :: (Integer, (Integer, (Integer, (Integer,())))) 
four = (1, (2, (3, (4,())))) 

La clave es que en el Esquema usted puede escribir una función que se extiende sobre todas las listas:

(define (reverse list) 
(foldl cons '() list)) 

(define (filter pred? list) 
    (foldr (lambda (elem rest) 
      (if (pred? elem) 
       (cons elem rest) 
       rest)) 
     '() 
     list)) 

(define (foldl fn init list) 
    (if (null? list) 
     init 
     (foldl fn (fn (car list) init) (cdr list)))) 

(define (foldr fn init list) 
    (if (null? list) 
     init 
     (fn (car list) 
      (foldr fn init (cdr list))))) 

en esta traducción Haskell, no se puede hacer tan fácilmente en absoluto, porque "listas" de diferentes longitudes tienen diferentes tip es. Y que se agrava si tenemos en cuenta la diferencia entre reverse (que tiene una lista de longitud n y produce una lista de longitud n) y filter (que tiene una lista de longitud n y produce una lista de longitud mn tal que m solo se puede conocer en tiempo de ejecución).

+0

Hmm, sí - Veo cómo sería incómodo intentar implementar 'filter' y' reverse' en Haskell para una "lista de elementos", aunque cadr, cddr etc. son bastante fáciles – gcbenison

Cuestiones relacionadas