Связывание узла на взаимно рекурсивных 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

Это очевидно потерпит неудачу, как только список ввода Strings ссылается на то, что не найдено на соответствующих картах. "Виновник" 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 Монада, и это будет признавать поражение.

Минимальная модификация приведенного выше рабочего примера - просто удалить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' Я ничего не получаю, со второй попытки я по крайней мере добираюсь до первого поиска, а затем глохну.

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

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

Answer 1

Проблема в том, что когда вы связываете узел, вы не "строите" структуры A а также B а скорее просто объявите, как они должны быть построены, а затем они будут оценены, когда это необходимо. Это, естественно, означает, что если проверка выполняется "в строке" с оценкой, то проверка ошибок должна выполняться в 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,

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