Haskell - 固定点集合库？

Question

Haskell - 固定点集合库？

haskellfixpoint-combinatorsfixed-point-iteration

6

我正在寻找一个库，可以计算一组可变参数运算符下的固定点/闭包。例如，

fixwith [(+)] [1]

对于整数，应该计算所有自然数N（1..）。我尝试着写了一下，但有些地方还不够。它不是很高效，并且我觉得我的多元函数处理方式不是最优雅的。此外，是否可能使用内置的fix函数而不是手动递归来编写？

class OperatorN α β | β -> α where
    wrap_op :: β -> (Int, [α] -> α)

instance OperatorN α (() -> α) where
    wrap_op f = (0, \[] -> f ())

instance OperatorN α (α -> α) where
    wrap_op f = (1, \[x] -> f x)

instance OperatorN α ((α, α) -> α) where
    wrap_op f = (2, \[x, y] -> f (x, y))

instance OperatorN α ((α, α, α) -> α) where
    wrap_op f = (3, \[x, y, z] -> f (x, y, z))

instance OperatorN α ((α, α, α, α) -> α) where
    wrap_op f = (4, \[x, y, z, w] -> f (x, y, z, w))

type WrappedOp α = (Int, [α] -> α)
fixwith_next :: Eq α => [WrappedOp α] -> [α] -> [α]
fixwith_next ops s = List.nub (foldl (++) s (map g ops)) where
    g (0, f) = [f []]
    g (arity, f) = do
        x <- s
        let fx = \xs -> f (x:xs)
        g (arity - 1, fx)
fixwith ops s
    | next <- fixwith_next ops s
    , next /= s
    = fixwith ops next
fixwith _ s = s

示例,

> fixwith [wrap_op $ uncurry (*)] [-1 :: Int]
[-1,1]
> fixwith [wrap_op $ uncurry (*)] [1 :: Int]
[1]
> fixwith [wrap_op $ max 3, wrap_op $ \() -> 0] [1 :: Int]
[1,3,0]

设置版本

这并不会显著提高性能，尽管我想我只需要找出如何减少计算量才能使其更快。

import qualified Control.RMonad as RMonad

class OperatorN α β | β -> α where
    wrap_op :: β -> (Int, [α] -> α)

instance OperatorN α (() -> α) where
    wrap_op f = (0, \[] -> f ())

instance OperatorN α (α -> α) where
    wrap_op f = (1, \[x] -> f x)

instance OperatorN α ((α, α) -> α) where
    wrap_op f = (2, \[x, y] -> f (x, y))

instance OperatorN α ((α, α, α) -> α) where
    wrap_op f = (3, \[x, y, z] -> f (x, y, z))

instance OperatorN α ((α, α, α, α) -> α) where
    wrap_op f = (4, \[x, y, z, w] -> f (x, y, z, w))

type WrappedOp α = (Int, [α] -> α)

fixwith_next :: Ord α => [WrappedOp α] -> Set α -> Set α
fixwith_next ops s = Set.unions $ s : map g ops where
    g (0, f) = RMonad.return $ f []
    g (arity, f) = s RMonad.>>= \x ->
        g (arity - 1, \xs -> f (x:xs))
fixwith' ops s
    | next <- fixwith_next ops s
    , next /= s
    = fixwith' ops next
fixwith' _ s = s
fixwith ops s = Set.toList $ fixwith' ops (Set.fromList s)

设置懒惰版本

我使用了 RMonad 来简化代码，并像Daniel建议的那样将其设置为懒惰版本。不幸的是，我认为大部分时间都花在了实际的乘法例程上，所以我没有看到这个改变带来的性能提升。但是懒惰版本很酷。

notin :: Ord α => Set α -> Set α -> Set α
notin = flip Set.difference

class Ord α => OperatorN α β | β -> α where
    next_values :: β -> Set α -> Set α

instance Ord α => OperatorN α (α -> α) where
    next_values f s = notin s $ s RMonad.>>= \x -> RMonad.return (f x)

instance Ord α => OperatorN α (α -> α -> α) where
    next_values f s = s RMonad.>>= \x -> next_values (f x) s

instance Ord α => OperatorN α (α -> α -> α -> α) where
    next_values f s = s RMonad.>>= \x -> next_values (f x) s

instance Ord α => OperatorN α (α -> α -> α -> α -> α) where
    next_values f s = s RMonad.>>= \x -> next_values (f x) s

-- bind lambdas with next_values
fixwith_next :: Ord α => [Set α -> Set α] -> Set α -> Set α
fixwith_next nv_bnd s = Set.unions $ map (\f -> f s) nv_bnd -- bound next values

fixwith' :: Ord α => [Set α -> Set α] -> Set α -> [α]
fixwith' ops s@(fixwith_next ops -> next)
    | Set.size next == 0 = []
    | otherwise = (Set.toList next) ++ fixwith' ops (Set.union s next)
fixwith ops s = (Set.toList s) ++ fixwith' ops s
fixwith_lst ops = fixwith ops . Set.fromList

示例

> take 3 $ fixwith [next_values (+2)] (Set.fromList [1])
[1,3,5]

我必须放弃一元操作，但这并不是致命的问题。

- gatoatigrado

1个回答

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

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

- Daniel Wagner · Accepted Answer

不对，fix是一个误导。它计算的是一种与你不同的固定点。

你处理参数数量的方式非常实用。有许多不同的方法可以使它少些样板代码；参见我的以前的回答中的一种方法。我相信，总会有人提出另一种基于类型级数的令人惊叹的解决方案。

就效率而言，如果只有一个Eq实例，我不确定你能做得更好。你可以考虑从调用（本地）g函数的结果中过滤出s值--也就是说，让fixwith_next仅返回新元素。这应该可以加快终止检查的速度，甚至可能使其成为一种生产力高、惰性的fixwith。

如果你可以接受严格性并需要一个Ord实例，使用真正的Set也可能会提高效率。