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

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

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

Например:

(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 необходим, если мне нужно использовать тип данных с Maybe или Either для моделирования ошибок.

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

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


haskell algebraic-data-types traversable kdb
person dhu    schedule 11.02.2020    source источник
comment
Предварительный совет: я бы определил Q без переменной типа, как data Q = QAtom Atom | QList [Q]. Это позволяет вам создавать списки типа QList [QAtom (D 1.0), QAtom (I 2), QList [QAtom (I 3), QAtom (I 4), QAtom (I 5)]], как в вашем примере с Q; вы не можете представить такую ​​структуру своим текущим типом. Но кроме этого я не знаю; Мне нужно еще немного изучить ваш код и посмотреть, не найду ли я что-нибудь еще, чтобы дать совет. РЕДАКТИРОВАТЬ: Я был неправ, см. следующий комментарий   -  person bradrn    schedule 11.02.2020
comment
На самом деле, нет, неважно: я неправильно истолковал ваш конструктор QAtom a как QAtom (Atom a). Ваше текущее определение Q действительно хорошо! Извините за путаницу.   -  person bradrn    schedule 11.02.2020
comment
Что касается вашего экземпляра Traversable: я думаю, вам обязательно стоит сделать его экземпляром Foldable и т. Д., Но, как вы уже заметили, ваш экземпляр Traversable немного забавен. Лучший способ реализовать этот случай - избежать сопоставления с образцом и вместо этого использовать экземпляр Traversable []: sequenceA (QList fl) = fmap QList $ sequenceA $ fmap sequenceA fl. (Вы можете представить себе это как упорядочивание каждого отдельного элемента QList, а затем упорядочение всего списка действий, который дает вам.) Но я считаю, что гораздо проще реализовать traverse, чем sequenceA.   -  person bradrn    schedule 11.02.2020
comment
Утверждение, что Списки - это упорядоченные коллекции, построенные из атомов, вводит в заблуждение. Это верно в некотором тривиальном смысле, потому что все типы в KDB в конечном итоге построены из атомов, но только простые списки строятся непосредственно из атомов. В любом случае, для лучшего понимания того, как типы данных q представлены в KDB, вы можете взглянуть на файл заголовка KDB для интерфейса C (k.h, можно найти на code.kx.com). Еще один полезный ресурс - это коллекция интерфейсов для KDB для Erlang, Java, C # и Python по адресу github.com/exxeleron , которые выражают типы данных KDB / q на этих языках.   -  person Slawomir K.    schedule 11.02.2020

Ответы (1)


arrow_upward
7
arrow_downward

Компилятор знает, как автоматически получить экземпляр 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
person Joseph Sible-Reinstate Monica    schedule 11.02.2020
comment
Я не думаю, что у каждого типа есть не более одного проходимого экземпляра. Я могу придумать как минимум два на data Pair a = Pair a a - person luqui; 11.02.2020