Ale*_*rov 10 haskell recursive-datastructures tying-the-knot
(注意:这篇文章是一个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")]
(用户当然不会直接输入这些列表;数据首先会被按下到这个表单中)
在没有错误处理的情况下执行此操作是微不足道的:
> 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在递归do绑定中使用monad:
> 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.但是,在我甚至可以开始访问任一映射中的键之前,需要对其进行全面评估,以便我们知道它是a Just还是a
Nothing.要在通话maybe中makeMap'就是这里我咬,我想.它包含一个隐藏的case表达式,因此是一个可反射的模式.
同样的情况也是如此,Either所以使用一些ErrorT变压器对我们没有帮助.
我不想回到运行时异常,因为这会让我反弹回IOmonad,这将是承认失败.
对上述工作示例的最小修改只是删除
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,但这不是我想要的方式.
问题是,当你喜结良缘你不"建"的结构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.
接下来,我们使用from 将HashMap String (Maybe a)地图"从里到外"转换为Maybe (HashMap String a)地图.结果值仅在地图内的每个节点都是,否则.这保证了我们上面使用的不会失败.sequenceAData.TraversableJust _Just _NothingfromJust