Сообщение об ошибке, которое вы получаете от SBV, действительно загадочное, что, к сожалению, не очень помогает. Я только что установил патч для github, и, надеюсь, новое сообщение об ошибке немного лучше:
*** Exception:
*** Data.SBV.Mergeable: Cannot merge instances of lists.
*** While trying to do a symbolic if-then-else with incompatible branch results.
***
*** Branches produce different sizes: 1 vs 0
***
*** Hint: Use the 'SList' type (and Data.SBV.List routines) to model fully symbolic lists.
SBV пытается сказать вам, что когда у вас есть символическое if-then-else (как в вашей getSAncestor функции), которое возвращает Haskell список SBV Person, то он не может объединить эти ветви, если в каждой ветви ite нет одинакового количества элементов.
Проблема
Вы, конечно, можете спросить, почему существует такое ограничение. Рассмотрим следующее выражение:
ite cond [s0, s1] [s2, s3, s4]
Интуитивно, это должно означать:
[ite cond s0 s2, ite cond s1 s3, ite cond ??? s4]
К сожалению, SBV ничто не может заменить ??? и, следовательно, сообщение об ошибке. Я надеюсь, что это имеет смысл!
Два вида списков
У SBV есть два вида представления списка символических элементов. Одним из них является старый добрый Haskell список символьных значений, который вы использовали; который подчиняется ограничению мощности, описанному выше для каждой символьной ите. Другой - полностью символический список, который отображается на последовательности SMTLib. Обратите внимание, что в обоих случаях размер списка является произвольным, но конечным, но есть разница в том, будем ли мы обрабатывать позвоночник символически или нет.
Бетонные символические списки позвоночника
Когда вы используете тип, такой как [SBV a], вы, по сути, говорите: «Хребет этого списка конкретный, а сами элементы символические». Этот тип данных наиболее подходит, когда вы точно знаете, сколько элементов у вас будет в каждой ветви, и все они имеют одинаковый размер.
Эти списки отображаются в гораздо более простое представление через бэкэнд, по сути, часть «списка» обрабатывается в Haskell, а элементы символически представлены точечно. Это позволяет использовать многие решатели SMT, даже те, которые не понимают символьные последовательности. С другой стороны, у вас не может быть символического позвоночника, как вы узнали.
Списки символов позвоночника
Второй вид, как вы можете догадаться, это вид списка, в котором сам позвоночник является символическим и, следовательно, может поддерживать произвольные условия ите без ограничений по количеству элементов. Они отображаются непосредственно на последовательности SMTLib и намного более гибки. Недостатком является то, что не все решатели SMT поддерживают последовательности, и логика последовательности вообще не разрешима, поэтому решатели могут ответить unknown, если случится так, что запрос выходит за рамки того, что могут обрабатывать их алгоритмы. (Другим недостатком является то, что логика последовательностей, поддерживаемая z3 и cvc4, является довольно незрелой, поэтому у самих решателей могут быть ошибки. Но они всегда должны сообщаться!)
Решение
Для решения вашей проблемы вам просто нужно использовать символические списки позвоночника SBV, известные как SList. Модификации, необходимые для вашего примера программы, относительно просты:
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV
import Data.List
import Data.SBV.List as L
data Person
= Mary
| Richard
| Claudia
| Christian
| Stephen
mkSymbolicEnumeration ''Person
-- symbolic shorthands for person constructors
[mary, richard, claudia, christian, stephen] =
map literal [Mary, Richard, Claudia, Christian, Stephen]
childOf :: [(Person, Person)]
childOf = [
(Mary, Richard) ,
(Richard, Christian),
(Christian, Stephen)]
getAncestors :: Person -> [Person]
getAncestors p = go childOf p []
where
go [] _ acc = nub acc
go ((p1, p2): rels) a acc
| p1 == p = go rels p (p2:acc) ++ getAncestors p2
| otherwise = go rels a acc
-- symbolic version of getAncestors
getSAncestors :: SBV Person -> SList Person
getSAncestors p = ite (p .== mary) (literal (getAncestors Mary))
$ ite (p .== richard) (literal (getAncestors Richard))
$ ite (p .== claudia) (literal (getAncestors Claudia))
$ ite (p .== christian) (literal (getAncestors Christian))
(literal (getAncestors Stephen))
cspAncestors :: IO AllSatResult
cspAncestors = allSat $ do
(person :: SBV Person) <- free "person"
constrain $ sNot $ L.singleton stephen `L.isInfixOf` (getSAncestors person)
(Примечание: я должен был изменить bnot на sNot, так как я использую SBV 8.0, доступный от hackage; у которого было это изменение имени. Если вы используете 7.12, вы должны оставить bnot. Также обратите внимание на использование SList Person вместо [SBV Person], которое говорит SBV использовать символические списки позвоночника.)
Когда я запускаю это, я получаю:
*Main> cspAncestors
Solution #1:
person = Claudia :: Person
Solution #2:
person = Stephen :: Person
Found 2 different solutions.
Я действительно не проверял, верен ли ответ, но я верю, что так и должно быть! (Если нет, пожалуйста, сообщите.)
Я надеюсь, что это дает обзор проблемы и как ее решить. Хотя SMT-решатель не может превзойти собственный CSP-решатель, я думаю, что он может быть отличной альтернативой, если у вас нет выделенного алгоритма. Надеюсь, Haskell / SBV облегчает использование!