用具有良好类型化错误处理的相互递归ADT打结

Question

用具有良好类型化错误处理的相互递归ADT打结

haskellrecursive-datastructurestying-the-knot

10

（说明：本篇文章是一个Literate 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")]

(当然，用户不会直接输入这些列表；数据将首先进行处理，变成这种格式)

如果不进行错误处理，这很容易实现：without。

> 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; 我们只是假设键会在那里。现在，我可以确保用户输入实际有效，并使用上述版本。但是，这将需要两个传递，并且不太优雅，不是吗？

因此，我尝试在递归的do绑定中使用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。在makeMap'中调用maybe是导致我困扰的原因，我想。它包含一个隐藏的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中捕获它们来实现它，但这不是我想做的事情。

- Aleksandar Dimitrov

1

我其实非常喜欢只进行快速预处理检查的想法，并且我有一种感觉，它最终会比你所考虑的错误处理方法简单得多。此外，你确定要使用绑定结构来表示图形吗？如果你在其上进行映射，该结构可能会解开，而在遍历过程中检查节点的身份或避免循环也更加困难。直接使用你制作的邻接列表或使用可变引用可能是要考虑的替代方案。 - hugomg

我在一个 ReaderT maps (Writer (Either errs assocs)) a monad 中做了类似的事情。棘手的部分是，当你告诉 writer 一个关联（或错误）时，你必须无条件地告诉（即，告诉一个 thunk，稍后会决定它是错误还是关联）。然后，当你绑定 knot 时，运行 writer，并在那个时候强制记录日志，同时构造将被反馈到 reader 中的 maps。整个过程非常脆弱，所以虽然这是一个有趣的练习，但在我看来，值得将其重写为两个单独的 passes。 - Lambdageek

@Lambdageek - 你所描述的实际上是一个双通道算法吗？一次在Writer中进行，一次在为ReaderT制作映射表时进行。 - GS - Apologise to Monica

你实际上想为无效输入做什么 - 只是产生Nothing或Left error或类似的整个计算？ - GS - Apologise to Monica

@GaneshSittampalam 最终，我想生成一个“左错误”，但由于Maybe和Either都属于相同的抽象类，因此在这里简化的最小示例中选择了更简单的一个。 - Aleksandar Dimitrov

2

@Lambdageek，我想我知道你的意思。这里有一个类似的想法。我也认为可以使用ST以命令式的方式实现它。我担心你是正确的，整个事情可能会变得太脆弱。我将不得不看看它是否在我正在编写的程序的上下文中很好地工作（一个解释器，这是类型图，其中A就像记录，而B则是实际类型）。 - Aleksandar Dimitrov

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- shang · Accepted Answer

问题在于，当你打算将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。

接下来，我们使用Data.Traversable中的sequenceA将HashMap String (Maybe a)映射“内翻”成Maybe (HashMap String a)映射。仅当映射中的每个节点都是Just _时，结果值才为Just _，否则为Nothing。这保证了我们上面使用的fromJust不会失败。