Un "contro" in Haskell che visualizza come la sua controparte Schema

Question

Come esercizio, sto implementando in Haskell un'operazione "contro" che forma una coppia da due valori di qualsiasi tipo. Attuare il tipo di dati necessario è abbastanza facile:

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> 

ma ispirata this thread, voglio fare le coppie risultanti stampare fuori come liste regime sarebbe - tra cui la "lista improprio" infame (1 2 3 4.). La mia implementazione (vedi sotto) sta lavorando per Char di:

*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') 

Non funziona così bene per Int di (o qualsiasi altro tipo di dati). Quindi la mia domanda è: come posso fare questo lavoro per altri tipi di dati? vale a dire, voglio farlo funzionare in questo modo:

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

mio attuale implementazione completa segue:

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 _ = "" 

Answer 1

Ecco un'opzione. In primo luogo, abilitare queste estensioni inserendo questa linea nella parte superiore del file:

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

Avanti, rimuovere il ShowPair istanze per Char e Int.

Ora aggiungere un'istanza ShowPair per nulla con Show:

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

Questo assicura ora che qualsiasi tipo a che è un'istanza di Show è anche un'istanza ShowPair quando è dimostrata anteponendo un . alla sua forma di corda normale. Tuttavia, se un tipo ha un'istanza ShowPair più specifica (ad esempio Nil), Haskell lo utilizzerà.

Questo non fa parte dello standard Haskell, quindi è necessario abilitare le tre estensioni della lingua. Guarda How to write an instance for all types in another type class? per ulteriori informazioni su perché hai bisogno delle estensioni.

Answer 2

Ben nei commenti alla domanda menziona il tipo di coppia nativa, che userò in questa risposta. Sostituirò anche il tuo Nil con l'unità Haskell tipo ().

Questo è un po 'fuori da quello che stai chiedendo, ma penso che valga la pena di dire. In Haskell è difficile acquisire la nozione di "elenco" in Scheme a meno che tu non "imbrogli" e utilizzi un'estensione come Data.Dynamic. Questo perché dal punto di vista di Haskell "puro", non esteso, è difficile se non impossibile assegnare tutti gli elenchi Scheme dello stesso tipo. Ciò significa che, sebbene Scheme ti permetta di scrivere funzioni che prendono qualsiasi lista, corretta o impropria, avrai difficoltà a fare lo stesso in Haskell (e per una buona ragione, "liste" impropri non dovrebbero probabilmente esistere comunque).

Quindi, ad esempio, in pratica si è scelto di utilizzare (a, b) come tipo di coppie simili a Schema.Ora supponiamo di avere queste liste Schema:

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

Ecco una semplice traduzione in termini di coppie Haskell, che corrisponde al modo in cui si sta facendo:

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 cosa fondamentale è che in Scheme si può facilmente scrivere una funzione che spazia su tutte le liste:

(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))))) 

In questa traduzione Haskell, non si può fare così facilmente a tutti, perché "liste" di diversa lunghezza hanno tip diverso es. E c'è di peggio se si considera la differenza tra reverse (che prende una lista di lunghezza n e produce una lista di lunghezza n) e filter (che prende una lista di lunghezza n e produce una lista di lunghezza m ≤ n tale che m può essere conosciuto solo in fase di esecuzione).