(说明:本篇文章是一个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
中捕获它们来实现它,但这不是我想做的事情。
ReaderT maps (Writer (Either errs assocs)) a
monad 中做了类似的事情。棘手的部分是,当你告诉 writer 一个关联(或错误)时,你必须无条件地告诉(即,告诉一个 thunk,稍后会决定它是错误还是关联)。然后,当你绑定 knot 时,运行 writer,并在那个时候强制记录日志,同时构造将被反馈到 reader 中的 maps。整个过程非常脆弱,所以虽然这是一个有趣的练习,但在我看来,值得将其重写为两个单独的 passes。 - LambdageekWriter
中进行,一次在为ReaderT
制作映射表时进行。 - GS - Apologise to MonicaNothing
或Left error
或类似的整个计算? - GS - Apologise to MonicaMaybe
和Either
都属于相同的抽象类,因此在这里简化的最小示例中选择了更简单的一个。 - Aleksandar DimitrovST
以命令式的方式实现它。我担心你是正确的,整个事情可能会变得太脆弱。我将不得不看看它是否在我正在编写的程序的上下文中很好地工作(一个解释器,这是类型图,其中A
就像记录,而B
则是实际类型)。 - Aleksandar Dimitrov