Haskell中的'cons'与其计划对应部分

Question

作为一个练习，我在Haskell中实现了一个'cons'操作，它从两个任意类型的值构成一对。实施所需的数据类型是很容易的：

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> 

但灵感this thread，我想使所产生的对打印出像Scheme列表会 - 包括臭名昭著的“不正当名单”（1 2 3 4）。我的实现（见下文）正在为夏亚：

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

这不是诚信部（或任何其它数据类型）的工作这么好。所以我的问题是：我怎样才能使这项工作的其他数据类型？即，我希望它是这样工作的：

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

我目前的全面实施如下：

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

这里是一个选项。首先，放上这行你的文件的顶部启用这些扩展：

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

接下来，删除您ShowPair实例为Char和Int。

现在添加ShowPair实例任何与Show：

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

现在，这确保了任何类型a这是Show的实例也是在那里被前面加上一个.所示的ShowPair实例其正常字符串形式。但是，如果某个类型具有更具体的ShowPair实例（例如Nil），则Haskell将使用该实例。

这不是标准Haskell的一部分，所以您需要启用三种语言扩展。看How to write an instance for all types in another type class?关于的更多信息为什么你需要扩展。

Answer 2

Ben在问题的评论中提到了本机对类型，我将在此答案中使用它。我也将用您的Nil替代Haskell单元类型()。

这有点超出你所问的范围，但我认为这值得说。除非你“欺骗”并使用像Data.Dynamic这样的扩展名，否则Haskell难以捕获Scheme中“列表”的概念。这是因为从“纯粹”的未扩展Haskell的角度来看，即使不是不可能将所有Scheme列表分配为相同的类型也很困难。这意味着，虽然Scheme允许你编写任何列表，适当或不适当的函数，但是在Haskell中做同样的事情会很困难（并且出于很好的理由;不正确的“列表”应该可能不存在）。

因此，例如，您基本上已选择使用(a, b)作为Scheme-like对的类型。现在假设我们有这些计划清单：

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

这里有一个简单的翻译在Haskell对而言，其对应的方式你这样做：

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

关键的一点是，在方案你可以很容易地写在范围内的所有列表的功能：

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

在此哈斯克尔翻译，你不能这样做，很容易在所有的，因为不同长度的“名单”有不同的典型ES。而且当你考虑reverse之间的差别（这需要长度ň的列表，并产生一个长度ň的列表）和filter（这需要长度ň的列表，并产生一个长度列表变得更糟m≤n这样m只能在运行时才知道）。