1

我正在尝试将以下命令式代码转换为 Haskell 中的功能解决方案。我想将集合s的成员与集合s'和更新集合的成员进行比较，t并t'基于比较。这是命令式伪代码：

-- s, s', t, t' are of type Data.Set a
-- foo x y returns a Just a or Nothing 
foo :: a -> a -> Just a

-- Initialize t and t' to s and s'
t = s
t = s'

foreach x in s
  foreach y in s'
      if (foo x y) == Just z
        insert z into t
        delete x from t
        delete y from t'

return (t, t')

我希望的 Haskell 函数的类型可能是这样的，

mergeSets :: S.Set -> S.Set -> (S.Set, S.Set)
mergeSets s s' = ...

其中S是类型Data.Set，函数的结果将是与新集合t和的一对t'（或返回集合t和的其他方式t'）。

4

2 回答 2

4

这是一种可能性：

bar s s' =
  foldl (\ (t,t') (z,(x,y)) -> 
              ( delete x (insert z t) , delete y t' ))
    (s,s')
    [(z,(x,y)) | x <- toList s, y <- toList s', Just z <- [foo x y]]

这里的主要问题是您是否打算让您的插入和删除干扰该foreach机制。以上假设您没有。

如果你的集合很大，你可能需要增加严格性，以避免重击爆炸：

bar s s' = foldl (\ (t,t') (z,(x,y)) ->
             let a=insert z t; b=delete x a; c=delete y t' 
             in a `seq` b `seq` c `seq` (b,c) )
    ....
于 2013-03-02T22:52:18.093 回答
2

如果您使用的是集合数据类型Set，通常不会在元素上编写循环。这将更适合列表。因此，如果您的算法需要以某种嵌套方式枚举所有元素，请将 Set 转换为列表。

所以，我会尽量避免完全在集合上使用嵌套循环算法，而是在集合操作方面寻找一些声明性规范：交集、联合、差异等。

如果这是不可能的，那么对列表的天真翻译当然是可能的：

import qualified Data.Set as S

mergeSets :: Ord a => S.Set a -> S.Set a -> (S.Set a, S.Set a)
mergeSets s t = go1 (S.toList s) s t
    where
        go1 []     t t' = (t,t')
        go1 (x:xs) t t' = go1 xs u u'
            where
                (u, u') = go2 x (S.toList t) t t'

        go2 x []     t t'       = (t,t')
        go2 x (y:ys) t t'
            | Just z <- foo x y = go2 x ys (S.delete x (S.insert z t)) (S.delete y t')
            | otherwise         = go2 x ys t t'

-- for example
foo x y = if x == y then Just x else Nothing

简单的一点是对嵌套循环进行建模。我们可以使用例如列表推导。但是，您的算法使用输出集的变异，因此我们需要将其作为累积参数传递。

不过，要真正很好地将这一点融入 Haskell，我们需要放弃逐个元素的命令式风格，并根据自然的 Set api 工作。这将是你通往一个好的解决方案的道路。

于 2013-03-02T22:52:08.423 回答