«Минусы» в Haskell, которые отображаются как его аналог Scheme

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> 

, но вдохновленный этой цепочкой , я хочу, чтобы результирующие пары распечатывались так же, как и списки схем - включая печально известный "неправильный список""(1 2 3. 4).Моя реализация (см. Ниже) работает для 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')

Она не работает так хорошо для Int (или любого другого типа данных).Итак, мой вопрос: как я могу заставить это работать для других типов данных?т.е. я хочу, чтобы это работало так:

*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, поэтому вам необходимо включить три языковых расширения. Посмотрите на Как написать экземпляр для всех типов в другом классе типов? для получения дополнительной информации о , почему вам нужны расширения.

Answer 2

Бен в комментариях к вопросу упоминает родной тип пары, который я собираюсь использовать в этом ответе. Я также собираюсь заменить ваш Nil типом блока Haskell ().

Это немного за пределами того, что вы спрашиваете, но я думаю, что стоит сказать. В Хаскеле трудно поймать понятие «список» в Схеме, если вы не «обманываете» и не используете расширение типа Data.Dynamic. Это связано с тем, что с точки зрения «чистого», расширенного Haskell трудно, если не невозможно, назначить все списки Scheme одного типа. Это означает, что, хотя Scheme позволяет вам писать функции, которые берут любой список, правильный или неправильный, вам будет трудно сделать то же самое в Haskell (и по понятной причине; неправильные «списки», вероятно, в любом случае не должны существовать).

Так, например, вы в основном решили использовать (a, b) в качестве типа схемоподобных пар. Теперь предположим, что у нас есть эти списки схем:

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

Ключевым моментом является то, что в Scheme вы можете легко написать функцию, которая охватывает все списки:

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

В этом переводе на Haskell вы вообще не можете сделать это легко, потому что «списки» разной длины имеют разные типы. И становится еще хуже, если учесть разницу между reverse (который принимает список длиной n и создает список длиной n ) и filter (который принимает список длиной n и создает список длиной m ≤ n , так что m может быть известен только во время выполнения).