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

Question

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

Описание проблемы: Я хочу создать граф с двумя разными типами узлов, которые ссылаются друг на друга. Пример ниже: очень упрощенный. Два типа данных 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 монада в рекурсивной сделать обязательными:

> 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, и это будет признавать поражение.

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

> 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, но это не то, как я хотел бы это сделать.

Answer 1

Проблема заключается в том, что когда вы связываете узел, вы не «строите» структуры A и B, а просто объявляете, как они должны быть построены, и затем они оцениваются по мере необходимости. Это, естественно, означает, что если проверка выполняется «in-line» с оценкой, проверка ошибок должна произойти в IO, потому что это единственное, что может вызвать оценку (в вашем случае это когда вы печатаете вывод show).

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

import Data.Traversable (sequenceA) 

maps' :: Maybe (HashMap String A, HashMap String B) 
maps' = 
    let maMap = M.fromList $ map (makePair A mbMap) alist 
     mbMap = M.fromList $ map (makePair B maMap) blist 
     makePair c l (k,v) = (k, c k . fromJust <$> M.lookup v l) 
    in (,) <$> sequenceA maMap <*> sequenceA mbMap 

Это первое определяют взаимно рекурсивную карту maMap и mbMap, которые имеют тип HashMap String (Maybe A) и HashMap String (Maybe B) соответственно, т.е. что они будут содержать все ключи узла, но ключи связаны с Nothing, если узел был недействителен.«Обман» происходит в

c k . fromJust <$> M.lookup v l 

Это в основном просто посмотреть ссылочный узел с M.lookup и если это удастся, мы просто предполагаем, что возвращаемый узел является действительным, и использовать fromJust. Это предотвратит бесконечный цикл, который в противном случае возник бы, если бы мы попытались проверить уровни Maybe на всем пути вниз. Если поиск не выполняется, этот узел недействителен, то есть Nothing.

Далее мы переводим карты «наизнанку» Maybe (HashMap String a) с использованием sequenceA из Data.Traversable. Результирующее значение составляет Just _, только если каждый узел внутри карты был Just _ и Nothing в противном случае. Это гарантирует, что описанный выше номер fromJust не может потерпеть неудачу.