Как мне указать конкретные реализации для класса типов?

Question

У меня есть следующий простой модуль Haskell, который определяет класс типов Queue, для которого должны быть определены операции push, pop и top, а также конструктор для пустой очереди и функция, которая проверяетесли очередь пустаЗатем он предоставляет две реализации: очередь «первым пришел - первым обслужен» и стек.

Код работает.Однако кажется, что я повторяюсь без необходимости.В частности, единственной операцией, которая отличается между очередью и стеком, является операция push (помещаем ли мы новые объекты в начало или конец списка?).Кажется, что должен быть какой-то способ определения общих операций в определении класса типов.Возможно ли это на самом деле?

module Queue (
    Queue,
    FifoQueue(FifoQueue),
    Stack(Stack),
    empty,
    isEmpty,
    push,
    pop,
    top
) where

class Queue q where
    empty :: q a
    isEmpty :: q a -> Bool
    push :: a -> q a -> q a
    pop :: q a -> (a, q a)
    top :: q a -> a

data Stack a = Stack [a] deriving (Show, Eq)

instance Queue Stack where
    empty = Stack []
    isEmpty (Stack xs) = null xs
    push x (Stack xs) = Stack (x:xs)
    pop (Stack xs) = (head xs, Stack (tail xs))
    top (Stack xs) = head xs

data FifoQueue a = FifoQueue [a] deriving (Show, Eq)

instance Queue FifoQueue where
    empty = FifoQueue []
    isEmpty (FifoQueue xs) = null xs
    push x (FifoQueue xs) = FifoQueue (xs ++ [x])
    pop (FifoQueue xs) = (head xs, FifoQueue (tail xs))
    top (FifoQueue xs) = head xs

Answer 1

Ну, есть небольшое количество дублирования, но давайте избавимся от него.

Ключ в том, что мы можем предоставить значения по умолчанию Queue, учитывая, что мы знаем, как превратить его в список, кроме того, мы предоставляем очередь, которую мы можем составить список. Поэтому мы просто добавляем две функции к вашему определению, toList и fromList, и проверяем, что либо предоставление toList и fromList, либо предоставление других функций дают полное определение.

import Control.Arrow

class Queue q where
    empty :: q a
    empty = fromList []
    isEmpty :: q a -> Bool
    isEmpty = null . toList
    push :: a -> q a -> q a
    push a b = fromList (a : toList b)
    pop :: q a -> (a, q a)
    pop qs = (head . toList $ qs,fromList . tail . toList $ qs)
    top :: q a -> a
    top = head . toList
    toList :: q a -> [a]
    toList queue = if isEmpty queue then [] 
                   else uncurry (:) . second toList . pop $ queue
    fromList :: [a] -> q a
    fromList = foldr push empty

Как видите, любая реализация очереди должна обеспечивать toList и fromList или другие функции и, следовательно, реализации ваших двух очередей становятся следующими:

data Stack a = Stack [a] deriving (Show, Eq)

instance Queue Stack where
    toList (Stack a) = a
    fromList a = Stack a

data FifoQueue a = FifoQueue [a] deriving (Show, Eq)

instance Queue FifoQueue where
    toList (FifoQueue a) = a
    fromList a = FifoQueue a
    push x (FifoQueue xs) = FifoQueue (xs ++ [x])

Answer 2

Кажется, что "дублирование", о котором вы беспокоитесь, является сходством в некоторых реализациях:

instance Queue Stack where
    empty = Stack []
    isEmpty (Stack xs) = null xs
    ...

instance Queue FifoQueue where
    empty = FifoQueue []
    isEmpty (FifoQueue xs) = null xs
    ...

Но, к сожалению, просто нет способа объединить части этих двух экземпляров. Вы можете удалить класс типов и просто иметь Stack и FifoQueue двумя разными конструкторами одного типа. Отсюда в основном применяются решения HaskellElephant (замена toList на lst).

data Queue a = Stack { lst :: [a] }
             | FifoQueue { lst :: [a] }
             deriving (Eq, Show)

-- "empty" obviously cannot be preserved as it was
-- you need to specify whether you want an empty Stack or empty FifoQueue
emptyS = Stack []
emptyQ = FifoQueue []

-- but some functions are the same either way
isEmpty = null . lst
top queue = head . lst

-- other functions behave *mostly* the same for both cases...
pop queue = (top queue, liftQ tail queue)

-- ...they just need a little helper to abstract over the slight difference
liftQ :: ([a] -> [b]) -> Queue a -> Queue b
liftQ f (Stack xs) = Stack (f xs)
liftQ f (FifoQueue xs) = FifoQueue (f xs)

-- then for functions where the implementation is completely different,
-- you just pattern match
push x (Stack xs) = Stack (x:xs)
push x (FifoQueue xs) = FifoQueue (xs ++ [x]) -- this is slow, by the way

Недостатком этого является, конечно, то, что вместо открытого класса типов ваш модуль теперь предоставляет закрытый ADT.

---

Там есть какая-то золотая середина, хотя. Вроде, как бы, что-то вроде. Рассмотрим этот альтернативный подход:

data QueueImpl q a = QueueImpl { _empty :: q a
                               , _isEmpty :: q a -> Bool
                               , _top :: q a -> a
                               , _pop :: q a -> (a, q a)
                               , _push :: a -> q a -> q a
                               }

-- partially applied constructor!
shared :: (a -> [a] -> [a]) -> QueueImpl [] a
shared = QueueImpl empty' isEmpty' top' pop'
  where empty' = []
        isEmpty' = null
        top' = head
        pop' (x:xs) = (x, xs)

stack :: QueueImpl [] a
stack = shared push'
  where push' = (:)

fifoQueue :: QueueImpl [] a
fifoQueue = shared push'
  where push' x = (++[x])

Превратив класс типов в тип данных, мы можем частично применить конструктор, таким образом разделяя реализации для большинства методов. Подвох в том, что у нас нет доступа к функциям, которые полиморфны так же, как и раньше. Для доступа к методам нам нужно сделать top stack или top fifoQueue. Это приводит к некоторым интересным изменениям в разработке «полиморфных» функций: поскольку мы усовершенствовали класс типов, нам нужно явно передать реализацию любым составным функциям:

-- if you haven't figured out by now, "impl" is short for "implementation"
_push3 :: QueueImpl [] a -> a -> [a] -> [a]
_push3 impl x = push x . push x . push x
  where push = _push impl

-- _push3 as implemented by a stack:
sPush3 :: a -> [a] -> [a]
sPush3 = _push3 stack

Обратите внимание, что здесь мы проигрываем в некоторой безопасности типов; представление как стека, так и FifoQueue отображается в виде необработанного списка. Там могут быть некоторые хакеры нового типа, которые могут сделать это немного безопаснее. Вывод таков: у каждого подхода есть свои преимущества и недостатки. Классы типов - довольно хорошая идея, но не путайте их с Серебряной пулей; знать о других опциях, таких как эти.

Answer 3

Вы можете сбрить две реализации для top, если добавите реализации по умолчанию в классе типа Queue:

top = fst . pop

, но, кроме того, я не думаю, что есть много делВот.В любом случае дублирования не так много.