Как смоделировать эту рекурсивную структуру в Haskell? - PullRequest
Новая
       48

Как смоделировать эту рекурсивную структуру в Haskell?

2 голосов
/ 11 февраля 2020

Я пытаюсь смоделировать "атомы и списки" kdb / q через систему типа Haskell.

В kdb / q все данные построены из атомов. Атом - это неприводимое значение определенного типа данных c. Int, boolean и char являются примерами атомов. Списки - это упорядоченные коллекции, построенные из атомов. Поскольку q - векторный язык, большинство встроенных операций - это атомы c, и поэтому он возвращается в структуру аргумента, пока не дойдет до атомов.

Например:

(1; 2; 3) - это простой список целых чисел 1, 2, 3

(1,0; 2; (3; 4; 5) )) - это общий список 1.0 (float), 2 (int), а простой список int (3; 4; 5)

neg - это функция, которая отрицает одно число. Например:

neg 1 приводит к -1

neg -1.0 приводит к 1f

neg (1.0; 2; (3; 4; 5)) к выходам (-1f; -2; (- 3; -4; -5)).

Это то, что вдохновило меня попытаться смоделировать это поведение в Haskell типах. Тип данных должен состоять из типа атома и списка.

Ниже приведена упрощенная версия того, что у меня есть. И я также пошел дальше, чтобы попытаться сделать его экземпляром Foldable и Traversable. 

data Atom = I Int
          | C Char
          | D Double 
          deriving Show

data Q a = QAtom a 
         | QList [Q a]
         deriving Show

instance Functor Q where
    fmap f (QAtom a) = QAtom (f a)
    fmap f (QList qs) = QList $ fmap (fmap f) qs

instance Foldable Q where
    foldMap f (QAtom a) = f a
    foldMap f (QList qs) = mconcat $ fmap (foldMap f) qs

instance Traversable Q where
    sequenceA (QAtom fa) = fmap QAtom fa
    sequenceA (QList []) = pure $ QList []
    sequenceA (QList (qfa:qfas)) = concatL <$> (sequenceA qfa) <*> (sequenceA (QList qfas))
        where
            concatL (QAtom a) (QList qas) = QList ((QAtom a):qas)

Это то, что у меня есть, и оно компилируется, но мне не особенно нравится функция concatL, которая не покрывает все шаблоны в соответствии с типом. Как только я начинаю добавлять новый конструктор значений QDict [(Q Atom, Q a)] в Q, это становится еще хуже.

Правильно ли смоделированы исходные данные? Должен ли я даже попытаться сделать это Traversable? Однако я думал, что Traversable необходим, если мне нужно использовать тип данных с Maybe или Either для моделирования ошибок.

Любой совет приветствуется.

РЕДАКТИРОВАТЬ: отредактированный формат q кода

1 Ответ

7 голосов
/ 11 февраля 2020

Компилятор знает, как автоматически получить экземпляр Traversable для ваших типов. Если вы сделаете :set -ddump-deriv -dsuppress-all -XDeriveTraversable -XStandaloneDeriving, а затем deriving instance Traversable Q, вы увидите «правильный» ответ. Если вы возьмете это знание и примените его к своему экземпляру, вы получите это: 

instance Traversable Q where
    sequenceA (QAtom fa) = fmap QAtom fa
    sequenceA (QList qfas) = fmap QList (traverse sequenceA qfas)

Или если вы хотите избежать traverse в пользу sequenceA: 

instance Traversable Q where
    sequenceA (QAtom fa) = fmap QAtom fa
    sequenceA (QList qfas) = fmap QList (sequenceA (fmap sequenceA qfas))

Ключ в том, что сами списки Traversable, так что вы можете вызывать sequenceA для них без необходимости переупаковывать их по своему типу.

Примечание в вашем Экземпляр Foldable вместо цепочек mconcat и fmap, просто используйте foldMap снова, так как списки тоже Foldable: 

instance Foldable Q where
    foldMap f (QAtom a) = f a
    foldMap f (QList qs) = foldMap (foldMap f) qs
...