Связывание узла на взаимно рекурсивных ADT с хорошо типизированной обработкой ошибок

(Примечание: этот пост является файлом грамотного-haskell. Вы можете скопировать его в текст буфера, сохраните его как someFile.lhs, а затем запустите его с помощью ghc.)

Описание проблемы: я хочу создать граф с двумя разными типами node, которые ссылаются друг на друга. Пример ниже очень упрощен. Два типа данных A и B, здесь практически идентичны, но есть причина, по которой они должны быть разные в исходной программе.

У нас будет скучный материал.

> {-# LANGUAGE RecursiveDo, UnicodeSyntax #-}
> 
> import qualified Data.HashMap.Lazy as M
> import Data.HashMap.Lazy (HashMap)
> import Control.Applicative ((<*>),(<$>),pure)
> import Data.Maybe (fromJust,catMaybes)

Определения типов данных сами по себе являются тривиальными:

> data A = A String B
> data B = B String A

Чтобы символизировать разницу между ними, мы дадим им другую Show.

> instance Show A where
>   show (A a (B b _)) = a ++ ":" ++ b
> 
> instance Show B where
>   show (B b (A a _)) = b ++ "-" ++ a

И тогда связывание узла, конечно, тривиально.

> knot ∷ (A,B)
> knot = let a = A "foo" b
>            b = B "bar" a
>        in (a,b)

Это приводит к:

ghci> knot
(foo:bar,bar-foo)

Это именно то, что я хочу!

Теперь сложная часть. Я хочу создать этот график во время выполнения от пользователя вход. Это означает, что мне нужна обработка ошибок. Пусть моделируют некоторые (действительные, но бессмысленный) пользовательский ввод:

> alist ∷ [(String,String)]
> alist = [("head","bot"),("tail","list")]
> 
> blist ∷ [(String,String)]
> blist = [("bot","tail"),("list","head")]

(пользователь, конечно же, не будет вводить эти списки напрямую, сначала данные быть массированным в эту форму)

Тривиально делать это без обработки ошибок:

> maps ∷ (HashMap String A, HashMap String B)
> maps = let aMap = M.fromList $ makeMap A bMap alist
>            bMap = M.fromList $ makeMap B aMap blist
>        in (aMap,bMap)
> 
> makeMap ∷ (String → b → a) → HashMap String b
>           → [(String,String)] → [(String,a)]
> makeMap _ _ [] = []
> makeMap c m ((a,b):xs) = (a,c a (fromJust $ M.lookup b m)):makeMap c m xs

Это, очевидно, не удастся, как только список входных данных String ссылок что-то, что не найдено на соответствующих картах. "Преступник" fromJust; мы просто предполагаем, что ключи будут там. Теперь я могу просто обеспечить, чтобы пользовательский ввод действительно действителен, и просто используйте указанную выше версию. Но это требуется два прохода и не будет очень изящным, не так ли?

Итак, я попытался использовать монаду Maybe в рекурсивной привязке do:

> makeMap' ∷ (String → b → a) → HashMap String b
>           → [(String,String)] → Maybe (HashMap String a)
> makeMap' c m = maybe Nothing (Just . M.fromList) . go id
>   where go l [] = Just (l [])
>         go l ((a,b):xs) = maybe Nothing (\b' → go (l . ((a, c a b'):)) xs) $
>                                 M.lookup b m
> 
> maps' ∷ Maybe (HashMap String A, HashMap String B)
> maps' = do rec aMap ← makeMap' A bMap alist
>                bMap ← makeMap' B aMap blist
>            return (aMap, bMap)

Но это заканчивается бесконечным циклом: aMap требуется bMap для определения, а bMap требуется aMap. Однако, прежде чем я могу даже начать доступ к ключам на любой карте, он должен быть полностью оценен, чтобы мы знали, является ли это Just или Nothing. Я считаю, что вызов Maybe в makeMap' меня укусил. Это содержит скрытое выражение case и, следовательно, опровержимый шаблон.

То же самое верно для Either, поэтому использование некоторого трансформатора ErrorT не будет помогите нам здесь.

Я не хочу возвращаться к исключениям во время выполнения, поскольку это отскочит назад к монаде IO, и это будет допускать поражение.

Минимальная модификация приведенного выше рабочего примера - просто удалить fromJust и выполняйте только те результаты, которые действительно работают.

> maps'' ∷ (HashMap String A, HashMap String B)
> maps'' = let aMap = M.fromList . catMaybes $ makeMap'' A bMap alist
>              bMap = M.fromList . catMaybes $ makeMap'' B aMap blist
>          in (aMap, bMap)
> 
> makeMap'' ∷ (String → b → a) → HashMap String b → [(String,String)] → [Maybe (String,a)]
> makeMap'' _ _ [] = []
> makeMap'' c m ((a,b):xs) = ((,) <$> pure a <*> (c <$> pure a <*> M.lookup b m))
>                            :makeMap'' c m xs

Это тоже не работает, и, что любопытно, приводит к немногому поведению!

ghci> maps' -- no output
^CInterrupted.
ghci> maps'' -- actually finds out it wants to build a map, then stops.
(fromList ^CInterrupted

Использование отладчика показало, что это даже не бесконечные циклы (как я и ожидал), но выполнение просто прекращается. С maps' я ничего не получаю, со второй попыткой я, по крайней мере, добираюсь до первого поиска, а затем останавливаюсь.

Я в тупике. Чтобы создать карты, мне нужно проверить ввод, но для его проверки мне нужно создать карты! Два очевидных ответа: косвенность и предварительная валидация. Оба они являются практичными, если несколько неэлегантными. Я хотел бы знать, можно ли делать ошибки в строке.

Является ли то, что я спрашиваю, с системой типа Haskell? (Это вероятно, есть, и я просто не могу понять, как.) Очевидно, это возможно пересылая исключения до верхнего уровня в fromJust, а затем перехватывая их в IO, но это не то, как я хотел бы это сделать.